What is the official behavior of ruby in case of integer overflow?
Thanks
jacob navia wrote:
What is the official behavior of ruby in case of integer overflow?
Integers overflow from Fixnums (30 bits) into Bignums (unlimited
precision integers).
irb(main):003:0> x = 2**30 - 1
=> 1073741823
irb(main):004:0> x.class
=> Fixnum
irb(main):005:0> x+1
=> 1073741824
irb(main):006:0> (x+1).class
=> Bignum
On 2009-09-13, Joel VanderWerf [email protected] wrote:
irb(main):005:0> x+1
=> 1073741824
irb(main):006:0> (x+1).class
=> Bignum
I looked briefly at the code underlying this. I am not totally
convinced that
it’s impossible for a calculation (especially a multiplication) to evade
the
overflow detection used.
-s
Seebs –
I haven’t looked at it in several years, but at one time I was pretty
deep in that code and my recollection is that it’s solid. Can you
explain your misgivings in more detail (e.g. outline a hypothetical
failure mode, even if you can’t produce a concrete example)?
– MarkusQ
On 2009-09-14, Markus R. [email protected] wrote:
I haven’t looked at it in several years, but at one time I was pretty
deep in that code and my recollection is that it’s solid. Can you
explain your misgivings in more detail (e.g. outline a hypothetical
failure mode, even if you can’t produce a concrete example)?
I’m not sure I can.
The first thing to keep in mind: Overflow in signed integers is pure
undefined behavior, so we don’t have any guarantee that we get exactly
the expected results. This is my big misgiving; I don’t necessarily
expect any consistent behavior on overflow. (We only have a promise of
modulos-N overflow for unsigned integers.)
Quick review:
#define INT2FIX(i) ((VALUE)(((long)(i))<<1 | FIXNUM_FLAG))
#define LONG2FIX(i) INT2FIX(i)
#define FIX2LONG(x) RSHIFT((long)x,1)
So, the value 0x03 represents the long value 1, and the value 3 would
become
the fix value 0x7.
long a, b, c;
VALUE r;
a = FIX2LONG(x);
if (a == 0) return x;
b = FIX2LONG(y);
c = a * b;
r = LONG2FIX(c);
if (FIX2LONG(r) != c || c/a != b) {
r = rb_big_mul(rb_int2big(a), rb_int2big(b));
}
return r;
Hmm.
I guess the likely boundary cases would be near 2^(n/2) or thereabouts.
If a and b are both 2^16, c will be 2^32, which we suspect comes out 0,
so we trip the c/a != b. Hmm. I think this is going to work, because
the
/a will produce 0 in most overflow cases. In particular, it can’t
actually
produce b, because if c/a == b, then b had no higher bits than those
that
survived the multiplication.
Well, let’s see. Imagine that c is 2^30. The creation of r is
undefined
behavior, because E1*2 is not representable in the result type. On most
systems, we’ll end up with r being -(2^31)+1 (0x80000001). When we
calculate
FIX2LONG(r), we will get either 0xc0000000 or 0x40000000, probably –
it’s
implementation-defined. So 2^30 would become a bignum, which I guess is
probably intentional, since it’s out of the effective range of a 31-bit
integer.
In terms of strict C conformance, then, the code is not safe – it
invokes
undefined behavior at least twice for some plausible input values. I’m
pretty sure that on most current CPUs, it’ll do what is intended. I
also
don’t know what the desired behavior would be for FIX2LONG(LONG2FIX())
on
2^30; I am pretty sure that there exist both systems which zero-fill and
systems which sign-extend on right shift.
-s
On 2009-09-15, David M. [email protected] wrote:
Fixnum seems to be a signed 63-bit integer (62 bits plus the sign bit) on my
64-bit system. I’m guessing that it’s actually a 31-bit signed integer on a
32-bit system.
That’s how it’s been described.
This is nice in that my programs don’t really care, but will use a 64-bit
integer where it’s efficient – yet it strikes me that for smaller numbers, 32
bits would be more efficient, RAM-wise, if nothing else.
They might, but using a native word as the one and only standard
variable type
is more efficient than needing to use a special something-else to
identify
that a given object is, in fact, a 32-bit fixnum rather than a native
word.
So if native words are 64-bit for other reasons, this behavior makes
sense.
-s
On Sunday 13 September 2009 05:52:03 pm Joel VanderWerf wrote:
jacob navia wrote:
What is the official behavior of ruby in case of integer overflow?
Integers overflow from Fixnums (30 bits) into Bignums (unlimited
precision integers).
Not entirely accurate, apparently:
irb(main):009:0> (262-1).class
=> Fixnum
irb(main):010:0> (262).class
=> Bignum
irb(main):012:0> ((-2)**62-1).class
=> Fixnum
irb(main):013:0> ((-2)**62).class
=> Bignum
Fixnum seems to be a signed 63-bit integer (62 bits plus the sign bit)
on my
64-bit system. I’m guessing that it’s actually a 31-bit signed integer
on a
32-bit system.
This is nice in that my programs don’t really care, but will use a
64-bit
integer where it’s efficient – yet it strikes me that for smaller
numbers, 32
bits would be more efficient, RAM-wise, if nothing else. Then again, I
don’t
know from this (nor should I have to care) how many bits Fixnum actually
uses.
Other interesting things: There only seems to be one Float class, and it
can’t
go as high as Bignum.
irb(main):033:0> (21023).to_f
=> 8.98846567431158e+307
irb(main):034:0> 21024
=>
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216
irb(main):035:0> (2**1024).to_f
=> Infinity
And there’s your answer for overflow behavior. It seems Bignum integers
will
happily consume all your RAM if you let them, whereas Floats will
occasionally
round up to Infinity.
On Tue, Sep 15, 2009 at 8:07 AM, Colin B.
[email protected] wrote:
JRuby 1.3.1 JIRB:
n = if RUBY_PLATFORM.downcase == “java” then 63 else 30 end  #=> 63
nn = 2 ** n - 1 ; “#{nn.class}  #{nn}”  #=> Fixnum  9223372036854775807
nn = -nn     ; “#{nn.class}  #{nn}”  #=> Fixnum  -9223372036854775807
nn = 2 ** n   ; “#{nn.class}  #{nn}”  #=> Bignum  9223372036854775808
nn = -nn     ; “#{nn.class}  #{nn}”  #=> Fixnum  -9223372036854775808
nn = 2 ** n + 1 ; “#{nn.class}  #{nn}”  #=> Bignum  9223372036854775809
nn = -nn     ; “#{nn.class}  #{nn}”  #=> Bignum  -9223372036854775809
JRuby Fixnums are always 64-bit(ish) and the rollover point reflects
that.
- Charlie
On Tue, Sep 15, 2009 at 2:08 AM, David M. [email protected]
wrote:
irb(main):009:0> (262-1).class => Fixnum
irb(main):010:0> (262).class => Bignum
irb(main):012:0> ((-2)**62-1).class => Fixnum
irb(main):013:0> ((-2)**62).class => Bignum
Fixnum seems to be a signed 63-bit integer (62 bits plus the sign bit) on
my 64-bit system.
I’m guessing that it’s actually a 31-bit signed integer on a 32-bit
system.
Fixnum/Bignum is implementation dependent?
On a Win32 Vista PC (with IRB/JIRB output cleaned up & aligned by hand):
*
Ruby 1.8.6 IRB:
n = if RUBY_PLATFORM.downcase == “java” then 63 else 30 end #=> 30
nn = 2 ** n - 1 ; “#{nn.class} #{nn}” #=> Fixnum 1073741823
nn = -nn ; “#{nn.class} #{nn}” #=> Fixnum -1073741823
nn = 2 ** n ; “#{nn.class} #{nn}” #=> Bignum 1073741824
nn = -nn ; “#{nn.class} #{nn}” #=> Fixnum -1073741824
nn = 2 ** n + 1 ; “#{nn.class} #{nn}” #=> Bignum 1073741825
nn = -nn ; “#{nn.class} #{nn}” #=> Bignum -1073741825
*
JRuby 1.3.1 JIRB:
n = if RUBY_PLATFORM.downcase == “java” then 63 else 30 end #=> 63
nn = 2 ** n - 1 ; “#{nn.class} #{nn}” #=> Fixnum 9223372036854775807
nn = -nn ; “#{nn.class} #{nn}” #=> Fixnum -9223372036854775807
nn = 2 ** n ; “#{nn.class} #{nn}” #=> Bignum 9223372036854775808
nn = -nn ; “#{nn.class} #{nn}” #=> Fixnum -9223372036854775808
nn = 2 ** n + 1 ; “#{nn.class} #{nn}” #=> Bignum 9223372036854775809
nn = -nn ; “#{nn.class} #{nn}” #=> Bignum -9223372036854775809