4 ms·

I think my preference is more towards conciseness. I made a stack machine with single character instructions and needed to solve a variation of this problem.

by Lerc 2y ago

I think my preference is more towards conciseness. I made a stack machine with single character instructions and needed to solve a variation of this problem. I had just the digits 0 through 9. The characters '23' would be push 2 followed by push 3. To actually represent the number 23 you would use 45*3+ or something similar. That left me with the problem of how to encode each integer in the fewest characters. Tools at hand. The digits 0 through 9 'P': Pi '*': (a * b), '/': (a / b), '-': (a - b), '+': (a + b), 's': sin(a), 'c': cos(a), 'q': sqrt(a), 'l': log(a), '~': abs(a), '#': round(a), '$': Math.floor(a), 'C': clamp(a), '<': min(a, b), '>': max(a, b), '^': pow(a, b), 'a': atan2(a, b), '%': positiveMod(a, b), '!': (1 - a), '?': (a <= 0 ? 0 : 1) 'o': a xor b scaled by c; ((a*c) xor (b*c))/c 'd': duplicate the top stack entry ':': swap the top two stack entries ';': swap the top and third stack entries I have wondered about revisiting the stack machine with a complex number stack to see what I can come up with. (Next time I post something like this I am not going to use my phone)

Y_Y 2y ago
The answer in general may be uncomputable. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
- Lerc 2y ago
  AHH but in practice you are limited to 50 characters. https://c50.fingswotidun.com/ https://c50.fingswotidun.com/ Which gives you a finite problem. The VM cannot loop or define functions (yet, anyway) so it doesn't go all busy beaver on you.
  - Y_Y 2y ago
    I thought it would be possible to use the (undocumented?) T instruction and use the time variable as persistent memory, but it seems to reset each step. It would be nice if there were a way to store things across time steps!
    - Lerc 2y ago
      ooh, hadn't thought about persistence. I always considered all executions running in isolation (and not necessarily in-order). Persistence would have to decide if it was localized to the same pixel, next frame or pass between pixels. A possibility for that is an instruction that sets a value in a buffer at the same resolution of the output and a paired instruction that reads the buffer generated the previous frame (with location popped from stack) so if { was write to buffer, it writes the top stack value to the buffer at the same location as the pixel output. using } to read would mean if you started a program with "xy}" would place the value from the buffer on the stack. It would also allow fade and blur effects. In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack. Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off. I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.
- nwallin 2y ago
  Kolmogorov complexity is uncomputable because it admits Turing complete languages, and reduces to the halting problem. If the language you admit isn't Turing complete, then the Kolmogorov complexity of the thing is computable. It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program. If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.
  - deleted 2y ago
    [deleted]
celdon25 2y ago
Reminds me of https://www.hacker.org/hvm/ https://www.hacker.org/hvm/ (2008)
Dylan16807 2y ago
I suspect a whole lot of numbers are going to get encoded in base 9 or 10 as mostly repetitions of digit + * digit + * or equivalent.
saulpw 2y ago
What about making each digit be the instruction "times 10 plus digit", with a different instruction to push a 0, like a space? Then you can represent 23 with " 23".
- rixed 2y ago
  Still, some numbers would admit a shorter sequence of instructions

by Lerc 2y ago

Y_Y 2y ago

The answer in general may be uncomputable. https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity

Lerc 2y ago
AHH but in practice you are limited to 50 characters. https://c50.fingswotidun.com/ https://c50.fingswotidun.com/ Which gives you a finite problem. The VM cannot loop or define functions (yet, anyway) so it doesn't go all busy beaver on you.
- Y_Y 2y ago
  I thought it would be possible to use the (undocumented?) T instruction and use the time variable as persistent memory, but it seems to reset each step. It would be nice if there were a way to store things across time steps!
  - Lerc 2y ago
    ooh, hadn't thought about persistence. I always considered all executions running in isolation (and not necessarily in-order). Persistence would have to decide if it was localized to the same pixel, next frame or pass between pixels. A possibility for that is an instruction that sets a value in a buffer at the same resolution of the output and a paired instruction that reads the buffer generated the previous frame (with location popped from stack) so if { was write to buffer, it writes the top stack value to the buffer at the same location as the pixel output. using } to read would mean if you started a program with "xy}" would place the value from the buffer on the stack. It would also allow fade and blur effects. In a similar vein I had wondered about a kernel function that read from a buffer with a 3x3 kernel on the stack. Perhaps I should revisit the idea. Using a stack with multiple lanes of floats would potentially richer operations, colors, complex numbers, quaternions? 4 lanes could potentially Even storing the top value of the stack at the base for the next frame. Or, (new idea) a cyclic buffer stack of a fixed length. That wouldn't require any memory management at render time, and could persist multiple values just by popping them off. I'm not sure how that would impact the speed. At the moment the stack expressions are converted into JavaScript expressions for the JIT to make fast. I'd have to go back to requiring an actual stack again.
nwallin 2y ago
Kolmogorov complexity is uncomputable because it admits Turing complete languages, and reduces to the halting problem. If the language you admit isn't Turing complete, then the Kolmogorov complexity of the thing is computable. It looks like OP's language is not Turing complete. It always terminates. You can just do a breadth first search on the program space. The first program you get that outputs the number you want is the shortest program. If it were Turing complete, you can't do this, because eventually you'll find a program that just keeps running for like a really long time. Is it running because the program never halts? Or is will it halt eventually and output the number you want? You can't know for sure.
- deleted 2y ago
  [deleted]

celdon25 2y ago

Reminds me of https://www.hacker.org/hvm/ https://www.hacker.org/hvm/ (2008)

Dylan16807 2y ago

I suspect a whole lot of numbers are going to get encoded in base 9 or 10 as mostly repetitions of digit + * digit + * or equivalent.

saulpw 2y ago

What about making each digit be the instruction "times 10 plus digit", with a different instruction to push a 0, like a space? Then you can represent 23 with " 23".

rixed 2y ago
Still, some numbers would admit a shorter sequence of instructions