php - que - Resultados inesperados al trabajar con enteros muy grandes en lenguajes interpretados
php lenguaje de programacion (30)
AWK:
BEGIN { s = 0; for (i = 1; i <= 1000000000; i++) s += i; print s }
produce el mismo resultado incorrecto que PHP:
500000000067108992
Parece que AWK usa un punto flotante cuando los números son realmente grandes, por lo que al menos la respuesta es el orden de magnitud correcto.
Ejecuciones de prueba:
$ 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
Estoy tratando de obtener la suma de 1 + 2 + ... + 1000000000 , pero estoy obteniendo resultados graciosos en PHP y 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
La respuesta correcta se puede calcular usando
1 + 2 + ... + n = n(n+1)/2
Respuesta correcta = 500000000500000000 , así que decidí probar otro idioma.
IR
var sum , i int64
for i = 0 ; i <= 1000000000; i++ {
sum += i
}
fmt.Println(sum) // 500000000500000000
¡Pero funciona bien! Entonces, ¿qué está mal con mi código PHP y Node.js?
Quizás este sea un problema de lenguajes interpretados, y es por eso que funciona en un lenguaje compilado como Go? Si es así, ¿tendrían el mismo problema otros idiomas interpretados, como Python y Perl?
ActivePerl v5.10.1 en ventanas de 32 bits, intel core2duo 2.6:
$sum = 0;
for ($i = 0; $i <= 1000000000 ; $i++) {
$sum += $i;
}
print $sum."/n";
Resultado: 5.00000000067109e + 017 en 5 minutos.
Con "usar bigint", el script funcionó durante dos horas y funcionaría más, pero lo detuve. Demasiado lento.
Aquí está la respuesta en C, para completar:
#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;
}
La clave en este caso es usar C99''s tipo de datos long long C99''s . Proporciona el mayor almacenamiento primitivo que C puede administrar y se ejecuta realmente, muy rápido. El tipo long long también funcionará en la mayoría de las máquinas de 32 o 64 bits.
Hay una advertencia: los compiladores proporcionados por Microsoft explícitamente no son compatibles con el estándar C99 de 14 años, por lo que conseguir que esto se ejecute en Visual Studio es una crapshot.
Categoría otro lenguaje interpretado:
Tcl:
Si usa Tcl 8.4 o más, depende de si fue compilado con 32 o 64 bits. (8.4 es el fin de la vida).
Si usa Tcl 8.5 o más reciente que tiene enteros grandes arbitrarios, se mostrará el resultado correcto.
proc test limit {
for {set i 0} {$i < $limit} {incr i} {
incr result $i
}
return $result
}
test 1000000000
Puse la prueba dentro de un proc para compilarlo por bytes.
Charla:
(1 to: 1000000000) inject: 0 into: [:subTotal :next | subTotal + next ].
"500000000500000000"
Common Lisp es uno de los idiomas * interpretados más rápidamente y maneja de manera predeterminada los enteros arbitrariamente grandes correctamente. Esto toma aproximadamente 3 segundos con 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
- Al interpretar, quiero decir, ejecuté este código desde el REPL, SBCL pudo haber hecho algunos JIT internamente para hacer que se ejecute rápidamente, pero la experiencia dinámica de ejecutar el código de inmediato es la misma.
El script de Perl nos da el resultado esperado:
use warnings;
use strict;
my $sum = 0;
for(my $i = 0; $i <= 1_000_000_000; $i++) {
$sum += $i;
}
print $sum, "/n"; #<-- prints: 500000000500000000
En Ruby:
sum = 0
1.upto(1000000000).each{|i|
sum += i
}
puts sum
Imprime 500000000500000000 , pero toma unos 4 minutos en mi Intel i7 de 2.6 GHz.
Magnuss y Jaunty tienen una solución Ruby mucho más:
1.upto(1000000000).inject(:+)
Para ejecutar un punto de referencia:
$ 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
En aras de la integridad, en Clojure (hermoso pero no muy eficiente):
(reduce + (take 1000000000 (iterate inc 1))) ; => 500000000500000000
En realidad, hay un truco genial para este problema.
Supongamos que fue 1-100 en su lugar.
1 + 2 + 3 + 4 + ... + 50 +
100 + 99 + 98 + 97 + ... + 51
= (101 + 101 + 101 + 101 + ... + 101) = 101 * 50
Fórmula:
Para N = 100: Salida = N / 2 * (N + 1)
Para N = 1e9: Salida = N / 2 * (N + 1)
Esto es mucho más rápido que recorrer todos esos datos. Tu procesador te lo agradecerá. Y aquí hay una historia interesante sobre este problema:
Erlang da el resultado esperado también.
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).
Y usándolo:
1> c(sum).
{ok,sum}
2> sum:iter_sum(1,1000000000).
500000000500000000
Erlang trabaja:
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).Resultados: 41> inútil: from_sum (1,1000000000). 500000000500000000
Esto da el resultado adecuado en PHP al forzar la conversión de enteros.
$sum = (int) $sum + $i;
Funciona bien en Rebol:
>> sum: 0
== 0
>> repeat i 1000000000 [sum: sum + i]
== 500000000500000000
>> type? sum
== integer!
Esto fue usar Rebol 3, que a pesar de estar compilado con 32 bits, usa números enteros de 64 bits (a diferencia de Rebol 2 que usaba números enteros de 32 bits)
La razón es que el valor de la sum de su variable de entero excede el valor máximo. Y la sum que obtiene es el resultado de la aritmética de punto flotante que implica redondear. Como otras respuestas no mencionaron los límites exactos, decidí publicarlo.
El valor entero máximo para PHP para:
- La versión de 32 bits es 2147483647
- La versión de 64 bits es 9223372036854775807
Por lo tanto, significa que está utilizando una CPU de 32 bits o un sistema operativo de 32 bits o una versión compilada de PHP de 32 bits. Se puede encontrar usando PHP_INT_MAX . La sum se calcularía correctamente si lo haces en una máquina de 64 bits.
El valor entero máximo en JavaScript es 9007199254740992 . El mayor valor integral exacto con el que puede trabajar es 2 53 (tomado de esta question ). La sum supera este límite.
Si el valor entero no excede estos límites, entonces usted es bueno. De lo contrario, tendrá que buscar bibliotecas enteras de precisión arbitraria.
La respuesta a esto es "sorprendentemente" simple:
Primero, como la mayoría de ustedes saben, un número entero de 32 bits varía de −2,147,483,648 a 2,147,483,647 . Entonces, ¿qué pasa si PHP obtiene un resultado, que es MÁS GRANDE que esto?
Por lo general, uno esperaría un "Desbordamiento" inmediato, lo que provocaría que 2,147,483,647 + 1 se convirtiera en −2,147,483,648 . Sin embargo, este no es el caso. Si PHP encuentra un número mayor, devuelve FLOAT en lugar de INT.
Si PHP encuentra un número más allá de los límites del tipo de entero, se interpretará como un flotante en su lugar. Además, una operación que resulte en un número más allá de los límites del tipo entero devolverá un flotante en su lugar.
php.net/manual/en/language.types.integer.php
Dicho esto, y sabiendo que la implementación de PHP FLOAT está siguiendo el formato IEEE 754 de doble precisión, significa que PHP puede manejar números de hasta 52 bits, sin perder precisión. (En un sistema de 32 bits)
Entonces, en el Punto, donde su Suma llega a 9,007,199,254,740,992 (que es 2 ^ 53 ) El valor de Flotación devuelto por el PHP Maths ya no será lo suficientemente preciso.
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
Este ejemplo muestra el punto, donde PHP está perdiendo precisión. Primero, el último bit significativo se eliminará, lo que hará que las 2 primeras expresiones resulten en un número igual, lo que no es así.
A partir de AHORA, toda la matemática saldrá mal, cuando se trabaja con tipos de datos predeterminados.
• ¿Es el mismo problema para otros lenguajes interpretados como Python o Perl?
No lo creo. Creo que este es un problema de idiomas que no tienen seguridad de tipos. Si bien se producirá un Desbordamiento de entero como se mencionó anteriormente en todos los idiomas que usen tipos de datos fijos, los idiomas sin seguridad de tipos podrían intentar capturar esto con otros tipos de datos. Sin embargo, una vez que alcanzan su borde "natural" (dado por el sistema), pueden devolver cualquier cosa, pero el resultado correcto.
Sin embargo, cada idioma puede tener diferentes hilos para tal Escenario.
Las otras respuestas ya explicaron lo que está sucediendo aquí (precisión de punto flotante como de costumbre).
Una solución es usar un tipo entero lo suficientemente grande, o esperar que el idioma elija uno si es necesario.
La otra solución es usar un algoritmo de resumen que conozca el problema de precisión y lo solucione. Abajo encontrará la misma suma, primero con un entero de 64 bits, luego con un punto flotante de 64 bits y luego usando el punto flotante nuevamente, pero con el algoritmo de suma Kahan .
Escrito en C #, pero lo mismo se aplica a otros idiomas, también.
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
La suma Kahan da un hermoso resultado. Por supuesto, toma mucho más tiempo para calcular. Si desea usarlo, depende a) de su rendimiento frente a las necesidades de precisión, yb) cómo maneja su idioma los tipos de datos de enteros y de puntos flotantes.
Lo curioso es que PHP 5.5.1 da 499999999500000000 (en ~ 30s), mientras que Dart2Js da 500000000067109000 (que es de esperar, ya que es JS quien se ejecuta). CLI Dart da la respuesta correcta ... al instante.
Mi conjetura es que cuando la suma excede la capacidad de un int nativo (2 32 -1 = 2,147,483,647), Node.js y PHP cambian a una representación de punto flotante y comienza a obtener errores de redondeo. Un lenguaje como Go probablemente tratará de mantener una forma de entero (por ejemplo, enteros de 64 bits) el mayor tiempo posible (si, de hecho, no comenzó con eso). Como la respuesta se ajusta a un entero de 64 bits, el cálculo es exacto.
No tengo suficiente reputación para comentar sobre la respuesta Common Lisp de @ postfuturist, pero se puede optimizar para completar en ~ 500ms con SBCL 1.1.8 en mi máquina:
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
Para el código PHP, la respuesta está here :
El tamaño de un entero depende de la plataforma, aunque un valor máximo de aproximadamente dos mil millones es el valor habitual (es decir, 32 bits con signo). Las plataformas de 64 bits suelen tener un valor máximo de aproximadamente 9E18. PHP no soporta enteros sin signo. El tamaño entero se puede determinar utilizando la constante PHP_INT_SIZE, y el valor máximo utilizando la constante PHP_INT_MAX desde PHP 4.4.0 y PHP 5.0.5.
Para obtener el resultado correcto en php, creo que necesitarías usar los operadores matemáticos de BC: http://php.net/manual/en/ref.bc.php
Aquí está la respuesta correcta en Scala. Tienes que usar Longs, de lo contrario desbordarás el número:
println((1L to 1000000000L).reduce(_ + _)) // prints 500000000500000000
Puerto:
proc Main()
local sum := 0, i
for i := 0 to 1000000000
sum += i
next
? sum
return
Resultados en 500000000500000000 . (en ambas ventanas / mingw / x86 y osx / clang / x64)
Python funciona:
>>> sum(x for x in xrange(1000000000 + 1))
500000000500000000
O:
>>> sum(xrange(1000000000+1))
500000000500000000
El auto de Python promueve a un Python long que admite precisión arbitraria. Producirá la respuesta correcta en plataformas de 32 o 64 bits.
Esto puede verse elevando 2 a una potencia mucho mayor que el ancho de bits de la plataforma:
>>> 2**99
633825300114114700748351602688L
Puede demostrar (con Python) que los valores erróneos que está obteniendo en PHP se debe a que PHP se está promocionando a flotar cuando los valores son mayores que 2 ** 32-1:
>>> int(sum(float(x) for x in xrange(1000000000+1)))
500000000067108992
Quería ver que pasaba en CF Script
<cfscript>
ttl = 0;
for (i=0;i LTE 1000000000 ;i=i+1) {
ttl += i;
}
writeDump(ttl);
abort;
</cfscript>
Tengo 5.00000000067E + 017
Este fue un experimento bastante bueno. Estoy bastante seguro de que podría haber codificado esto un poco mejor con más esfuerzo.
Raqueta v 5.3.4 (MBP; tiempo en ms):
> (time (for/sum ([x (in-range 1000000001)]) x))
cpu time: 2943 real time: 2954 gc time: 0
500000000500000000
Si tienes PHP de 32 bits, puedes calcularlo con php.net/manual/en/book.bc.php :
<?php
$value = 1000000000;
echo bcdiv( bcmul( $value, $value + 1 ), 2 );
//500000000500000000
En Javascript tienes que usar una biblioteca de números arbitrarios, por ejemplo BigInteger :
var value = new BigInteger(1000000000);
console.log( value.multiply(value.add(1)).divide(2).toString());
//500000000500000000
Incluso con lenguajes como Go y Java, eventualmente tendrá que usar una biblioteca de números arbitrarios, su número resultó ser lo suficientemente pequeño para 64 bits pero demasiado alto para 32 bits.
Su código Go usa aritmética de enteros con suficientes bits para dar una respuesta exacta. Nunca toqué PHP o Node.js, pero por los resultados sospecho que los cálculos se realizan con números de punto flotante y, por lo tanto, se debe esperar que no sean exactos para los números de esta magnitud.
Tomó siglos en rubí, pero da la respuesta correcta:
(1..1000000000).reduce(:+)
=> 500000000500000000
Yo uso node-bigint para cosas de enteros grandes:
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);
No es tan rápido como algo que puede usar material nativo de 64 bits para esta prueba exacta, pero si obtiene números mayores que 64 bits, utiliza libgmp debajo del capó, que es una de las bibliotecas de precisión arbitraria más rápidas que existen.