Why is 10^9942066 the biggest power I can calculate without overflows?

Question

In ruby, some large numbers are larger than infinity. Through binary search, I discovered:

(1.0/0) > 10**9942066.000000001 # => false
(1.0/0) > 10**9942066 # => true
RUBY_VERSION # => "2.3.0"

Why is this? What is special about 10^9942066? It doesn't seem to be an arbitrary number like 9999999, it is not close to any power of two (it's approximately equivelent to 2^{33026828.36662442}).

Why isn't ruby's infinity infinite? How is 10^9942066 involved?

---

I now realize, any number greater than 10^9942066 will overflow to infinity:

10**9942066.000000001 #=> Infinity
10**9942067 #=> Infinity

But that still leaves the question: Why 10^9942066?

Answer 1

TL;DR

I did the calculations done inside numeric.c's int_pow manually, checking where an integer overflow (and a propagation to Bignum's, including a call to rb_big_pow) occurs. Once the call to rb_big_pow happens there is a check whether the two intermediate values you've got in int_pow are too large or not, and the cutoff value seems to be just around 9942066 (if you're using a base of 10 for the power). Approximately this value is close to

BIGLEN_LIMIT / ceil(log2(base^n)) * n ==
32*1024*1024 / ceil(log2(10^16)) * 16 ==
32*1024*1024 / 54 * 16 ~=
9942054

where BIGLEN_LIMIT is an internal limit in ruby which is used as a constant to check if a power calculation would be too big or not, and is defined as 32*1024*1024. base is 10, and n is the largest power-of-2 exponent for the base that would still fit inside a Fixnum.

Unfortunately I can't find a better way than this approximation, due to the algorithm used to calculate powers of big numbers, but it might be good enough to use as an upper limit if your code needs to check validity before doing exponentiation on big numbers.

---

Original question:

The problem is not with 9942066, but that with one of your number being an integer, the other one being a float. So

(10**9942066).class # => Bignum
(10**9942066.00000001).class # => Float

The first one is representable by a specific number internally, which is smaller than Infinity. The second one, as it's still a float is not representable by an actual number, and is simply replaced by Infinity, which is of course not larger than Infinity.

Updated question:

You are right that there seem to be some difference around 9942066 (if you're using a 64-bit ruby under Linux, as the limits might be different under other systems). While ruby does use the GMP library to handle big numbers, it does some precheck before even going to GMP, as shown by the warnings you can receive. It will also do the exponentiation manually using GMP's mul commands, without calling GMP's pow functions.

Fortunately the warnings are easy to catch:

irb(main):010:0> (10**9942066).class
=> Bignum

irb(main):005:0> (10**9942067).class
(irb):5: warning: in a**b, b may be too big
=> Float

And then you can actually check where these warnings are emitted inside ruby's bignum.c library.

But first we need to get to the Bignum realm, as both of our numbers are simple Fixnums. The initial part of the calculation, and the "upgrade" from fixnum to bignum is done inside numeric.c. Ruby does quick exponentiation, and at every step it checks whether the result would still fit into a Fixnum (which is 2 bits less than the system bitsize: 62 bits on a 64 bit machine). If not, it will then convert the values to the Bignum realm, and continues the calculations there. We are interested at the point where this conversion happens, so let's try to figure out when it does in our 10^9942066 example (I'm using x,y,z variables as present inside the ruby's numeric.c code):

x = 10^1  z = 10^0   y = 9942066
x = 10^2  z = 10^0   y = 4971033
x = 10^2  z = 10^2   y = 4971032
x = 10^4  z = 10^2   y = 2485516
x = 10^8  z = 10^2   y = 1242758
x = 10^16 z = 10^2   y = 621379
x = 10^16 z = 10^18  y = 621378
x = OWFL

At this point x will overflow (10^32 > 2^62-1), so the process will continue on the Bignum realm by calculating x**y, which is (10^16)^621378 (which are actually still both Fixnums at this stage)

If you now go back to bignum.c and check how it determines if a number is too large or not, you can see that it will check the number of bits required to hold x, and multiply this number with y. If the result is larger than 32*1024*1024, it will then fail (emit a warning and does the calculations using basic floats).

(10^16) is 54 bits (ceil(log_2(10^16)) == 54), 54*621378 is 33554412. This is only slightly smaller than 33554432 (by 20), the limit after which ruby will not do Bignum exponentiation, but simply convert y to double, and hope for the best (which will obviously fail, and just return Infinity)

Now let's try to check this with 9942067:

x = 10^1   z = 10^0    y = 9942067
x = 10^1   z = 10^1    y = 9942066
x = 10^2   z = 10^1    y = 4971033
x = 10^2   z = 10^3    y = 4971032
x = 10^4   z = 10^3    y = 2485516
x = 10^8   z = 10^3    y = 1242758
x = 10^16  z = 10^3    y = 621379
x = 10^16  z = OWFL

Here, at the point z overflows (10^19 > 2^62-1), the calculation will continue on the Bignum realm, and will calculate x**y. Note that here it will calculate (10^16)^621379, and while (10^16) is still 54 bits, 54*621379 is 33554466, which is larger than 33554432 (by 34). As it's larger you'll get the warning, and ruby will only to calculations using double, hence the result is Infinity.

Note that these checks are only done if you are using the power function. That's why you can still do (10**9942066)*10, as similar checks are not present when doing plain multiplication, meaning you could implement your own quick exponentiation method in ruby, in which case it will still work with larger values, although you won't have this safety check anymore. See for example this quick implementation:

def unbounded_pow(x,n)
  if n < 0
    x = 1.0 / x
    n = -n
  end
  return 1 if n == 0
  y = 1
  while n > 1
    if n.even?
      x = x*x
      n = n/2
    else
      y = x*y
      x = x*x
      n = (n-1)/2
    end
  end
  x*y
end

puts (10**9942066) == (unbounded_pow(10,9942066)) # => true
puts (10**9942067) == (unbounded_pow(10,9942067)) # => false 
puts ((10**9942066)*10) == (unbounded_pow(10,9942067)) # => true

But how would I know the cutoff for a specific base?

My math is not exactly great, but I can tell a way to approximate where the cutoff value will be. If you check the above calls you can see the conversion between Fixnum and Bignum happens when the intermediate base reaches the limit of Fixnum. The intermediate base at this stage will always have an exponent which is a power of 2, so you just have to maximize this value. For example let's try to figure out the maximum cutoff value for 12.

First we have to check what is the highest base we can store in a Fixnum:

ceil(log2(12^1)) = 4
ceil(log2(12^2)) = 8
ceil(log2(12^4)) = 15
ceil(log2(12^8)) = 29
ceil(log2(12^16)) = 58
ceil(log2(12^32)) = 115

We can see 12^16 is the max we can store in 62 bits, or if we're using a 32 bit machine 12^8 will fit into 30 bits (ruby's Fixnums can store values up to two bits less than the machine size limit).

For 12^16 we can easily determine the cutoff value. It will be 32*1024*1024 / ceil(log2(12^16)), which is 33554432 / 58 ~= 578525. We can easily check this in ruby now:

irb(main):004:0> ((12**16)**578525).class
=> Bignum
irb(main):005:0> ((12**16)**578526).class
(irb):5: warning: in a**b, b may be too big
=> Float

Now we hate to go back to our original base of 12. There the cutoff will be around 578525*16 (16 being the exponent of the new base), which is 9256400. If you check in ruby, the values are actually quite close to this number:

irb(main):009:0> (12**9256401).class
=> Bignum
irb(main):010:0> (12**9256402).class
(irb):10: warning: in a**b, b may be too big
=> Float

Answer 2

Note that the problem is not with the number but with the operation, as told by the warning you get.

$ ruby -e 'puts (1.0/0) > 10**9942067'
-e:1: warning: in a**b, b may be too big
false

The problem is 10**9942067 breaks Ruby's power function. Instead of throwing an exception, which would be a better behavior, it erroneously results in infinity.

$ ruby -e 'puts 10**9942067'
-e:1: warning: in a**b, b may be too big
Infinity

The other answer explains why this happens near 10e9942067.

10**9942067 is not greater than infinity, it is erroneously resulting in infinity. This is a bad habit of a lot of math libraries that makes mathematicians claw their eyeballs out in frustration.

Infinity is not greater than infinity, they're equal, so your greater than check is false. You can see this by checking if they're equal.

$ ruby -e 'puts (1.0/0) == 10**9942067'
-e:1: warning: in a**b, b may be too big
true

Contrast this with specifying the number directly using scientific notation. Now Ruby doesn't have to do math on huge numbers, it just knows that any real number is less than infinity.

$ ruby -e 'puts (1.0/0) > 10e9942067'
false

Now you can put on as big an exponent as you like.

$ ruby -e 'puts (1.0/0) > 10e994206700000000000000000000000000000000'
false