Неожиданные результаты при работе с очень большими целыми числами на интерпретируемых языках
Я пытаюсь получить сумму 1 + 2 + ... + 1000000000, но я получаю забавные результаты в PHP и Node.js.
PHP
$sum = 0;
for($i = 0; $i <= 1000000000 ; $i++) {
$sum += $i;
}
printf("%s", number_format($sum, 0, "", "")); // 500000000067108992
Node.js
var sum = 0;
for (i = 0; i <= 1000000000; i++) {
sum += i ;
}
console.log(sum); // 500000000067109000
Правильный ответ можно рассчитать, используя
1 + 2 + ... + n = n(n+1)/2
Правильный ответ = 500000000500000000, поэтому я решил попробовать другой язык.
ИДТИ
var sum , i int64
for i = 0 ; i <= 1000000000; i++ {
sum += i
}
fmt.Println(sum) // 500000000500000000
Но это работает отлично! Так что же не так с моим кодом PHP и Node.js?
Возможно, это проблема интерпретируемых языков, и поэтому она работает на скомпилированном языке, таком как Go? Если да, будут ли другие интерпретируемые языки, такие как Python и Perl, иметь такую же проблему?
36 ответов
Python работает:
>>> sum(x for x in xrange(1000000000 + 1))
500000000500000000
Или же:
>>> sum(xrange(1000000000+1))
500000000500000000
Питона int авто продвигается к питону long который поддерживает произвольную точность. Он даст правильный ответ на 32 или 64-битных платформах.
Это можно увидеть, подняв 2 до степени, намного превышающей ширину в битах платформы:
>>> 2**99
633825300114114700748351602688L
Вы можете продемонстрировать (с помощью Python), что ошибочные значения, которые вы получаете в PHP, объясняются тем, что PHP переводит в плавающее число, когда значения больше 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. Наибольшее точное целое значение, с которым вы можете работать, составляет 253 (взято из этого вопроса). 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;
}
Ключ в этом случае использует C99 long long тип данных. Он предоставляет самое большое примитивное хранилище, с которым может работать C, и работает он действительно очень быстро. long long Тип также будет работать на большинстве любых 32 или 64-битных машин.
Есть одно предостережение: компиляторы, предоставляемые Microsoft, явно не поддерживают 14-летний стандарт C99, поэтому запуск его в Visual Studio - непростая задача.
Я предполагаю, что когда сумма превышает возможности туземца int (232-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 получит результат, который БОЛЬШЕ, чем этот?
Обычно можно ожидать немедленного "переполнения", в результате которого 2 147 483 647 + 1 превратится в -2 147 483 648. Тем не менее, это не так. Если PHP встречает большее число, он возвращает FLOAT вместо INT.
Если PHP встречает число за пределами целочисленного типа, оно будет интерпретироваться как число с плавающей точкой. Кроме того, операция, результатом которой является число, выходящее за пределы целочисленного типа, вместо этого вернет число с плавающей запятой.
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 теряет точность. Во-первых, последний значащий бит будет сброшен, в результате чего первые два выражения приведут к равному числу, а это не так.
С этого момента вся математика будет работать неправильно при работе с типами данных по умолчанию.
• Это та же проблема для другого интерпретируемого языка, такого как Python или Perl?
Я так не думаю. Я думаю, что это проблема языков, которые не имеют безопасности типов. В то время как целочисленное переполнение, как упомянуто выше, будет происходить на каждом языке, который использует фиксированные типы данных, языки без безопасности типов могут попытаться перехватить это с другими типами данных. Однако, как только они достигнут своей "естественной" (заданной Системой) границы - они могут вернуть что угодно, но правильный результат.
Однако каждый язык может иметь разные потоки для такого сценария.
Другие ответы уже объяснили, что здесь происходит (как обычно, с плавающей запятой).
Одно из решений состоит в том, чтобы использовать достаточно большой целочисленный тип или надеяться, что язык выберет один, если это необходимо.
Другое решение состоит в том, чтобы использовать алгоритм суммирования, который знает о проблеме точности и работает вокруг нее. Ниже вы найдете то же самое суммирование, сначала с 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-разрядных.
В рубине:
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 под капотом, который является одной из самых быстрых библиотек произвольной точности.
Чтобы получить правильный результат в php, я думаю, вам нужно использовать математические операторы BC: http://php.net/manual/en/ref.bc.php
Вот правильный ответ в Scala. Вы должны использовать длинные, иначе вы переполните число:
println((1L to 1000000000L).reduce(_ + _)) // prints 500000000500000000
Берут в рубине целую вечность, но дает правильный ответ:
(1..1000000000).reduce(:+)
=> 500000000500000000
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, возможно, выполнил некоторую внутреннюю JIT-обработку, чтобы он работал быстро, но динамический опыт немедленного запуска кода такой же.
У меня недостаточно репутации, чтобы комментировать ответ на Common 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
На самом деле есть крутой трюк с этой проблемой.
Предположим, что это было 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)
Это намного быстрее, чем перебирать все эти данные. Ваш процессор поблагодарит вас за это. И вот интересная история, касающаяся этой самой проблемы:
Болтовня:
(1 to: 1000000000) inject: 0 into: [:subTotal :next | subTotal + next ].
"500000000500000000"
Ракетка v 5.3.4 (MBP; время в мс):
> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000
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" скрипт работал два часа, и работал бы больше, но я его остановил. Слишком медленно.
Это дает правильный результат в PHP путем принудительного целочисленного приведения.
$sum = (int) $sum + $i;
Категория другой интерпретируемый язык:
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, чтобы получить его скомпилированным байтом.
Прекрасно работает в Rebol:
>> sum: 0
== 0
>> repeat i 1000000000 [sum: sum + i]
== 500000000500000000
>> type? sum
== integer!
При этом использовался Rebol 3, который, несмотря на 32-битную компиляцию, использует 64-битные целые числа (в отличие от Rebol 2, который использовал 32-битные целые числа)
Эрланг тоже дает ожидаемый результат.
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
Для полноты в Clojure (красиво, но не очень эффективно):
(reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000
Я хотел посмотреть, что произошло в CF Script
<cfscript>
ttl = 0;
for (i=0;i LTE 1000000000 ;i=i+1) {
ttl += i;
}
writeDump(ttl);
abort;
</cfscript>
Я получил 5.00000000067E+017
Это был довольно аккуратный эксперимент. Я вполне уверен, что мог бы закодировать это немного лучше, приложив больше усилий.
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 и Node.js не работают должным образом, поэтому я не буду повторять это здесь. Я просто хочу отметить, что это не имеет ничего общего с "интерпретированными и скомпилированными языками".
Возможно, это проблема интерпретируемых языков, и поэтому она работает на скомпилированном языке, таком как Go?
"Язык" - это просто набор четко определенных правил; реализация языка - это то, что интерпретируется или компилируется. Я мог бы взять язык, основная реализация которого скомпилирована (например, Go), и написать для него интерпретатор (и наоборот), но каждая программа, обработанная интерпретатором, должна выдавать идентичный вывод, как при запуске программы через скомпилированную реализацию, и этот вывод должно соответствовать спецификации языка. Результаты PHP и Node.js фактически соответствуют спецификациям языков (как указывают некоторые другие ответы), и это не имеет ничего общего с тем фактом, что основные реализации этих языков интерпретируются; Скомпилированные реализации языков по определению также должны давать те же результаты.
Реальным примером всего этого является Python, который имеет как широко используемые скомпилированные, так и интерпретируемые реализации. Запуск переведенной версии вашей программы в интерпретированной реализации:
>>> total = 0
>>> for i in xrange(1000000001):
... total += i
...
>>> print total
500000000500000000
по определению Python не должен приводить к выводу, отличному от запуска его в скомпилированной реализации:
total = 0
for i in xrange(1000000001):
total += i
print total
500000000500000000
Для кода PHP ответ здесь:
Размер целого числа зависит от платформы, хотя максимальное значение около двух миллиардов является обычным значением (это 32 бита со знаком). 64-битные платформы обычно имеют максимальное значение около 9E18. PHP не поддерживает целые числа без знака. Целочисленный размер можно определить с помощью константы PHP_INT_SIZE, а максимальное значение - с помощью константы PHP_INT_MAX, начиная с PHP 4.4.0 и PHP 5.0.5.
Забавно, PHP 5.5.1 выдает 499999999500000000 (через ~ 30 с), в то время как Dart2Js выдает 500000000067109000 (что и следовало ожидать, поскольку выполняется JS). CLI Dart дает правильный ответ... мгновенно.
Только для полноты.
В MATLAB нет проблем с автоматическим выбором типа:
tic; ii = 1:1000000; sum(ii); toc; ans
Elapsed time is 0.004471 seconds.
ans = 5.000005000000000e+11
А в интерактивном F# автоматические типы единиц дают ошибку переполнения. Назначение типа int64 дает правильный ответ:
seq {int64 1.. int64 1000000} |> Seq.sum
val it : int64 = 500000500000L
Заметки:
Мог бы использовать Seq.reduce (+) вместо Seq.sum без заметного изменения эффективности. Однако, используя Seq.reduce (+) с автоматическим типом устройства даст неправильный ответ, а не ошибку переполнения.
Время вычислений составляет <.5 секунд, но я в настоящее время ленив, и поэтому я не импортирую класс секундомера.NET, чтобы получить более точное время.