Неожиданные результаты при работе с очень большими целыми числами на интерпретируемых языках

Python работает:

 >>> sum(x for x in xrange(1000000000 + 1)) 500000000500000000 

Или:

 >>> sum(xrange(1000000000+1)) 500000000500000000 

int auto Python продвигается до Python long который поддерживает произвольную точность. Он даст правильный ответ на 32 или 64-битных платформах.

Это можно увидеть, подняв 2 до мощности, намного превышающей ширину бита платформы:

 >>> 2**99 633825300114114700748351602688L 

Вы можете продемонстрировать (с Python), что ошибочные значения, которые вы получаете в PHP, – это то, что PHP продвигает к float, когда значения больше, чем 2 ** 32-1:

 >>> int(sum(float(x) for x in xrange(1000000000+1))) 500000000067108992 

Ваш код Go использует целочисленную арифметику с достаточным количеством битов, чтобы дать точный ответ. Никогда не касался PHP или Node.js, но из результатов, которые я подозреваю, математика выполняется с использованием чисел с плавающей запятой и поэтому должна быть неточна для чисел этой величины.

Причина в том, что значение вашей целочисленной переменной sum превышает максимальное значение. И sum вы получаете, является результатом арифметики с плавающей точкой, которая включает округление. Поскольку в других ответах не упоминались точные пределы, я решил опубликовать их.

Максимальное целочисленное значение для PHP для:

• 32-разрядная версия – 2147483647
• 64-разрядная версия – 9223372036854775807

Таким образом, это означает, что вы используете 32-битную ЦП или 32-битную ОС или 32-битную скомпилированную версию PHP. Его можно найти с помощью PHP_INT_MAX . sum будет правильно рассчитана, если вы сделаете это на 64-битной машине.

Максимальное целочисленное значение в JavaScript составляет 9007199254740992 . Наибольшее точное целочисленное значение, с которым вы можете работать, составляет 2 ⁵³ (взято из этого вопроса ). sum превышает этот предел.

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

Вот ответ на C, для полноты:

 #include <stdio.h> int main(void) { unsigned long long sum = 0, i; for (i = 0; i <= 1000000000; i++) //one billion sum += i; printf("%llu\n", sum); //500000000500000000 return 0; } 

Ключ в этом случае использует long long тип данных C99 . Он обеспечивает самое большое примитивное хранилище C, которое может работать и работает очень быстро. long long тип также будет работать на большинстве 32 или 64-битных машин.

Существует одно предостережение: компиляторы, предоставленные Microsoft, явно не поддерживают 14-летний стандарт C99, поэтому его запуск в Visual Studio – это crapshot.

Я предполагаю, что когда сумма превышает емкость собственного int (2 ³² -1 = 2,147,483,647), Node.js и PHP переключаются на представление с плавающей запятой, и вы начинаете получать ошибки округления. Язык, подобный Go, вероятно, будет пытаться придерживаться целочисленной формы (например, 64-битных целых чисел) до тех пор, пока это возможно (если это не началось с этого). Поскольку ответ соответствует 64-битовому целому числу, вычисление является точным.

Perl-скрипт дает нам ожидаемый результат:

 use warnings; use strict; my $sum = 0; for(my $i = 0; $i <= 1_000_000_000; $i++) { $sum += $i; } print $sum, "\n"; #<-- prints: 500000000500000000 

Ответ на это «удивительно» прост:

Во-первых – как известно большинству из вас – 32-битное целое число варьируется от -2,147,483,648 до 2,147,483,647 . Итак, что произойдет, если PHP получит результат, то есть LARGER, чем это?

Обычно можно ожидать немедленного «переполнения», в результате чего 2,147,483,647 + 1 превратится в -2,147,483,648 . Однако это не так. Если PHP встречает большее число, он возвращает FLOAT вместо INT.

Если PHP встречает число за пределами целочисленного типа, оно будет интерпретироваться как float. Кроме того, операция, которая приводит к числу за пределами целочисленного типа, вместо этого возвращает float.

http://php.net/manual/en/language.types.integer.php

Это говорит о том, что реализация PHP FLOAT соответствует формату двойной точности IEEE 754, означает, что PHP способен обрабатывать цифры до 52 бит без потери точности. (В 32-разрядной системе)

Итак, в точке, где ваша сумма достигает 9,007,199,254,740,992 (что составляет 2 ^ 53 ) Значение Float, возвращаемое PHP Maths, больше не будет достаточно точным.

 E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000000\"); echo number_format($x,0);" 

9.007.199.254.740.992

 E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000001\"); echo number_format($x,0);" 

9.007.199.254.740.992

 E:\PHP>php -r "$x=bindec(\"100000000000000000000000000000000000000000000000000010\"); echo number_format($x,0);" 

9.007.199.254.740.994

Этот пример показывает точку, где PHP теряет точность. Во-первых, последний бит синтаксиса будет отброшен, в результате чего первые 2 выражения приведут к равному числу, а это не так.

Начиная с версии NOW, вся математика будет ошибаться при работе с типами данных по умолчанию.

• Является ли такая же проблема для других интерпретируемых языков, таких как Python или Perl?

Я так не думаю. Я думаю, что это проблема языков, которые не имеют безопасности типа. В то время как Integer Overflow, как упоминалось выше, произойдет на всех языках, использующих фиксированные типы данных, языки без безопасности типов могут попытаться поймать это с другими типами данных. Однако, как только они попадают в их «естественную» (System-given) Border – они могут что-то вернуть, но правильный результат.

Однако для такого сценария на каждом языке могут быть разные потоки.

Другие ответы уже объяснили, что здесь происходит (точность с плавающей запятой, как обычно).

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

Другое решение – использовать алгоритм суммирования, который знает о проблеме точности и работает вокруг него. Ниже вы найдете такое же суммирование, сначала с 64-битным целым числом, затем с 64-битной плавающей точкой, а затем с использованием с плавающей запятой снова, но с алгоритмом суммирования Кахана .

Написано на C #, но то же самое относится и к другим языкам.

 long sum1 = 0; for (int i = 0; i <= 1000000000; i++) { sum1 += i ; } Console.WriteLine(sum1.ToString("N0")); // 500.000.000.500.000.000 double sum2 = 0; for (int i = 0; i <= 1000000000; i++) { sum2 += i ; } Console.WriteLine(sum2.ToString("N0")); // 500.000.000.067.109.000 double sum3 = 0; double error = 0; for (int i = 0; i <= 1000000000; i++) { double corrected = i - error; double temp = sum3 + corrected; error = (temp - sum3) - corrected; sum3 = temp; } Console.WriteLine(sum3.ToString("N0")); //500.000.000.500.000.000 

Сводка Кахана дает прекрасный результат. Конечно, для вычисления требуется намного больше времени. Независимо от того, хотите ли вы использовать его, зависит а) от вашей производительности и точности, и б) как ваш язык обрабатывает целые числа или типы данных с плавающей точкой.

Если у вас 32-битный PHP, вы можете вычислить его с помощью bc :

 <?php $value = 1000000000; echo bcdiv( bcmul( $value, $value + 1 ), 2 ); //500000000500000000 

В Javascript вам нужно использовать произвольную библиотеку чисел, например BigInteger :

 var value = new BigInteger(1000000000); console.log( value.multiply(value.add(1)).divide(2).toString()); //500000000500000000 

Даже с такими языками, как Go и Java, вам в конечном итоге придется использовать произвольную библиотеку чисел, ваш номер просто оказался достаточно маленьким для 64-битного, но слишком высокого для 32-битного.

В Ruby:

 sum = 0 1.upto(1000000000).each{|i| sum += i } puts sum 

Печатает 500000000500000000 , но занимает 4 минуты на моем 2,6 ГГц Intel i7.

У Magnuss и Jaunty гораздо больше решений Ruby:

 1.upto(1000000000).inject(:+) 

Для запуска теста:

 $ time ruby -e "puts 1.upto(1000000000).inject(:+)" ruby -e "1.upto(1000000000).inject(:+)" 128.75s user 0.07s system 99% cpu 2:08.84 total 

Я использую node-bigint для больших целых вещей:
https://github.com/substack/node-bigint

 var bigint = require('bigint'); var sum = bigint(0); for(var i = 0; i <= 1000000000; i++) { sum = sum.add(i); } console.log(sum); 

Это не так быстро, как то, что может использовать собственный 64-разрядный материал для этого точного теста, но если вы попадаете в большее число, чем в 64-битный, он использует libgmp под капотом, который является одной из более быстрых библиотек с произвольной точностью.

взял возраст в рубине, но дает правильный ответ:

 (1..1000000000).reduce(:+) => 500000000500000000 

Чтобы получить правильный результат в php, я думаю, вам нужно будет использовать операторов математики BC: http://php.net/manual/en/ref.bc.php

Вот правильный ответ в Scala. Вы должны использовать Longs, иначе вы переполняете число:

 println((1L to 1000000000L).reduce(_ + _)) // prints 500000000500000000 

На самом деле это крутой трюк.

Предположим, что это было 1-100.

1 + 2 + 3 + 4 + … + 50 +

100 + 99 + 98 + 97 + … + 51

= (101 + 101 + 101 + 101 + … + 101) = 101 * 50

Формула:

Для N = 100: Выход = N / 2 * (N + 1)

Для N = 1e9: Выход = N / 2 * (N + 1)

Это намного быстрее, чем перебирать все эти данные. Ваш процессор поблагодарит вас за это. И вот интересная история по этой самой проблеме:

http://www.jimloy.com/algebra/gauss.htm

Common Lisp является одним из самых быстрых интерпретируемых языков и по умолчанию обрабатывает произвольно большие целые числа. Это занимает около 3 секунд с SBCL :

 * (time (let ((sum 0)) (loop :for x :from 1 :to 1000000000 :do (incf sum x)) sum)) Evaluation took: 3.068 seconds of real time 3.064000 seconds of total run time (3.044000 user, 0.020000 system) 99.87% CPU 8,572,036,182 processor cycles 0 bytes consed 500000000500000000 

• По интерпретации, я имею в виду, я запустил этот код из REPL, SBCL, возможно, сделал JITing внутри, чтобы заставить его работать быстро, но динамический опыт запуска кода сразу же.

У меня недостаточно репутации, чтобы комментировать ответ на обычный ответ Lisp @ postfuturist, но он может быть оптимизирован для завершения в ~ 500 мс с SBCL 1.1.8 на моей машине:

 CL-USER> (compile nil '(lambda () (declare (optimize (speed 3) (space 0) (safety 0) (debug 0) (compilation-speed 0))) (let ((sum 0)) (declare (type fixnum sum)) (loop for i from 1 to 1000000000 do (incf sum i)) sum))) #<FUNCTION (LAMBDA ()) {1004B93CCB}> NIL NIL CL-USER> (time (funcall *)) Evaluation took: 0.531 seconds of real time 0.531250 seconds of total run time (0.531250 user, 0.000000 system) 100.00% CPU 1,912,655,483 processor cycles 0 bytes consed 500000000500000000 

Категория другой язык:

Tcl:

Если использовать Tcl 8.4 или старше, это зависит от того, была ли она скомпилирована с 32 или 64 бит. (8.4 – конец жизни).

Если вы используете Tcl 8.5 или новее с произвольными большими целыми числами, он отобразит правильный результат.

 proc test limit { for {set i 0} {$i < $limit} {incr i} { incr result $i } return $result } test 1000000000 

Я положил тест внутри proc, чтобы получить его байт-скомпилированный.

Это дает правильный результат в PHP, заставляя целочисленное преобразование.

 $sum = (int) $sum + $i; 

Racket v 5.3.4 (MBP; время в мс):

 > (time (for/sum ([x (in-range 1000000001)]) x)) cpu time: 2943 real time: 2954 gc time: 0 500000000500000000 

Эрланг также дает ожидаемый результат.

sum.erl:

 -module(sum). -export([iter_sum/2]). iter_sum(Begin, End) -> iter_sum(Begin,End,0). iter_sum(Current, End, Sum) when Current > End -> Sum; iter_sum(Current, End, Sum) -> iter_sum(Current+1,End,Sum+Current). 

И используя его:

 1> c(sum). {ok,sum} 2> sum:iter_sum(1,1000000000). 500000000500000000 

Прекрасно работает в Rebol:

 >> sum: 0 == 0 >> repeat i 1000000000 [sum: sum + i] == 500000000500000000 >> type? sum == integer! 

Это использовало Rebol 3, который, несмотря на 32-битную компиляцию, использует 64-битные целые числа (в отличие от Rebol 2, в котором используются 32-битные целые числа)

Я хотел посмотреть, что произошло в CF Script

 <cfscript> ttl = 0; for (i=0;i LTE 1000000000 ;i=i+1) { ttl += i; } writeDump(ttl); abort; </cfscript> 

Я получил 5.00000000067E + 017

Это был довольно опрятный эксперимент. Я вполне уверен, что мог бы лучше закодировать это с большим усилием.

ActivePerl v5.10.1 на 32-битных окнах, intel core2duo 2.6:

 $sum = 0; for ($i = 0; $i <= 1000000000 ; $i++) { $sum += $i; } print $sum."\n"; 

результат: 5.00000000067109e + 017 через 5 минут.

С скриптом «use bigint» работал в течение двух часов и работал больше, но я его остановил. Слишком медленно.

Болтовня:

 (1 to: 1000000000) inject: 0 into: [:subTotal :next | subTotal + next ]. "500000000500000000" 

Для полноты, в Clojure (красивый, но не очень эффективный):

 (reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000 

AWK:

 BEGIN { s = 0; for (i = 1; i <= 1000000000; i++) s += i; print s } 

дает тот же неправильный результат, что и PHP:

 500000000067108992 

Кажется, AWK использует плавающие точки, когда числа действительно большие, поэтому, по крайней мере, ответ – правильный порядок величины.

Тесты:

 $ awk 'BEGIN { s = 0; for (i = 1; i <= 100000000; i++) s += i; print s }' 5000000050000000 $ awk 'BEGIN { s = 0; for (i = 1; i <= 1000000000; i++) s += i; print s }' 500000000067108992 

Для кода PHP ответ здесь :

Размер целого зависит от платформы, хотя максимальное значение около двух миллиардов – это обычное значение (это 32 бита). Обычно 64-битные платформы имеют максимальное значение около 9E18. PHP не поддерживает целые числа без знака. Целочисленный размер может быть определен с использованием константы PHP_INT_SIZE и максимального значения с использованием константы PHP_INT_MAX с PHP 4.4.0 и PHP 5.0.5.

порт:

 proc Main() local sum := 0, i for i := 0 to 1000000000 sum += i next ? sum return 

Результаты в 500000000500000000 . (на обоих окнах / mingw / x86 и osx / clang / x64)

Эрланг работает:

 from_sum(From,Max) -> from_sum(From,Max,Max). from_sum(From,Max,Sum) when From =:= Max -> Sum; from_sum(From,Max,Sum) when From =/= Max -> from_sum(From+1,Max,Sum+From). 

Результаты: 41> бесполезно: from_sum (1,1000000000). 500000000500000000

Смешная вещь, PHP 5.5.1 дает 499999999500000000 (в ~ 30 секунд), а Dart2Js дает 500000000067109000 (что и следовало ожидать, так как это JS, который выполняется). CLI Dart дает правильный ответ … мгновенно.