Ответ 1
TL; DR
Я сделал вычисления, выполненные внутри numeric.c int_pow вручную, проверяя, где происходит переполнение целых чисел (и распространение в Bignum's, включая вызов rb_big_pow). После вызова rb_big_pow происходит проверка того, являются ли два промежуточных значения у вас в int_pow слишком большими или нет, а значение отсечки составляет около 9942066 (если вы используете базу 10 для мощности). Примерно это значение близко к
BIGLEN_LIMIT / ceil(log2(base^n)) * n ==
32*1024*1024 / ceil(log2(10^16)) * 16 ==
32*1024*1024 / 54 * 16 ~=
9942054
где BIGLEN_LIMIT - внутренний предел в рубине, который используется как константа, чтобы проверить, будет ли вычисление мощности слишком большим или нет, и определяется как 32*1024*1024. base равно 10, а n - наибольшая степень степени 2 для основания, которая по-прежнему будет помещаться внутри Fixnum.
К сожалению, я не могу найти лучшего способа, чем это приближение, из-за алгоритма, используемого для вычисления полномочий больших чисел, но он может быть достаточно хорош, чтобы использовать его как верхний предел, если ваш код должен проверить правильность, прежде чем делать возведение в степень на большие числа.
Оригинальный вопрос:
Проблема заключается не в 9942066, а в том, что одно из ваших чисел является целым числом, а другое - плавающим. Так
(10**9942066).class # => Bignum
(10**9942066.00000001).class # => Float
Первый представляет собой внутреннее число, которое меньше, чем Infinity. Второй, поскольку он по-прежнему является float, не представляется реальным числом и просто заменяется на Infinity, который, конечно, не больше, чем Infinity.
Обновленный вопрос:
Вы правы, что, похоже, есть какая-то разница около 9942066 (если вы используете 64-разрядный рубин под Linux, поскольку в других системах ограничения могут отличаться). Хотя Ruby действительно использует библиотеку GMP для обработки больших чисел, он делает некоторые предварительные проверки перед тем, как даже перейти на GMP, как показано предупреждениями, которые вы можете получить. Он также будет выполнять возведение в степень вручную с помощью команд GMP mul, не вызывая функции GMP pow.
К счастью, предупреждения легко поймать:
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
И тогда вы можете проверить, где эти предупреждения испускаются внутри библиотеки ruby bignum.c.
Но сначала нам нужно добраться до области Bignum, так как оба наших числа являются простыми Fixnums. Начальная часть вычисления и "обновление" от fixnum до bignum выполняется внутри numeric.c. Ruby делает быстрое возведение в степень и на каждом шаге проверяет, будет ли результат по-прежнему вписываться в Fixnum (что на 2 бита меньше, чем в битах системы: 62 бит на 64-битной машине). Если нет, он затем преобразует значения в область Bignum и продолжит вычисления там. Мы заинтересованы в том, что такое преобразование происходит, поэтому постарайтесь выяснить, когда это происходит в нашем примере 10^9942066 (я использую переменные x, y, z, присутствующие внутри кода ruby numeric.c):
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
В этот момент x будет переполняться (10^32 > 2^62-1), поэтому процесс будет продолжаться в области Bignum, вычисляя x**y, который равен (10^16)^621378 (которые на самом деле остаются обе Fixnums на этом этапе)
Если вы вернетесь к bignum.c и проверьте, как он определяет, является ли число слишком большим или нет, вы можете видеть, что это проверит количество бит, необходимое для хранения x, и умножьте это число на y. Если результат больше, чем 32*1024*1024, он будет терпеть неудачу (выдает предупреждение и выполняет вычисления с использованием базовых поплавков).
(10^16) - 54 бит (ceil(log_2(10^16)) == 54), 54*621378 - 33554412. Это только немного меньше 33554432 (на 20), предел, после которого рубин не будет выполнять возложение Bignum, а просто преобразует y удвоить и надеяться на лучшее (что, очевидно, не удастся и просто вернет Infinity)
Теперь попробуйте проверить это с помощью 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
Здесь, в точке z переполнения (10^19 > 2^62-1), вычисление продолжится в области Bignum и рассчитает x**y. Обратите внимание, что здесь он будет вычислять (10^16)^621379, и пока (10^16) все еще 54 бит, 54*621379 равен 33554466, что больше 33554432 (на 34). Чем больше вы получите предупреждение, а рубин будет только для вычислений с использованием double, поэтому результат будет Infinity.
Обратите внимание, что эти проверки выполняются только в том случае, если вы используете функцию питания. Вот почему вы все еще можете сделать (10**9942066)*10, поскольку аналогичные проверки отсутствуют при выполнении простого умножения, то есть вы можете реализовать свой собственный метод быстрой экспоненции в рубине, и в этом случае он будет по-прежнему работать с более крупными значениями, хотя у вас не будет это проверка безопасности больше. См., Например, эту быструю реализацию:
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
Но как я могу узнать обрезание для конкретной базы?
Моя математика не очень велика, но я могу сказать способ приблизиться к тому, где будет значение отсечки. Если вы проверите вышеуказанные вызовы, вы увидите, что преобразование между Fixnum и Bignum происходит, когда промежуточная база достигает предела Fixnum. Промежуточная база на этом этапе всегда будет иметь показатель степени 2, поэтому вам просто нужно максимизировать это значение. Например, попробуйте выяснить максимальное значение отсечки для 12.
Сначала мы должны проверить, какая самая высокая база, которую мы можем сохранить в 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
Мы можем видеть, что 12^16 - это максимум, который мы можем сохранить в 62 битах, или если мы используем 32-битную машину 12^8, вписывается в 30 бит (ruby Fixnums может хранить значения до двух бит меньше, чем ограничение размера машины).
Для 12^16 мы можем легко определить значение отсечки. Он будет 32*1024*1024 / ceil(log2(12^16)), который равен 33554432 / 58 ~= 578525. Теперь мы можем легко проверить это в рубине:
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
Теперь нам не хочется возвращаться к исходной базе 12. Там срез будет вокруг 578525*16 (16 - показатель новой базы), который равен 9256400. Если вы проверите рубин, значения на самом деле довольно близки к этому числу:
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