매우 큰 카운터 번호에 대한 실행 시간에 대해 간단한 질문이 있습니다

카운터에 대한 최대 크기에 대한 간단한 질문이 있습니다. 예를 들어 다음 코드는 적어도 2^512의 산술 연산이 필요하거나 본질적으로 i 2^512 번 값을 변경해야하기 때문에 reasonalbe 시간에 수행 할 수 없어야합니다!매우 큰 카운터 번호에 대한 실행 시간에 대해 간단한 질문이 있습니다

c = 2 to the power 512; 
for (i = 1, i < c, i++) { 
    j = j + 1/(i * i + 1);  

}

그러나 컴퓨터 대수 소프트웨어 "Mathematica"를 사용하면 1 초 미만의 대답을 얻을 수 있습니다. 제 질문은 어떻게 이것을 성취 할 수 있겠습니까?

ps. 카운터 크기에 대한 나의 순진한 생각은 복잡성에 대한 제 의견에 기인합니다. 복잡성에 대한 산술 연산의 복잡성에만 초점을 맞추기 때문에 너무 형식적이지 않은 책을 읽을 때 색인의 비용은 항상 생략됩니다. 나는 카운터가 작은 경우에만 이것을 상상할 수 있습니다.

출처

2011-04-09 user565739

확실히 루프가 i == 1에서 i == 513으로 이동하지 않습니다. 샘플 코드는 어떤 언어입니까? C/C++에서'2^512'는 확실히 514를 산출합니다. – 0xC0000022L

C/C++에서 검사하지 않았습니다. 나는 2^512의 입력 크기가 단지 512라는 것을 알고있다. 그러나 카운터 i에 나타나기 때문에 1에서 2^512까지 실행되어야한다. 즉, 명령 j = j + 1/(i * i + 1) 2^512 시간 동안, 그렇지 않습니까? – user565739

루프 종료 조건이 2^512로 고정되어 있기 때문에 Mathematica는이를 합산 된 기하학적 시퀀스로 처리 할 수 있으므로 모든 루프 값을 반복하지 않고 수식을 사용하여 계산할 수 있습니다.

위키 백과 항목 Geometric Progression과 볼프람 페이지 Geometric Series을 살펴보십시오.

정상적인 프로그래밍 언어 인 경우 C++, Java 또는 C#과 같이 절대적으로 옳습니다! 또한 2^512는 매우 큰 숫자이며 해당 언어의 "일반"데이터 유형을 오버플로합니다.

2의 거듭 제곱을 2x 또는 512가 아닌 514라고 가정합니다.

출처

2011-04-09 21:50:37

감사합니다. 그래서 C/C++의 모든 프로그램에서 ... 우리는 카운터의 최대 크기가 2^128 또는 2^256보다 많지 않습니까? – user565739

C++에서 2^512는 실제로 2 XOR 512를 의미하며 512의 힘에는 2가 아니라는 것을 의미하므로 명확하게 의미하는지 확인하십시오. 2 XOR 512는 큰 수가 아닙니다 !! 전 당신이 후자가 아니라 전을 의미한다고 가정하고있었습니다. –

또한 언급 한 시리즈는 기하학적 인 것이 아닙니다. 하지만 그것은 이런 종류의 시리즈에 대한 수식을 가지고 있습니다 .... – user565739

매우 큰 카운터 번호에 대한 실행 시간에 대해 간단한 질문이 있습니다

답변

관련 문제