Nieoczekiwane wyniki podczas pracy z bardzo dużymi liczbami całkowitymi w językach interpretowanych

Próbuję dostać sumę 1 + 2 + ... + 1000000000, ale jestem coraz śmieszne wyników w PHP i 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

Prawidłową odpowiedź można obliczyć za pomocą

1 + 2 + ... + n = n(n+1)/2

Prawidłowa odpowiedź = 500000000500000000 , więc postanowiłem spróbować innego języka.

UDAĆ SIĘ

var sum , i int64
for i = 0 ; i <= 1000000000; i++ {
    sum += i
}
fmt.Println(sum) // 500000000500000000

Ale działa dobrze! Więc co jest nie tak z moim kodem PHP i Node.js?

Być może jest to problem interpretowanych języków i dlatego działa w skompilowanym języku takim jak Go? Jeśli tak, to czy inne interpretowane języki, takie jak Python i Perl, miałyby ten sam problem?

Python działa:

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

Lub:

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

intAuto Pythona awansuje do Pythona, longktóry obsługuje dowolną precyzję. Wywoła poprawną odpowiedź na platformach 32- lub 64-bitowych.

Można to zaobserwować, podnosząc 2 do mocy znacznie większej niż szerokość bitowa platformy:

>>> 2**99
633825300114114700748351602688L

Możesz zademonstrować (za pomocą Pythona), że błędne wartości otrzymywane w PHP są spowodowane tym, że PHP promuje się jako zmiennoprzecinkowe, gdy wartości są większe niż 2 ** 32-1:

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

Twój kod Go używa arytmetyki liczb całkowitych z wystarczającą liczbą bitów, aby dać dokładną odpowiedź. Nigdy nie dotknąłem PHP ani Node.js, ale z wyników podejrzewam, że matematyka jest wykonywana przy użyciu liczb zmiennoprzecinkowych i dlatego należy oczekiwać, że nie będzie dokładna dla liczb tej wielkości.

Powodem jest to, że wartość zmiennej całkowitej sumprzekracza wartość maksymalną. A summasz jest wynikiem pływak-punktowej arytmetyki która polega zaokrągleń. Ponieważ inne odpowiedzi nie wspominały o dokładnych limitach, postanowiłem to opublikować.

Maksymalna wartość całkowita dla PHP dla:

• Wersja 32-bitowa to 2147483647
• Wersja 64-bitowa to 9223372036854775807

Oznacza to, że używasz 32-bitowego procesora, 32-bitowego systemu operacyjnego lub 32-bitowej wersji PHP. Można go znaleźć za pomocą PHP_INT_MAX. Zostanie sumobliczony poprawnie, jeśli zrobisz to na komputerze 64-bitowym.

Maksymalna wartość całkowita w JavaScript to 9007199254740992 . Największa dokładna wartość całki, z którą możesz pracować, to 2 ⁵³ (wzięte z tego pytania ). sumPrzekroczy ten limit.

Jeśli wartość całkowita nie przekracza tych limitów, oznacza to, że jesteś dobry. W przeciwnym razie będziesz musiał szukać bibliotek liczb całkowitych o dowolnej precyzji.

Oto odpowiedź w C, dla kompletności:

#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;
}

Kluczem w tym przypadku jest użycie typu danych C99 long long . Zapewnia największą prymitywną pamięć C, którą może zarządzać, i działa naprawdę, bardzo szybko. Ten long longtyp będzie również działał na większości dowolnych komputerów 32- lub 64-bitowych.

Jest jedno zastrzeżenie: kompilatory dostarczone przez Microsoft wyraźnie nie obsługują 14-letniego standardu C99, więc uruchomienie go w Visual Studio to crapshot.

Domyślam się, że gdy suma przekracza pojemność natywnego int(2 ³¹ -1 = 2 147 483 647), Node.js i PHP przełączają się na reprezentację zmiennoprzecinkową i zaczynają pojawiać się błędy zaokrągleń. Język taki jak Go prawdopodobnie będzie starał się trzymać z liczbą całkowitą (np. 64-bitowe liczby całkowite) tak długo, jak to możliwe (jeśli rzeczywiście nie zaczął się od tego). Ponieważ odpowiedź mieści się w 64-bitowej liczbie całkowitej, obliczenia są dokładne.

Skrypt Perla daje nam oczekiwany wynik:

use warnings;
use strict;

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

Odpowiedź na to jest „zaskakująco” prosta:

Po pierwsze - jak większość z was może wiedzieć - 32-bitowa liczba całkowita wynosi od -2 147 483 648 do 2147 483 647 . Co się stanie, jeśli PHP otrzyma wynik, który jest WIĘKSZY niż ten?

Zwykle można się spodziewać natychmiastowego „przepełnienia”, powodując, że 2 147 483 647 + 1 zmienia się w -2 147 147 483 648 . Tak jednak nie jest. JEŻELI PHP napotyka większą liczbę, zwraca wartość FLOAT zamiast INT.

Jeśli PHP napotka liczbę przekraczającą granice liczby całkowitej, zostanie ona zinterpretowana jako liczba zmiennoprzecinkowa. Również operacja, w wyniku której liczba wykracza poza granice liczby całkowitej, zwróci liczbę zmiennoprzecinkową.

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

To powiedziawszy, i wiedząc, że implementacja PHP FLOAT jest zgodna z formatem podwójnej precyzji IEEE 754, oznacza, że ​​PHP jest w stanie poradzić sobie z liczbami do 52 bitów, bez utraty precyzji. (W systemie 32-bitowym)

Tak więc w punkcie, w którym twoja suma osiągnie 9 007 199 254 440,992 (czyli 2 ^ 53 ) Wartość zmiennoprzecinkowa zwrócona przez matematykę PHP nie będzie już wystarczająco precyzyjna.

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

Ten przykład pokazuje punkt, w którym PHP traci precyzję. Po pierwsze, ostatni znaczący bit zostanie usunięty, co spowoduje, że pierwsze 2 wyrażenia będą miały taką samą liczbę - co nie jest.

Od TERAZ cała matematyka pójdzie nie tak podczas pracy z domyślnymi typami danych.

• Czy to ten sam problem w przypadku innych interpretowanych języków, takich jak Python lub Perl?

Nie wydaje mi się Myślę, że jest to problem języków, które nie mają bezpieczeństwa typu. Podczas gdy przepełnienie liczb całkowitych, jak wspomniano powyżej, BĘDZIE występować w każdym języku, który używa stałych typów danych, języki bez bezpieczeństwa typu mogą próbować wychwycić to z innymi typami danych. Jednak po osiągnięciu „naturalnej” (podanej przez system) granicy - mogą zwrócić wszystko, ale właściwy wynik.

Jednak każdy język może mieć różne wątki dla takiego scenariusza.

Inne odpowiedzi już wyjaśniły, co się tutaj dzieje (jak zwykle zmiennoprzecinkowa).

Jednym z rozwiązań jest użycie wystarczająco dużej liczby całkowitej lub mieć nadzieję, że język wybierze ją w razie potrzeby.

Innym rozwiązaniem jest użycie algorytmu sumowania, który zna problem precyzji i działa na jego podstawie. Poniżej znajduje się to samo podsumowanie, najpierw z 64-bitową liczbą całkowitą, następnie z 64-bitową zmiennoprzecinkową, a następnie ponownie używając zmiennoprzecinkowego, ale z algorytmem sumowania Kahana .

Napisane w C #, ale to samo dotyczy innych języków.

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

Podsumowanie Kahana daje piękny wynik. Obliczenie zajmuje oczywiście więcej czasu. To, czy chcesz go użyć, zależy od a) wydajności i potrzeb precyzji oraz b) tego, jak Twój język obsługuje typy danych liczb całkowitych i zmiennoprzecinkowych.

Jeśli masz 32-bitowy PHP, możesz go obliczyć za pomocą bc :

<?php

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

W Javascript musisz użyć dowolnej biblioteki liczb, na przykład BigInteger :

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

Nawet w przypadku języków takich jak Go i Java w końcu będziesz musiał użyć dowolnej biblioteki liczb, twoja liczba była po prostu wystarczająco mała dla 64-bitowych, ale zbyt wysoka dla 32-bitowych.

W Ruby:

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

Drukuje 500000000500000000, ale zajmuje 4 minuty na moim Intel i7 2,6 GHz.

Magnuss i Jaunty mają znacznie więcej Rubiego:

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

Aby uruchomić test porównawczy:

$ 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

Używam node-bigint do dużych liczb całkowitych:
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);

Nie jest tak szybki, jak coś, co może używać natywnych 64-bitowych danych do tego dokładnego testu, ale jeśli dojdziesz do większej liczby niż 64-bit, używa libgmp pod maską, która jest jedną z najszybszych bibliotek o dowolnej precyzji.

wieki w rubinie, ale daje poprawną odpowiedź:

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

Aby uzyskać poprawny wynik w php, myślę, że będziesz musiał użyć operatorów matematycznych BC: http://php.net/manual/en/ref.bc.php

Oto poprawna odpowiedź w Scali. Musisz użyć Longs, w przeciwnym razie przepełnisz liczbę:

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

Ten problem jest naprawdę fajny.

Załóżmy, że zamiast tego było to 1-100.

1 + 2 + 3 + 4 + ... + 50 +

100 + 99 + 98 + 97 + ... + 51

= (101 + 101 + 101 + 101 + ... + 101) = 101 * 50

Formuła:

Dla N = 100: Wyjście = N / 2 * (N + 1)

Dla N = 1e9: Wyjście = N / 2 * (N + 1)

Jest to o wiele szybsze niż przeglądanie wszystkich tych danych. Twój procesor ci za to podziękuje. A oto ciekawa historia dotycząca tego właśnie problemu:

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

Daje to poprawny wynik w PHP poprzez wymuszenie rzutowania liczbami całkowitymi.

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

Common Lisp jest jednym z najszybciej interpretowanych języków * i domyślnie poprawnie obsługuje dowolne duże liczby całkowite. W SBCL zajmuje to około 3 sekund :

* (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

• Zinterpretowany, mam na myśli, że uruchomiłem ten kod z REPL, SBCL mógł wewnętrznie wykonać JITing, aby działał szybko, ale dynamiczne działanie natychmiastowego uruchamiania kodu jest takie samo.

Nie mam wystarczającej reputacji, aby skomentować odpowiedź Common Lisp @ postfuturist, ale można ją zoptymalizować w ~ 500ms za pomocą SBCL 1.1.8 na moim komputerze:

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; czas w ms):

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

Działa dobrze w Rebol:

>> sum: 0
== 0

>> repeat i 1000000000 [sum: sum + i]
== 500000000500000000

>> type? sum
== integer!

To było przy użyciu Rebol 3, który pomimo 32-bitowej kompilacji używa 64-bitowych liczb całkowitych (w przeciwieństwie do Rebol 2, który używał 32-bitowych liczb całkowitych)

Chciałem zobaczyć, co się wydarzyło w skrypcie CF.

<cfscript>
ttl = 0;

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

Mam 5,00000000067E + 017

To był całkiem fajny eksperyment. Jestem całkiem pewien, że przy większym wysiłku mógłbym to kodować nieco lepiej.

ActivePerl v5.10.1 w 32-bitowych oknach, Intel Core2duo 2.6:

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

wynik: 5,00000000067109e + 017 w 5 minut.

Skrypt „use bigint” działał przez dwie godziny i działał dłużej, ale przestałem. Za wolno.

Dla kompletności w Clojure (piękny, ale niezbyt wydajny):

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

AWK:

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

daje taki sam zły wynik jak PHP:

500000000067108992

Wygląda na to, że AWK używa liczb zmiennoprzecinkowych, gdy liczby są naprawdę duże, więc przynajmniej odpowiedź brzmi: właściwy rząd wielkości.

Przebiegi testowe:

$ 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

Kategoria inny tłumaczony język:

Tcl:

Jeśli używasz Tcl 8.4 lub starszego, zależy to, czy został skompilowany z 32- lub 64-bitowym kodem. (8.4 to koniec życia).

Jeśli używasz Tcl 8.5 lub nowszego, który ma dowolne duże liczby całkowite, wyświetli poprawny wynik.

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

Umieszczam test w proc, aby uzyskać kompilację bajtów.

W przypadku kodu PHP odpowiedź jest tutaj :

Rozmiar liczby całkowitej zależy od platformy, chociaż maksymalna wartość wynosząca około dwóch miliardów jest zwykle wartością (to 32 bitów ze znakiem). Platformy 64-bitowe zwykle mają maksymalną wartość około 9E18. PHP nie obsługuje liczb całkowitych bez znaku. Wielkość całkowitą można określić za pomocą stałej PHP_INT_SIZE, a maksymalną wartość za pomocą stałej PHP_INT_MAX od PHP 4.4.0 i PHP 5.0.5.

Port:

proc Main()

   local sum := 0, i

   for i := 0 to 1000000000
      sum += i
   next

   ? sum

   return

Wyniki w 500000000500000000. (zarówno w systemie Windows / mingw / x86, jak i osx / clang / x64)

Erlang działa:

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).

Wyniki: 41> bezużyteczne: from_sum (1 1000000000). 500000000500000000

Zabawne, PHP 5.5.1 daje 499999999500000000 (w ~ 30s), podczas gdy Dart2Js daje 500000000067109000 (czego należy się spodziewać, ponieważ wykonywany jest JS). CLI Dart daje właściwą odpowiedź ... natychmiast.

Erlang daje również oczekiwany wynik.

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).

I używając go:

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

Pogawędka:

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

"500000000500000000"