루프 계산 반복 관계가 매우 오래 걸림

Question

Q(x)=[Q(x−1)+Q(x−2)]^2 
Q(0)=0, Q(1)=1 

Q (29)를 찾아야합니다. 파이썬으로 코드를 작성했지만 너무 오래 걸립니다. 출력을 얻는 방법 (모든 언어는 괜찮을 것입니다)? 무한대 기하 급수적의 일종이기 때문에 이것은, 너무 오래 걸릴 것

a=0 
b=1 
for i in range(28): 
    c=(a+b)*(a+b) 
    a=b 
    b=c 
print(b) 

Answer 1

: 여기

내가 쓴 코드입니다.

예 : C % 다음 10 == 0과 그것을 나눈다면

a=0 

b=1 

c=1*1 = 1 

a=1 

b=1 

c=2*2 = 4 

a=1 

b=4 

c=5*5 = 25 

a=4 

b=25 

c= 29*29 = 841 

a=25 

b=841 

. 
. 
. 

Answer 2

당신은 확인할 수 있으며, 시간의 끝 multiplyit 번호를 당신이 그것을 나누어 그러나 결국은 큰 같은 수 있습니다 번호. 이 계산을 정말로해야한다면 C++을 사용해보십시오. Python보다 빨리 실행해야합니다.

---

다음은 C로 작성된 코드 ++ 나는이 프로그램을 가진 다루기 쉬운 문제라고 생각하지 않습니다

#include <cstdlib> 
#include <iostream> 

using namespace std; 

int main(int argc, char *argv[]) 
{ 
    long long int a=0; 
    long long int b=1; 
    long long int c=0; 
    for(int i=0;i<28;i++){ 
      c=(a+b)*(a+b); 
      a=b; 
      b=c; 
    } 

    cout << c; 
    return 0; 
} 

Answer 3

입니다. 코드가 느린 이유는 숫자가 으로 매우 빠르게으로 증가하고 파이썬은 무한 정밀도 정수를 사용하기 때문에 결과를 계산하는 데 시간이 걸립니다.

배정 밀도 수레와 코드를보십시오 :

이

a=0.0 
b=1.0 
for i in range(28): 
    c=(a+b)*(a+b) 
    a=b 
    b=c 
print(b) 

대답은 inf입니다. 이는 대답이 가장 큰 표현 가능한 배정 밀도 숫자 인 rougly 10^308보다 훨씬 크기 때문입니다. 유한 정밀도 정수를 사용해 볼 수도 있지만, 표현할 수있는 최대 값은 훨씬 작습니다. 복식을 사용하면 정밀도가 떨어질 수 있지만 분명히 당신의 huuuge 번호의 모든 한자리 수를 알고 싶지는 않습니다 (보조 메모 : I happen to know that you do, 직장을 더욱 어렵게 만듭니다).

그래서 여기 내 회의론에 대한 몇 가지 수학 배경 : 당신이 해결할 수있는 경우

P[k] = sqrt(Q[k]) 
P[k] = P[k-2]^2 + P[k-1]^2 

: 귀하의 재발 관계가

Q[k] = (Q[k-2] + Q[k-1])^2 

당신은이 순서의 제곱근에서 더 다루기 쉬운 순서를 공식화 할 수 있습니다 간다 P의 경우 Q = P^2을 알게 될 것입니다. 이제

,이 순서 고려해

R[k] = R[k-1]^2 

같은 초기 값에서 시작을, 이것은 항상

P[k] = P[k-2]^2 + P[k-1]^2 >= P[k-1]^2 

때문에, P[k]보다 작아야합니다 (그러나 이것은 "아주 가까이"입니다 첫 번째 용어와 같은 하한은 두 번째 용어와 비교할 때 항상 중요하지 않습니다., 값 2

R[k] = R[k-1]^2 = R[k-2]^4 = R[k-3]^6 = R[k-m]^(2^m) = R[0]^(2^k) 

P[1 give or take]부터 시작, 우리는 P[k]에 대한 하한으로

R[k] = 2^(2^k) 

을 고려해야한다 제공하거나 이것이 k=28 2. 몇 지수를 가지고 : 우리는이 순서를 만들 수 있습니다 squar가 P의 최종 값에 대해 적어도 80807124 숫자이다

P[28] > 2^(2^28) = 2^(268435456) = 10^(log10(2)*2^28) ~ 10^80807124 

당신이 찾고있는 번호의 루트. 이로 인해 Q[28]은 10^1.6e8보다 커집니다. 이 번호를 텍스트 파일에 인쇄하면 150 메가 바이트 이상이 소요됩니다.

이러한 정수를 정확히 처리하려고한다고 생각하면 왜 그렇게 오래 걸리는 이유와 왜 접근 방식을 재고해야하는지 알 수 있습니다. 그 엄청난 숫자를 계산할 수 있다면 어떨까요? 너는 그걸로 무엇을 할 것인가? 화면에 그 숫자를 프린트하는 데 파이썬이 얼마나 걸릴까요? 이 중 어느 것도 사소한 것이 아니므로, 종이에 문제를 해결하거나 문제를 해결하는 방법을 찾으십시오. 당신이 파이썬에서 sympy와 같은 상징적 인 수학 패키지를 사용할 수 있습니다

---

참고 문제가 얼마나 힘든 느낌 얻을 :

import sympy as sym 
a,b,c,b0 = sym.symbols('a,b,c,b0') 
a = 0 
b = b0 
for k in range(28): 
    c = (a+b)**2 
    a = b 
    b = c 
print(c) 

이 시간이 걸릴 것이다, 그러나 그것은 채울 것이다 화면에서 b0을 매개 변수로 사용하는 Q[k]의 명시 적 표현식을 사용하십시오. 정확한 결과를 얻으려면 그 몬스터로 값을 대체해야합니다. 표현식에 sym.simplify을 시도해 볼 수도 있지만 의미있는 결과를 반환 할 때까지 기다릴 수 없습니다.

---

점심 시간 동안 나는 루프를 돌리고 완료되었습니다. 그 결과가

>>> import math 
>>> print(math.log10(c)) 
49287457.71120789 

그래서 내 낮은 k=28위한 행 조금 큰, 아마도 오프별로 한 지수의 오류. 이 정수를 저장하는 데 필요한 메모리는 대략 20MB 인이 정수를 저장하는 데 필요한 메모리는

>>> import sys 
>>> sys.getsizeof(c) 
21830612 

입니다.

Answer 4

이것은 무차별 대입으로 해결할 수 있지만 두 가지 "느린"연산을 사용하고 올바른 접근 방식을 선택하는 데있어 상충 관계가 있으므로 여전히 흥미로운 문제입니다.

파이썬 구현이 느린 곳은 두 곳입니다 : 큰 숫자의 곱셈과 큰 숫자의 문자열로의 변환.

파이썬은 곱하기에 Karatsuba 알고리즘을 사용합니다. 실행 시간은 O (n^1.585)이며, 여기서 n은 숫자의 길이입니다. 숫자가 커짐에 따라 느려지지만 Q (29)를 계산할 수 있습니다.

파이썬 정수를 10 진수 표현으로 변환하는 알고리즘은 훨씬 느립니다. 실행 시간은 O (n^2)입니다. 큰 숫자의 경우 곱셈보다 훨씬 느립니다.

참고 : 문자열로 변환하기위한 시간에는 실제 계산 시간도 포함됩니다.

컴퓨터에서 Q (25)를 계산할 때 ~ 2.5 초가 필요하지만 문자열로 변환하는 데 ~ 3 분 9 초가 필요합니다. Q (26) 계산에는 ~ 7.5 초가 필요하지만 문자열로의 변환에는 ~ 12 분 36 초가 필요합니다. 숫자의 크기가 두 배가되면 곱셈 시간은 3 배 증가하고 문자열 변환의 실행 시간은 4 배 증가합니다. 문자열로의 변환 실행 시간이 지배적입니다. 컴퓨팅 Q (29)는 약 3 분 20 초가 소요되지만 문자열로 변환하는 데는 12 시간 이상이 걸릴 것입니다. (실제로 그렇게 오래 기다리지는 않았습니다).

매우 편리한 GMP 라이브러리에 액세스 할 수있는 모듈은 gmpy2입니다. gmpy2을 사용하면 Q (26)을 ~ 0.2 초 내에 계산할 수 있고 ~ 1.2 초 내에 문자열로 변환 할 수 있습니다. Q (29)는 ~ 1.7 초 내에 계산되고 ~ 15 초 내에 문자열로 변환 될 수 있습니다. GMP에서의 곱셈은 O (n * ln (n))입니다. 십진수로의 변환은 Python의 O (n^2) 알고리즘보다 빠르지 만 여전히 곱셈보다 느립니다.

가장 빠른 옵션은 Python의 decimal 모듈입니다. radix-2 또는 2 진 내부 표현을 사용하는 대신 radix-10 (실제로는 10의 제곱) 내부 표현을 사용합니다. 계산은 약간 느리지 만 문자열로의 변환은 매우 빠릅니다. 그것은 단지 O (n)입니다. Q (29) 계산에는 ~ 9.2 초가 필요하지만 계산과 변환을 함께 수행하는 데는 ~ 9.5 초 밖에 걸리지 않습니다. 문자열로 변환하는 시간은 불과 0.3 초입니다.

다음은 decimal을 사용한 예제 프로그램입니다. 또한 최종 값의 개별 자릿수를 합합니다.

import decimal 

decimal.getcontext().prec = 200000000 
decimal.getcontext().Emax = 200000000 
decimal.getcontext().Emin = -200000000 

def sum_of_digits(x): 
    return sum(map(int, (t for t in str(x)))) 

a = decimal.Decimal(0) 
b = decimal.Decimal(1) 
for i in range(28): 
    c = (a + b) * (a + b) 
    a = b 
    b = c 


temp = str(b) 
print(i, len(temp), sum_of_digits(temp)) 

수백만 자릿수를 문자열로 변환하고 위의 설명에 추가하는 시간은 포함되지 않았습니다. 그 시간은 각 버전마다 동일해야합니다.