hacker.org

Posted: **Wed Sep 07, 2011 3:47 pm**

I'm not sure if I understand the signed integer arithmetic of the HVM correctly. Take for example this code which is a bit lengthy, but mathematically correct:

(EDIT: Added line breaks to make the example look less ugly. hackvm.py seems to allow them when interpreting the code)

Code: Select all

12+
4+
8+
82*+
84*+
88*+
88*2*+
88*4*+
88*8*+
88*8*2*+
88*8*4*+
88*8*8*+
88*8*8*2*+
88*8*8*4*+
88*8*8*8*+
88*8*8*8*2*+
88*8*8*8*4*+
88*8*8*8*8*+
88*8*8*8*8*2*+
88*8*8*8*8*4*+
88*8*8*8*8*8*+
88*8*8*8*8*8*2*+
88*8*8*8*8*8*4*+
88*8*8*8*8*8*8*+
88*8*8*8*8*8*8*2*+
88*8*8*8*8*8*8*4*+
88*8*8*8*8*8*8*8*+
88*8*8*8*8*8*8*8*2*+
88*8*8*8*8*8*8*8*4*+
88*8*8*8*8*8*8*8*8*+p!

It computes 2^0 + 2^1 + 2^2 + ... + 2^28 + 2^29 + 2^30, which is the same as 2^31-1. The printed result is, correctly so, 2147483647. This is the largest positive number which can be stored in a signed 32-bit integer, which is what the HVM description claims is being used.

Now, what happens if I add 1 to that? The result printed is 2147483648. I don't know how this would be possible, since this number cannot be held in a signed 32-bit integer. I would either expect an error message ("integer overflow", this is what happens in the JavaScript implementation), or a "wrap around" to the number -2147483648, but neither of that happens using the official implementation (hackvm.py).
So, is my understanding of things wrong here, or is this an error in the Python implementation of the HVM? Or is the HVM working correctly, and it is rather the documentation which is erroneous?

Posted: **Wed Sep 07, 2011 4:56 pm**

Although the HVM page says the data is 32 bit the python implementation actually works with 64 bit limits, however the implementation for the challenges uses 32 bit or so I assume from checking King Rat but it may be different for other challenges as I don't know behind the scenes.

Posted: **Wed Sep 07, 2011 5:46 pm**

"For implementation reasons, those integers are currently limited to 32 bits, but do not count on it, they could be large in future implementations."
I think adum's just forgotten to update this bit...

Posted: **Thu Sep 08, 2011 9:00 am**

CodeX wrote:however the implementation for the challenges uses 32 bit or so I assume from checking King Rat but it may be different for other challenges as I don't know behind the scenes.

I would have thought that the same implementation is used for judging all of the HVM challenges...

When I extend the example above to compute 2^63-1, and then add 1 to the result, I get:

Code: Select all

!ERROR: exception while executing I=+ PC=1375 STACK_SIZE=0
integer overflow

Well there goes my idea to create a -1 by a wrap-around, and to use that to beat the "Brokenest Keys" challenge

Posted: **Thu Sep 08, 2011 10:03 am**

I was a bit miffed by the overflow fault too as it could have had a few applications, also here's a slightly shorter way to get to the limits of the 32 and 64 bit integers:
2³¹-1 -> 88*0^0^*0^**0^1-+
2⁶³-1 -> 88*0^0^*0^**2*0^*0^1-+

hacker.org

HVM Integer Arithmetic Question

HVM Integer Arithmetic Question