Skip to content

Integers never overflow: 2 ** 200 is just an Integer

Level: 101 · a Python programmer's first week in Ruby

One line: Ruby has one Integer class with no ceiling — 2 ** 200 is an ordinary value with bit_length, digits, to_s(2), Integer.sqrt, a modular pow and gcd — and the only way a big Integer loses digits is by passing through a Float; Python's int is the same, except that str() of a 5000-digit number raises unless you lift a limit.

Ruby integers are arbitrary precision, and there is no visible seam between a small one and a large one: both are the one class Integer, 2 ** 200 prints all 61 of its digits, and there is no overflow to check for. The two classes that used to expose the seam, Fixnum and Bignum, were folded into Integer in Ruby 2.4 (Not machine-checked here.), and row 3 shows that the old names are NameErrors today. What the class gives you is a toolbox built for numbers of any size: bit_length, digits, to_s(base), Integer.sqrt (exact, where Math.sqrt rounds to a Float), pow(b, m) for modular exponentiation without the huge intermediate, gcd and lcm. The one boundary that matters is the Float: a double carries 53 bits of integer, so (2 ** 53 + 1).to_f silently becomes 2 ** 53.

Verified output of integers_are_unbounded_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

 1. 2 ** 200                    -> 1606938044258990275541962092341162602522202993782792835301376 (61 digits, and no overflow)
 2. (2 ** 200).class            -> Integer                one class for every size; 1.class is Integer too
 3. Fixnum                      -> NameError: uninitialized constant Fixnum the size classes are gone; Bignum is a NameError too
 4. 255.bit_length              -> 8                      256.bit_length is 9
 5. (-1).bit_length             -> 0                      two's complement without the sign bit: (-256).bit_length is 8
 6. 1234.digits                 -> [4, 3, 2, 1]           least significant first; 255.digits(16) is [15, 15]
 7. 255.to_s(2)                 -> "11111111"             to_s(16) is "ff", to_s(36) is "73", (-255).to_s(2) is "-11111111"
 8. Integer.sqrt(10 ** 40)      -> 100000000000000000000  exact; Math.sqrt(10 ** 40) is 1.0e+20, a Float
 9. 3.pow(200, 1000)            -> 1                      modular pow, never building the 96-digit power
10. 12.gcd(18), 12.lcm(18)      -> 6, 36                  gcdlcm gives both: [6, 36]
11. 2 ** -1                     -> (1/2)                  a negative exponent gives a Rational, not a Float
12. (2 ** 53 + 1).to_f.to_i     -> 9007199254740992       the +1 is lost: a Float holds 53 bits of integer
13. (10 ** 5000).to_s.size      -> 5001                   no limit on the digits of to_s
14. (10 ** 5000).to_s(16).size  -> 4153                   nor in any other base
15. 0b1010, 0o17, 0x1f, 1_000   -> 10, 15, 31, 1000       literal forms; a leading 0 alone is octal: 017 is 15

Reading the output

Rows 1–3 are the one class. 2 ** 200 is a 61-digit Integer and its class is Integer, the same class 1 has; Fixnum is an uninitialized constant. Rows 4–7 are the bit and digit views. bit_length counts the bits needed to represent the number without its sign, so 255 needs 8 and 256 needs 9; for a negative number Ruby counts the bits of the two's-complement form without the sign bit, which is why (-1).bit_length is 0 and (-256).bit_length is 8. digits returns the digits least-significant first — digits[i] is the coefficient of base ** i — in any base; to_s(base) writes the number out in bases 2 to 36 with no prefix and a leading minus for a negative.

Rows 8–11 are the arithmetic that stays exact. Integer.sqrt(10 ** 40) is exactly 10 ** 20, where Math.sqrt answers 1.0e+20, a Float that happens to be right here and will not be for a number whose root does not fit in 53 bits. 3.pow(200, 1000) reduces modulo 1000 as it multiplies and never builds the 96-digit power. gcd, lcm and gcdlcm are methods on the Integer. Row 11 is the surprise for a Python reader: a negative exponent gives a Rational, (1/2), not 0.5 — Ruby keeps the exact answer.

Rows 12–15 are the edges. (2 ** 53 + 1).to_f.to_i comes back as 2 ** 53: the + 1 did not survive the trip through a 53-bit significand. There is no limit on to_s — a 5001-digit decimal or a 4153-digit hexadecimal prints as readily as 1 — and the literal forms are 0b, 0o and 0x, with underscores allowed as digit separators and a bare leading 0 meaning octal, so 017 is 15.

Compared with Python

Python's int is the same idea — unbounded, and one class since Python 3 dropped long — and most rows agree to the digit: bit_length, bin and hex with a prefix where to_s(2) has none, math.isqrt for the exact root, pow(3, 200, 1000) for modular exponentiation, math.gcd and math.lcm as functions rather than methods, and the same 2 ** 53 loss through a float. Three rows differ. (-1).bit_length() is 1 in Python, which counts the bits of the magnitude, where Ruby's 0 counts the two's-complement bits without the sign. 2 ** -1 is the float 0.5, not a Fraction. And Python is the language with a limit: converting an int with more than 4300 digits to or from a decimal string raises ValueError — a guard added in 3.11 against quadratic-time conversions of untrusted input (Not machine-checked here.) — and sys.set_int_max_str_digits(0) lifts it, while hexadecimal was never limited. Ruby has no such limit, in any base. Finally, a leading zero alone is a SyntaxError in Python 3, where 0o17 is the only octal form, while Ruby still reads 017 as octal.

Verified output of integers_are_unbounded_py.py — regenerated by tools/run_examples.py, never hand-typed.

 1. 2 ** 200                    -> 1606938044258990275541962092341162602522202993782792835301376 (61 digits, and no overflow)
 2. type(2 ** 200).__name__     -> int                    one class for every size; type(1).__name__ is int too
 3. long                        -> NameError              Python 2's second integer class is gone too
 4. (255).bit_length()          -> 8                      (256).bit_length() is 9
 5. (-1).bit_length()           -> 1                      bits of the magnitude: (-256).bit_length() is 9
 6. digits of 1234              -> [4, 3, 2, 1]           no digits(); go through str and reverse
 7. bin(255)                    -> '0b11111111'           prefixed; format(255, 'b') is '11111111', hex(255) is '0xff', bin(-255) is '-0b11111111'
 8. math.isqrt(10 ** 40)        -> 100000000000000000000  exact; math.sqrt(10 ** 40) is 1e+20, a float
 9. pow(3, 200, 1000)           -> 1                      modular pow, never building the 96-digit power
10. math.gcd(12, 18), lcm       -> 6, 36                  two functions; math.lcm arrived in 3.9
11. 2 ** -1                     -> 0.5                    a negative exponent gives a float, not a Fraction
12. int(float(2 ** 53 + 1))     -> 9007199254740992       the +1 is lost: a float holds 53 bits of integer
13. len(str(10 ** 5000))        -> ValueError             the 4300-digit limit on str(int)
14. len(f'{10 ** 5000:x}')      -> 4153                   hex never had the limit; after set_int_max_str_digits(0), len(str(10 ** 5000)) is 5001
15. 0b1010, 0o17, 0x1f, 1_000   -> 10, 15, 31, 1000       literal forms; a leading 0 alone is a SyntaxError

The Python library's bin() is not the bits ↗ works through why bin(-255) prints a minus sign rather than a two's-complement pattern; Ruby's (-255).to_s(2) does the same, and it is bit_length — row 5 — that shows the two's-complement view.

Try it

  1. Compute 100! with (1..100).inject(:*) and, with Integer methods only, print how many digits and bits it has, its first twelve digits, how many zeros it ends in, whether Integer.sqrt of it is the exact floor of the root (root ** 2 <= f and (root + 1) ** 2 > f), and what a round trip through to_f does to it. Then compute 100! % 1_000_007 twice: once from the full product and once reducing at every step.
  2. Write to_binary(n) that builds what n.to_s(2) returns from n.abs.digits(2) and a sign, and check it against to_s(2) for 0, 5, 255, 2 ** 70 and -6. Then compare n.bit_length with to_binary(n).size for the positive cases, and explain from row 5 why the negative case is different.
Solution to 1

integers_are_unbounded_kata_rb.rb in full — pasted here by tools/run_examples.py from the file CI runs.

# Kata: 100! with nothing but Integer — count its digits and bits, find its
# trailing zeros, check Integer.sqrt against the exact square, and see what
# a trip through Float costs.

f = (1..100).inject(:*)
puts "1. 100! has #{f.to_s.size} digits and #{f.bit_length} bits"
puts "2. it starts #{f.to_s[0, 12]}... and ends in #{f.digits.take_while(&:zero?).size} zeros"
root = Integer.sqrt(f)
puts "3. Integer.sqrt(100!) has #{root.to_s.size} digits; root ** 2 <= 100! is #{root**2 <= f}, (root + 1) ** 2 > 100! is #{(root + 1)**2 > f}"
puts "4. 100! as a Float is #{f.to_f}; f.to_f.to_i == f is #{f.to_f.to_i == f}"
puts "5. 100! % 1_000_007 is #{f % 1_000_007}, and (1..100).inject(1) { |acc, i| acc * i % 1_000_007 } is #{(1..100).inject(1) { |acc, i| acc * i % 1_000_007 }}"

Verified output of integers_are_unbounded_kata_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

1. 100! has 158 digits and 525 bits
2. it starts 933262154439... and ends in 24 zeros
3. Integer.sqrt(100!) has 79 digits; root ** 2 <= 100! is true, (root + 1) ** 2 > 100! is true
4. 100! as a Float is 9.332621544394415e+157; f.to_f.to_i == f is false
5. 100! % 1_000_007 is 323756, and (1..100).inject(1) { |acc, i| acc * i % 1_000_007 } is 323756

See also