Почему 10 ^ 9942066 самая большая сила, которую я могу вычислить без переполнения?

Ответ 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

Ответ 2

Обратите внимание, что проблема связана не с номером, а с операцией, как сказано в предупреждении, которое вы получаете.

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

Проблема 10**9942067 прерывает функцию мощности Ruby. Вместо того, чтобы бросать исключение, которое было бы лучше, оно ошибочно приводит к бесконечности.

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

Другой ответ объясняет, почему это происходит около 10e9942067.

10**9942067 не больше бесконечности, он ошибочно приводит к бесконечности. Это плохая привычка к множеству математических библиотек, которые заставляют математиков вырвать свои глазные ящики из-за разочарования.

Бесконечность не больше бесконечности, они равны, поэтому ваш больше, чем чек, является ложным. Вы можете видеть это, проверяя, равны ли они.

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

Сравните это с указанием номера непосредственно с помощью научной нотации. Теперь Ruby не нужно делать математику на огромных количествах, он просто знает, что любое реальное число меньше бесконечности.

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

Теперь вы можете наложить как большой показатель, как вам нравится.

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