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

Python работает:

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

Or:

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

Функция Python int auto превращается в 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 теряет точность. Сначала будет отброшен последний значащий бит, в результате чего первые 2 выражения дадут равное количество, а это не так.

С СЕЙЧАС вся математика пойдет не так при работе с типами данных по умолчанию.

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

В Ruby:

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

Prints 500000000500000000, but takes a good 4 minutes on my 2.6 GHz Intel i7.

У Магнуса и Джонти есть гораздо более Ruby-решение:

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

To run a benchmark:

$ 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. Вы должны использовать Long, иначе вы переполните число:

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

Racket 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-битной Windows, 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 

Я помещаю тест в процесс, чтобы он был скомпилирован в байтах.

Для кода 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)

Erlang работает:

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 дает правильный ответ ... мгновенно.

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

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"

Только для полноты.

В 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 (+) с автоматическим типом единицы измерения даст неправильный ответ, а не ошибку переполнения.
Время вычисления составляет <0,5 секунды, но в настоящее время я ленив, поэтому я не импортирую класс секундомера .NET, чтобы получить больше точное время.

Несколько ответов уже объяснили, почему ваш код 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

В Ruby эти функционально схожие решения (которые возвращают правильный ответ) требуют значительно разного времени для выполнения:

$ time ruby -e "(1..1000000000).inject{|sum, n| sum + n}"
real    1m26.005s
user    1m26.010s
sys 0m0.076s

$ time ruby -e "1.upto(1000000000).inject(:+)"
real    0m48.957s
user    0m48.957s
sys 0m0.045s

$ ruby -v
ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-darwin10.8.0]

Javascript (и, возможно, PHP) представляет все числа как двойные и округляет их для целых значений. Это означает, что они имеют только 53 бита точности (вместо 64 бита, предоставляемых int64 и Java long), и приведут к ошибкам округления для больших значений.

Как отмечали другие люди, самый быстрый способ выполнить этот расчет (независимо от языка) - использовать простую математическую функцию (вместо цикла с интенсивным использованием ЦП):

number = 1000000000;
result = (number/2) * (number+1);

Тем не менее, вам все равно придется решать любые проблемы с 32/64 битными целыми числами / числами с плавающей запятой, в зависимости от языка.

И рубиновый:

[15] pry(main)> (1..1000000000).inject(0) { |sum,e| sum + e }
=> 500000000500000000

Кажется, получил правильный номер.