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

Я пытаюсь получить сумму 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, иметь такую ​​же проблему?

Python работает:

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

Или:

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

intАвто Python продвигается к Python, 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 . Наибольшее точное целое значение, с которым вы можете работать, составляет 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;
}

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

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

Я предполагаю, что когда сумма превышает емкость нативного 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 получит результат, который БОЛЬШЕ, чем этот?

Обычно можно ожидать немедленного «переполнения», в результате которого 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 под капотом, который является одной из самых быстрых библиотек произвольной точности.

берут в рубине целую вечность, но дает правильный ответ:

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

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

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

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

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

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

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

Ракетка v 5.3.4 (MBP; время в мс):

> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
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» скрипт работал два часа, и работал бы больше, но я его остановил. Слишком медленно.

Для полноты в 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

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

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 ответ здесь :

Размер целого числа зависит от платформы, хотя максимальное значение около двух миллиардов является обычным значением (это 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. (на обоих windows / 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 дает правильный ответ ... мгновенно.

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

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

Болтовня:

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

"500000000500000000"