Overflow behavior

J

Joel VanderWerf

jacob said:
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
 
S

Seebs

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

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
 
M

Markus Roberts

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
 
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)?

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
 
S

Seebs

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
 
D

David Masover

Integers overflow from Fixnums (30 bits) into Bignums (unlimited
precision integers).

Not entirely accurate, apparently:

irb(main):009:0> (2**62-1).class
=> Fixnum
irb(main):010:0> (2**62).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> (2**1023).to_f
=> 8.98846567431158e+307
irb(main):034:0> 2**1024
=>
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.
 
C

Colin Bartlett

[Note: parts of this message were removed to make it a legal post.]

irb(main):009:0> (2**62-1).class => Fixnum
irb(main):010:0> (2**62).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
 
C

Charles Oliver Nutter

JRuby 1.3.1 JIRB:
n =3D if RUBY_PLATFORM.downcase =3D=3D "java" then 63 else 30 end =C2=A0#= =3D> 63
nn =3D 2 ** n - 1 ; "#{nn.class} =C2=A0#{nn}" =C2=A0#=3D> Fixnum =C2=A0 9= 223372036854775807
nn =3D -nn =C2=A0 =C2=A0 =C2=A0 =C2=A0; "#{nn.class} =C2=A0#{nn}" =C2=A0#=
=3D> Fixnum =C2=A0-9223372036854775807
nn =3D 2 ** n =C2=A0 =C2=A0 ; "#{nn.class} =C2=A0#{nn}" =C2=A0#=3D> Bignu= m =C2=A0 9223372036854775808
nn =3D -nn =C2=A0 =C2=A0 =C2=A0 =C2=A0; "#{nn.class} =C2=A0#{nn}" =C2=A0#=
=3D> Fixnum =C2=A0-9223372036854775808
nn =3D 2 ** n + 1 ; "#{nn.class} =C2=A0#{nn}" =C2=A0#=3D> Bignum =C2=A0 9= 223372036854775809
nn =3D -nn =C2=A0 =C2=A0 =C2=A0 =C2=A0; "#{nn.class} =C2=A0#{nn}" =C2=A0#=
=3D> Bignum =C2=A0-9223372036854775809

JRuby Fixnums are always 64-bit(ish) and the rollover point reflects that.

- Charlie
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,167
Messages
2,570,910
Members
47,453
Latest member
MadelinePh

Latest Threads

Top