해석 언어에서 매우 큰 정수로 작업 할 때 예기치 않은 결과

lottoking 2020. 5. 12. 08:22

해석 언어에서 매우 큰 정수로 작업 할 때 예기치 않은 결과

의 합을 얻으려고하는데 1 + 2 + ... + 1000000000PHP와 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과 같은 다른 해석 언어도 같은 문제가 있습니까?

파이썬 작동 :

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

또는:

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

파이썬의 int자동 long은 임의의 정밀도를 지원 하는 파이썬으로 승격합니다 . 32 또는 64 비트 플랫폼에서 정답을 생성합니다.

이는 플랫폼의 비트 폭보다 훨씬 큰 2를 2로 올리면 알 수 있습니다.

>>> 2**99
633825300114114700748351602688L

PHP에서 잘못된 값이 2 ** 32-1보다 큰 경우 PHP가 부동으로 승격하기 때문에 오류가 있음을 입증 할 수 있습니다.

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

Go 코드는 정확한 답을 제공하기에 충분한 비트와 함께 정수 산술을 사용합니다. PHP 나 Node.js를 만지지 않았지만 결과에서 수학은 부동 소수점 숫자를 사용하여 수행 된 것으로 생각 되므로이 크기의 숫자에는 정확하지 않아야합니다.

정수 변수의 sum값이 최대 값을 초과 하기 때문입니다 . 그리고 sum당신은 반올림을 포함하는 부동 소수점 산술의 결과입니다. 다른 답변은 정확한 한계를 언급하지 않았으므로 게시하기로 결정했습니다.

다음에 대한 PHP의 최대 정수 값 :

32 비트 버전은 2147483647입니다.
64 비트 버전은 9223372036854775807입니다.

따라서 32 비트 CPU 또는 32 비트 OS 또는 32 비트 컴파일 버전의 PHP를 사용하고 있음을 의미합니다. 를 사용하여 찾을 수 있습니다 PHP_INT_MAX. 는 sum64 비트 컴퓨터에 그것을 할 경우 정확하게 계산 될 것이다.

JavaScript의 최대 정수 값은 9007199254740992 입니다. 당신이 작업 할 수있는 가장 큰 정확한 적분 값은 2 ^53입니다 (이 질문 에서 취함 ). 는 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 비트 정수에 적합하므로 계산이 정확합니다.

펄 스크립트는 우리에게 예상되는 결과를줍니다 :

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가 더 큰 숫자를 만나면 INT 대신 FLOAT를 반환합니다.

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 인 경우 )에서 PHP 수학에서 반환되는 Float 값은 더 이상 정확하지 않습니다.

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가 정밀도를 잃는 지점을 보여줍니다. 첫째, 마지막 significatn 비트가 삭제되어 처음 두 표현식이 같은 수를 얻습니다.

NOW ON부터는 기본 데이터 형식으로 작업 할 때 전체 수학이 잘못됩니다.

파이썬이나 펄과 같은 다른 해석 언어의 경우에도 같은 문제입니까?

나는 그렇게 생각하지 않습니다. 나는 이것이 유형 안전이없는 언어의 문제라고 생각합니다. 위에서 언급 한 정수 오버 플로우는 고정 데이터 유형을 사용하는 모든 언어에서 발생하지만, 유형 안전이없는 언어는 다른 데이터 유형에서이를 포착하려고 시도 할 수 있습니다. 그러나 일단 "자연"(시스템 제공) 경계에 도달하면 올바른 결과를 제외한 모든 것을 반환 할 수 있습니다.

그러나 이러한 시나리오에 따라 언어마다 스레딩이 다를 수 있습니다.

다른 답변은 이미 여기서 일어나는 일을 설명했습니다 (평소와 같이 부동 소수점 정밀도).

한 가지 해결책은 충분히 큰 정수 유형을 사용하거나 필요한 경우 언어가 하나를 선택하기를 희망하는 것입니다.

다른 해결책은 정밀도 문제를 알고 해결하는 합산 알고리즘을 사용하는 것입니다. 아래에서 먼저 64 비트 정수를 사용한 다음 64 비트 부동 소수점을 사용한 다음 부동 소수점을 사용하지만 Kahan 합계 알고리즘 을 사용하여 동일한 합계를 찾습니다 .

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

카한 요약은 아름다운 결과를 제공합니다. 물론 계산하는 데 시간이 오래 걸립니다. 사용 여부는 a) 성능 대 정밀도 요구 사항 및 b) 언어가 정수 대 부동 소수점 데이터 유형을 처리하는 방법에 따라 다릅니다.

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하지만 2.6GHz Intel i7에서는 4 분이 걸립니다.

Magnuss와 Jaunty는 훨씬 더 많은 루비 솔루션을 가지고 있습니다.

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

스칼라의 정답입니다. Longs를 사용해야합니다. 그렇지 않으면 숫자가 오버플로됩니다.

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는 가장 빠르게 해석되는 언어 중 하나이며 기본적으로 임의로 큰 정수를 올바르게 처리합니다. SBCL을 사용 하면 약 3 초가 걸립니다 .

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

By interpreted, I mean, I ran this code from the REPL, SBCL may have done some JITing internally to make it run fast, but the dynamic experience of running code immediately is the same.

I don't have enough reputation to comment on @postfuturist's Common Lisp answer, but it can be optimized to complete in ~500ms with SBCL 1.1.8 on my machine:

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 in ms):

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

Works fine in Rebol:

>> sum: 0
== 0

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

>> type? sum
== integer!

This was using Rebol 3 which despite being 32 bit compiled it uses 64-bit integers (unlike Rebol 2 which used 32 bit integers)

I wanted to see what happened in CF Script

<cfscript>
ttl = 0;

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

I got 5.00000000067E+017

This was a pretty neat experiment. I'm fairly sure I could have coded this a bit better with more effort.

ActivePerl v5.10.1 on 32bit windows, intel core2duo 2.6:

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

result: 5.00000000067109e+017 in 5 minutes.

With "use bigint" script worked for two hours, and would worked more, but I stopped it. Too slow.

For the sake of completeness, in Clojure (beautiful but not very efficient):

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

AWK:

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

produces the same wrong result as PHP:

500000000067108992

It seems AWK uses floating point when the numbers are really big, so at least the answer is the right order-of-magnitude.

Test runs:

$ 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

Category other interpreted language:

Tcl:

If using Tcl 8.4 or older it depends if it was compiled with 32 or 64 bit. (8.4 is end of life).

If using Tcl 8.5 or newer which has arbitrary big integers, it will display the correct result.

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

I put the test inside a proc to get it byte-compiled.

For the PHP code, the answer is here:

The size of an integer is platform-dependent, although a maximum value of about two billion is the usual value (that's 32 bits signed). 64-bit platforms usually have a maximum value of about 9E18. PHP does not support unsigned integers. Integer size can be determined using the constant PHP_INT_SIZE, and maximum value using the constant PHP_INT_MAX since PHP 4.4.0 and PHP 5.0.5.

Harbour:

proc Main()

   local sum := 0, i

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

   ? sum

   return

Results in 500000000500000000. (on both windows/mingw/x86 and osx/clang/x64)

Erlang works:

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

Results: 41> useless:from_sum(1,1000000000). 500000000500000000

Funny thing, PHP 5.5.1 gives 499999999500000000 (in ~ 30s), while Dart2Js gives 500000000067109000 (which is to be expected, since it's JS that gets executed). CLI Dart gives the right answer ... instantly.

Erlang gives the expected result too.

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

And using it:

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

Smalltalk:

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

"500000000500000000"

참고URL : https://stackoverflow.com/questions/18046347/unexpected-results-when-working-with-very-big-integers-on-interpreted-languages

'IT' 카테고리의 다른 글

대화 상자에서 편집 텍스트 상자를 만드는 방법 (0)	2020.05.12
자바 추상 인터페이스 (0)	2020.05.12
텍스트로 옵션을 선택해야하는 선택기는 무엇입니까? (0)	2020.05.12
JQuery를 사용하여 HTML 5 비디오 재생 / 일시 정지 (0)	2020.05.12
각도 2 @ViewChild 주석은 정의되지 않은 값을 반환합니다. (0)	2020.05.12

현재글해석 언어에서 매우 큰 정수로 작업 할 때 예기치 않은 결과

내가 바로 로또왕!

spring, 놀거리, 무비순위, DVD순위, C#, 연극, 영화순위, c++, 관광, jquery, Java, 축제, spring3, 행사, javascript, 공연, 뮤지컬, 여행, 자바, 볼거리,

Today :
Yesterday :

lottoking