hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
HVM Integer Arithmetic Question

 
Reply to topic    hacker.org Forum Index » Challenges View previous topic
View next topic
HVM Integer Arithmetic Question
Author Message
AMindForeverVoyaging
Forum Admin


Joined: 28 May 2011
Posts: 472
Location: Germany

Post HVM Integer Arithmetic Question Reply with quote
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:

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?


Last edited by AMindForeverVoyaging on Thu Sep 08, 2011 9:18 am; edited 1 time in total
Wed Sep 07, 2011 3:47 pm View user's profile Send private message
CodeX



Joined: 17 Oct 2008
Posts: 350

Post Reply with quote
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.
Wed Sep 07, 2011 4:56 pm View user's profile Send private message
laz0r



Joined: 04 Feb 2010
Posts: 290
Location: Within the depths of Unix

Post Reply with quote
"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...

_________________
There is no spoon.
Wed Sep 07, 2011 5:46 pm View user's profile Send private message
AMindForeverVoyaging
Forum Admin


Joined: 28 May 2011
Posts: 472
Location: Germany

Post Reply with quote
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:

!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 Razz
Thu Sep 08, 2011 9:00 am View user's profile Send private message
CodeX



Joined: 17 Oct 2008
Posts: 350

Post Reply with quote
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-+
Thu Sep 08, 2011 10:03 am View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Challenges All times are GMT
Page 1 of 1

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.