Unerwartete Ergebnisse bei der Arbeit mit sehr großen Ganzzahlen in interpretierten Sprachen

192

Ich versuche , die Summe zu bekommen 1 + 2 + ... + 1000000000, aber ich bin immer lustig Ergebnisse in PHP und 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

Die richtige Antwort kann mit berechnet werden

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

Richtige Antwort = 500000000500000000 , also habe ich beschlossen, eine andere Sprache auszuprobieren.

GEHEN

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

Aber es funktioniert gut! Was ist also falsch an meinem PHP- und Node.js-Code?

Vielleicht ist dies ein Problem interpretierter Sprachen, und deshalb funktioniert es in einer kompilierten Sprache wie Go? Wenn ja, hätten andere interpretierte Sprachen wie Python und Perl das gleiche Problem?

Baba
quelle
36
Sie brauchen dies: php.net/manual/en/book.bc.php , oder Sie schlagen Ihren Kopf gegen IEEE 754, bis die Hölle zufriert.
Tereško
5
Verwenden Sie zum Behandeln großer Zahlen in PHP (dh 64-Bit) die GMP-Funktionen, in diesem Fall gmp_add ().
Jeffrey
113
Für eine super Effizienz sollten Ihre Loops wirklich bei 1 statt bei 0 beginnen: P
Graham Borland
55
Summe (1 bis N) = (N / 2) * (N + 1)
Phong
5
@Baba 0 ist für Ihre Berechnung überflüssig, so dass keine zusätzliche Iteration der Schleife erforderlich ist, um 0 zu 0 hinzuzufügen.
Brian Warshaw

Antworten:

155

Python funktioniert:

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

Oder:

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

Pythons intAuto wird zu einem Python longhochgestuft, der beliebige Genauigkeit unterstützt. Auf 32- oder 64-Bit-Plattformen wird die richtige Antwort ausgegeben.

Dies kann gesehen werden, indem 2 auf eine Leistung angehoben wird, die weit größer als die Bitbreite der Plattform ist:

>>> 2**99
633825300114114700748351602688L

Sie können (mit Python) demonstrieren, dass die fehlerhaften Werte, die Sie in PHP erhalten, darauf zurückzuführen sind, dass PHP zu einem Float hochgestuft wird, wenn die Werte größer als 2 ** 32-1 sind:

>>> int(sum(float(x) for x in xrange(1000000000+1)))
500000000067108992
dawg
quelle
Haben Sie dies auf einem 32- oder 64-Bit-System ausgeführt?
Baba
4
Es sollte unabhängig davon funktionieren (32 vs 64 Bit), da Python Ints automatisch mit willkürlicher Genauigkeit und nicht mit Überlauf hochstufen. Könnte eine Weile länger dauern.
Morgengrauen
3
Python funktioniert in diesem Fall auf jedem System, da Python bei Bedarf automatisch auf lange Ganzzahlen umschaltet. Und wenn das nicht genug ist, wird auch auf große Ganzzahlen umgeschaltet.
Alok Singhal
12
@ 0x499602D2: Das ist ein bisschen hart. Das OP selbst hat dafür gestimmt. Er fragte speziell, ob dies ein ähnliches Problem bei Python sei. Antworte, nein ist es nicht. Code, um zu zeigen, dass dies nicht der Fall ist. WTH?
Morgengrauen
10
Das Python-Beispiel ist zu lang, verwenden Sie einfach sum (xrange (int (1e9) +1)) (.... sum funktioniert auf iterables)
Jason Morgan
101

Ihr Go-Code verwendet eine Ganzzahlarithmetik mit genügend Bits, um eine genaue Antwort zu geben. Nie PHP oder Node.js berührt, aber aufgrund der Ergebnisse vermute ich, dass die Berechnung mit Gleitkommazahlen durchgeführt wird und daher erwartet werden sollte, dass sie für Zahlen dieser Größenordnung nicht genau sind.

zzzz
quelle
46
Ja. If PHP encounters a number beyond the bounds of the integer type, it will be interpreted as a float instead. Also, an operation which results in a number beyond the bounds of the integer type will return a float instead.- php.net/manual/en/language.types.integer.php
Nate
3
Und in NodeJS (und JavaScript im Allgemeinen) verhalten sich alle arithmetischen Operationen (außer Bitoperationen) so, als ob sie mit Gleitkommazahlen ausgeführt würden. Ob dies tatsächlich der Fall ist oder nicht, hängt von den Entscheidungen der einzelnen JavaScript-Engines ab.
Peter Olson
13
In der Javascript-Spezifikation gibt es keine Ganzzahltypen. Alle Zahlen sind Gleitkommazahlen.
Toasted_flakes
8
@ GrasGendarme Es gibt. Die ES5-Spezifikation spezifiziert verschiedene ganzzahlige Konvertierungen und Mandate, die beispielsweise in bitweisen Verschiebungen aufgerufen werden sollen . Das heißt, hinter den Kulissen werden in Javascript ganzzahlige Typen verwendet, aber alle arithmetischen Operatoren konvertieren ihre Operanden in Gleitkommazahlen, bevor sie etwas mit ihnen tun (mit Ausnahme von Compileroptimierungen).
Peter Olson
2
Hier ist der Code, den ich vermasselt habe, weil ich float64 und nicht int64 verwendet habe. Ich habe nur bestätigt, dass er nichts mit 32 oder 64 Bit zu tun hat
Baba
45

Der Grund ist, dass der Wert Ihrer Ganzzahlvariablen sumden Maximalwert überschreitet. Und das, was sumSie erhalten, ist das Ergebnis einer Gleitkomma-Arithmetik, bei der abgerundet wird. Da in anderen Antworten die genauen Grenzen nicht erwähnt wurden, habe ich beschlossen, sie zu veröffentlichen.

Der maximale ganzzahlige Wert für PHP für:

  • Die 32-Bit-Version ist 2147483647
  • Die 64-Bit-Version lautet 9223372036854775807

Dies bedeutet, dass Sie entweder eine 32-Bit-CPU oder ein 32-Bit-Betriebssystem oder eine 32-Bit-kompilierte Version von PHP verwenden. Es kann mit gefunden werden PHP_INT_MAX. Das sumwürde korrekt berechnet, wenn Sie es auf einem 64-Bit-Computer tun.

Der maximale ganzzahlige Wert in JavaScript beträgt 9007199254740992 . Der größte exakte Integralwert, mit dem Sie arbeiten können, ist 2 53 (aus dieser Frage entnommen ). Das sumüberschreitet diese Grenze.

Wenn der ganzzahlige Wert diese Grenzwerte nicht überschreitet, sind Sie gut. Andernfalls müssen Sie nach Ganzzahlbibliotheken mit beliebiger Genauigkeit suchen.

user568109
quelle
28

Hier ist der Vollständigkeit halber die Antwort in 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;
}

Der Schlüssel in diesem Fall ist die Verwendung des long long Datentyps von C99 . Es bietet den größten primitiven Speicher, den C verwalten kann, und läuft sehr, sehr schnell. Der long longTyp funktioniert auch auf den meisten 32- oder 64-Bit-Computern.

Es gibt eine Einschränkung: Von Microsoft bereitgestellte Compiler unterstützen den 14 Jahre alten C99-Standard ausdrücklich nicht. Daher ist es ein Crapshot, diesen in Visual Studio auszuführen.

CyberSkull
quelle
3
MSVC ++ ist ein C ++ - Compiler, und C ++ wurde long longin den C ++ 11-Standard aufgenommen. Es ist jedoch seit einigen Jahren eine MSVC ++ - und g ++ - Erweiterung.
MSalters
1
@MSalters Da es sich also um eine C ++ - Funktion handelt, hilft es niemandem, ein direktes C-Programm zu kompilieren. Ich habe nie versucht, von C nach C ++ zu wechseln, daher weiß ich nicht, ob diese Problemumgehung tatsächlich funktionieren würde.
CyberSkull
19
Und schön, GCC oder Clang mit Optimierungen verwandeln die ganze Schleife inmovabsq $500000000500000000, %rsi
Tor Klingberg
3
Einfach gcc -O3oder clang -O3. Ich kenne den Namen der spezifischen Optimierung nicht. Grundsätzlich stellt der Compiler fest, dass das Ergebnis der Schleife von keinem Argument abhängt, und berechnet es zur Kompilierungszeit.
Tor Klingberg
1
C99 long long hat eine Mindestgröße von 64 Bit und ist meines Wissens auf 32-Bit- und 64-Bit-Plattformen 64-Bit. Ich habe keine allgemeine Unterstützung für Quad- oder Octo-Ints gesehen.
Devin Lane
21

Ich vermute, wenn die Summe die Kapazität eines nativen Systems überschreitet int(2 31 -1 = 2.147.483.647), wechseln Node.js und PHP zu einer Gleitkommadarstellung und es treten Rundungsfehler auf. Eine Sprache wie Go wird wahrscheinlich versuchen, so lange wie möglich bei einer Ganzzahlform (z. B. 64-Bit-Ganzzahlen) zu bleiben (wenn dies tatsächlich nicht damit begonnen hat). Da die Antwort in eine 64-Bit-Ganzzahl passt, ist die Berechnung genau.

Ted Hopp
quelle
Node.js hat explizit keinen int-Typ. Es funktioniert in einem Float-Typ.
Greyfade
@greyfade - Ja, ich denke, das gilt für alle EcmaScript-kompatiblen Umgebungen.
Ted Hopp
Ist das nicht (2 ** 31 - 1)?
Zachary Hunter
@ ZacharyHunter - In der Tat ist es. Vielen Dank, dass Sie diesen Fehler entdeckt haben.
Ted Hopp
19

Perl-Skript geben uns das erwartete Ergebnis:

use warnings;
use strict;

my $sum = 0;
for(my $i = 0; $i <= 1_000_000_000; $i++) {
    $sum += $i;
}
print $sum, "\n";  #<-- prints: 500000000500000000
Miguel Prz
quelle
3
Haben Sie dies auf einem 32- oder 64-Bit-System ausgeführt?
Baba
2
es wurde auf 64-Bit-System ausgeführt
Miguel Prz
3
4.99999999067109e+017unter Perl v5.16.1 MSWin32-x86.
Qtax
7
Wenn Sie wirklich große Zahlen benötigen, verwenden Sie das bignumoder bigint. Beide sind Kernmodule, dh sie werden mit Perl v5.8.0 oder höher installiert. Siehe http://perldoc.perl.org/bignum.htmlundhttp://perldoc.perl.org/bigint.html
shawnhcorey
Ich habe 500000000500000000 auf einem 32-Bit-PPC-Mac mit Perl 5.12.4 ausgeführt.
CyberSkull
17

Die Antwort darauf ist "überraschend" einfach:

Erstens reicht - wie die meisten von Ihnen vielleicht wissen - eine 32-Bit-Ganzzahl von –2.147.483.648 bis 2.147.483.647 . Was passiert also, wenn PHP ein Ergebnis erzielt, das GRÖSSER ist?

Normalerweise würde man einen sofortigen "Überlauf" erwarten, wodurch 2.147.483.647 + 1 zu -2.147.483.648 werden . Dies ist jedoch NICHT der Fall. Wenn PHP auf eine größere Zahl stößt, wird FLOAT anstelle von INT zurückgegeben.

Wenn PHP auf eine Zahl stößt, die über die Grenzen des Integer-Typs hinausgeht, wird sie stattdessen als Float interpretiert. Außerdem gibt eine Operation, die zu einer Zahl führt, die über die Grenzen des Integer-Typs hinausgeht, stattdessen einen Float zurück.

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

Das heißt, und zu wissen, dass die Implementierung von PHP FLOAT dem IEEE 754-Format mit doppelter Genauigkeit folgt, bedeutet, dass PHP in der Lage ist, Zahlen bis zu 52 Bit zu verarbeiten, ohne an Genauigkeit zu verlieren. (Auf einem 32-Bit-System)

An dem Punkt, an dem Ihre Summe 9.007.199.254.740.992 erreicht (das sind 2 ^ 53 ), ist der von PHP Maths zurückgegebene Float-Wert nicht mehr genau genug.

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

Dieses Beispiel zeigt den Punkt, an dem PHP an Genauigkeit verliert. Zuerst wird das letzte signifikante Bit gelöscht, wodurch die ersten beiden Ausdrücke zu einer gleichen Anzahl führen - was sie nicht sind.

Ab JETZT wird die gesamte Mathematik schief gehen, wenn mit Standarddatentypen gearbeitet wird.

• Ist es das gleiche Problem für andere interpretierte Sprachen wie Python oder Perl?

Das glaube ich nicht. Ich denke, dies ist ein Problem von Sprachen, die keine Typensicherheit haben. Während ein Integer-Überlauf wie oben erwähnt in jeder Sprache auftritt, die feste Datentypen verwendet, versuchen die Sprachen ohne Typensicherheit möglicherweise, dies mit anderen Datentypen abzufangen. Sobald sie jedoch ihre "natürliche" (vom System vorgegebene) Grenze erreicht haben, können sie alles zurückgeben, aber das richtige Ergebnis.

Jede Sprache kann jedoch unterschiedliche Threadings für ein solches Szenario haben.

dognose
quelle
15

Die anderen Antworten erklärten bereits, was hier passiert (Gleitkommapräzision wie gewohnt).

Eine Lösung besteht darin, einen ganzzahligen Typ zu verwenden, der groß genug ist, oder zu hoffen, dass die Sprache bei Bedarf einen auswählt.

Die andere Lösung besteht darin, einen Summationsalgorithmus zu verwenden, der das Präzisionsproblem kennt und es umgeht. Unten finden Sie dieselbe Summierung, zuerst mit 64-Bit-Ganzzahl, dann mit 64-Bit-Gleitkomma und dann wieder mit Gleitkomma, jedoch mit dem Kahan-Summierungsalgorithmus .

Geschrieben in C #, aber das Gleiche gilt auch für andere Sprachen.

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

Die Kahan-Summe ergibt ein schönes Ergebnis. Die Berechnung dauert natürlich viel länger. Ob Sie es verwenden möchten, hängt a) von Ihren Leistungs- und Präzisionsanforderungen ab und b) davon, wie Ihre Sprache mit Ganzzahl- und Gleitkomma-Datentypen umgeht.

Linac
quelle
@Baba Es ist dasselbe wie bei Node.js / JavaScript im OP. Warum 500000000067109000 vs. 500000000067108992… keine Ahnung.
Linac
Vielleicht ist Baba fasziniert von der Verwendung von Punkten für tausend Trennzeichen: Englisch erwartet normalerweise Kommas. Sie können auch Unterstriche als neutraleren Mittelwert verwenden.
Didierc
14

Wenn Sie 32-Bit-PHP haben, können Sie es mit bc berechnen :

<?php

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

In Javascript müssen Sie eine beliebige Zahlenbibliothek verwenden , zum Beispiel BigInteger :

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

Selbst bei Sprachen wie Go und Java müssen Sie möglicherweise eine beliebige Nummernbibliothek verwenden. Ihre Nummer war zufällig klein genug für 64-Bit, aber zu hoch für 32-Bit.

Esailija
quelle
12

In Ruby:

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

Druckt 500000000500000000, dauert aber auf meinem 2,6 GHz Intel i7 gut 4 Minuten.


Magnuss und Jaunty haben eine viel mehr Ruby-Lösung:

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

So führen Sie einen Benchmark durch:

$ 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
cgenco
quelle
10
1.upto (1000000000) .inject (: +)
Magnuss
@Magnuss: Das habe ich zuerst versucht, aber es hat einen massiven Speicherverlust verursacht. Ihre scheint zu funktionieren ...
Cgenco
11

Ich benutze Node-Bigint für große Ganzzahlen:
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);

Es ist nicht so schnell wie etwas, das native 64-Bit-Inhalte für diesen genauen Test verwenden kann. Wenn Sie jedoch größere Zahlen als 64-Bit verwenden, wird libgmp unter der Haube verwendet, eine der schnelleren Bibliotheken mit beliebiger Genauigkeit.

Eve Freeman
quelle
4

hat ewig in Rubin gedauert, gibt aber die richtige Antwort:

(1..1000000000).reduce(:+)
 => 500000000500000000 
Jauny
quelle
4

Um das richtige Ergebnis in PHP zu erhalten, müssten Sie vermutlich die BC-Mathematikoperatoren verwenden: http://php.net/manual/en/ref.bc.php

Hier ist die richtige Antwort in Scala. Sie müssen Longs verwenden, sonst überlaufen Sie die Nummer:

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

Es gibt tatsächlich einen coolen Trick zu diesem Problem.

Angenommen, es war stattdessen 1-100.

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

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

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

Formel:

Für N = 100: Ausgang = N / 2 * (N + 1)

Für N = 1e9: Ausgabe = N / 2 * (N + 1)

Dies ist viel schneller als das Durchlaufen all dieser Daten. Ihr Prozessor wird es Ihnen danken. Und hier ist eine interessante Geschichte zu diesem Problem:

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

user2522001
quelle
11
Glauben Sie, dass es möglich sein könnte, über jede Brücke über den Pregel in Kaliningrad zu gehen, ohne zweimal eine Brücke zu überqueren? Viele Menschen haben es versucht und sind gescheitert, aber noch hat niemand festgestellt, dass dies unmöglich ist. Dies scheint eine Herausforderung zu sein, für deren Lösung Sie in einzigartiger Weise qualifiziert wären.
JWG
3

Dies ergibt das richtige Ergebnis in PHP, indem die Ganzzahlumwandlung erzwungen wird.

$sum = (int) $sum + $i;
ck_
quelle
3

Common Lisp ist eine der am schnellsten interpretierten * Sprachen und verarbeitet beliebig große Ganzzahlen standardmäßig korrekt. Dies dauert bei SBCL ca. 3 Sekunden :

* (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
  • Mit interpretiert meine ich, ich habe diesen Code von der REPL ausgeführt. SBCL hat möglicherweise intern JITing durchgeführt, damit er schnell ausgeführt wird, aber die dynamische Erfahrung, Code sofort auszuführen, ist dieselbe.
Postfuturist
quelle
Kann vereinfacht werden als (Zeit (Schleife für x von 1 bis 1000000000 Summe x)). Ich habe ~ 5x Geschwindigkeit durch Hinzufügen der Deklaration erhalten: (Zeit (lokal (deklarieren (optimieren (Geschwindigkeit 3) (Sicherheit 0))) (Schleife für i vom Typ Fixnum von 1 bis 1000000000 Summe i vom Typ Fixnum)))
Huaiyuan
Das ist falsch. Lass dich nicht von den anderen Sprachen blenden! Die richtige Art, es in lisp zu schreiben, ist: (Summe von 1 bis n (n) (/ (* n (1+ n)) 2)) (Zeit (Summe von 1 bis n) 1000000000)) dauerte 14 Mikrosekunden (0,000014 Sekunden). Während dieses Zeitraums und mit 4 verfügbaren CPU-Kernen wurden 0 Mikrosekunden (0,000000 Sekunden) im Benutzermodus verbracht. 0 Mikrosekunden (0,000000 Sekunden) wurden im Systemmodus verbracht -> 500000000500000000
informatimago
@informatimago: Es ist nicht falsch. Ich habe den imperativen Schleifenstil der Frage kopiert, und wie viele darauf hingewiesen haben, erwähnt die Frage selbst, dass es eine einfachere Methode zur Berechnung gibt. Chillax.
Postfuturist
3

Ich habe nicht genug Ruf, um die Common Lisp-Antwort von @ postfuturist zu kommentieren, aber sie kann so optimiert werden, dass sie mit SBCL 1.1.8 auf meinem Computer in ~ 500 ms abgeschlossen ist:

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
jdtw
quelle
3

Racket v 5.3.4 (MBP; Zeit in ms):

> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000
Keith Flower
quelle
1
Löschte meine Antwort 6 Minuten nach dir, als ich deine bemerkte. :)
Greg Hendershott
3

Funktioniert gut in Rebol:

>> sum: 0
== 0

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

>> type? sum
== integer!

Hierbei wurde Rebol 3 verwendet, das trotz seiner 32-Bit-Kompilierung 64-Bit-Ganzzahlen verwendet (im Gegensatz zu Rebol 2, bei dem 32-Bit-Ganzzahlen verwendet wurden).

draegtun
quelle
3

Ich wollte sehen, was in CF Script passiert ist

<cfscript>
ttl = 0;

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

Ich habe 5.00000000067E + 017

Dies war ein ziemlich ordentliches Experiment. Ich bin mir ziemlich sicher, dass ich das mit mehr Aufwand ein bisschen besser hätte codieren können.

georgiamadkow
quelle
3

ActivePerl v5.10.1 unter 32-Bit-Fenstern, Intel Core2duo 2.6:

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

Ergebnis: 5.00000000067109e + 017 in 5 Minuten.

Mit "use bigint" funktionierte das Skript zwei Stunden lang und würde mehr funktionieren, aber ich habe es gestoppt. Zu langsam.

Schlau
quelle
Kann jemand bestätigen, dass das Hinzufügen so vieler Bigint wirklich so lange dauert?
JWG
3

Der Vollständigkeit halber in Clojure (schön, aber nicht sehr effizient):

(reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000
Blacksad
quelle
1
Das einzig Nützliche, das die $ MY_FAVOURITE_LANGUAGE-Antworten haben, ist, wenn sie das Ergebnis liefern ...
jwg
@jwg Ja, tut mir leid, ich habe das Ende der Zeile verpasst - aktualisierte Antwort.
Blacksad
3

AWK:

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

erzeugt das gleiche falsche Ergebnis wie PHP:

500000000067108992

Es scheint, dass AWK Gleitkomma verwendet, wenn die Zahlen wirklich groß sind, also ist zumindest die Antwort die richtige Größenordnung.

Testläufe:

$ 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
QuasarDonkey
quelle
2

Kategorie andere interpretierte Sprache:

Tcl:

Wenn Sie Tcl 8.4 oder älter verwenden, hängt es davon ab, ob es mit 32 oder 64 Bit kompiliert wurde. (8.4 ist das Ende des Lebens).

Wenn Sie Tcl 8.5 oder eine neuere Version mit beliebigen großen Ganzzahlen verwenden, wird das richtige Ergebnis angezeigt.

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

Ich habe den Test in einen Prozess eingefügt, um ihn bytekompiliert zu bekommen.

Johannes Kuhn
quelle
2

Für den PHP-Code lautet die Antwort hier :

Die Größe einer Ganzzahl ist plattformabhängig, obwohl ein Maximalwert von etwa zwei Milliarden der übliche Wert ist (das sind 32 Bit Vorzeichen). 64-Bit-Plattformen haben normalerweise einen Maximalwert von etwa 9E18. PHP unterstützt keine vorzeichenlosen Ganzzahlen. Die Ganzzahlgröße kann mit der Konstanten PHP_INT_SIZE und der Maximalwert mit der Konstanten PHP_INT_MAX seit PHP 4.4.0 und PHP 5.0.5 bestimmt werden.

Vicentazo
quelle
2

Hafen:

proc Main()

   local sum := 0, i

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

   ? sum

   return

Ergebnisse in 500000000500000000. (unter Windows / Mingw / x86 und OSX / Clang / x64)

vszakats
quelle
2

Erlang arbeitet:

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

Ergebnisse: 41> nutzlos: from_sum (1.1000000000). 500000000500000000

Steve Moon
quelle
2

Lustige Sache, PHP 5.5.1 gibt 499999999500000000 (in ~ 30s), während Dart2Js 500000000067109000 gibt (was zu erwarten ist, da es JS ist, das ausgeführt wird). CLI Dart gibt die richtige Antwort ... sofort.

Doru Moisa
quelle
2

Erlang gibt auch das erwartete Ergebnis.

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

Und damit:

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

Smalltalk:

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

"500000000500000000"
Samuel Henry
quelle