반복의 효율성 대 지수의 반복

Question

그래서 나는 2^n을 계산하는보다 효율적인 방법을 구현하려고합니다.

나는 이것을 O(logn)이되도록 분할 할 수 있으며 재귀를 사용하여 쉽게 할 수 있음을 알고 있습니다. 당신은 2로 나누기를 계속하고 그것의 이상 (또는 그런 것)이있을 때 그것을 더 낮은 힘으로 곱하십시오. 문제는 큰 숫자에 대한 곱셈 방법을 손으로 썼다는 것입니다. 따라서 하나 이상의 매개 변수를 반환해야합니다.

제가 생각할 수있는 한 가지 해결책은 모든 필요한 정보가 포함 된 쌍을 만드는 것입니다. 그 외에도 반복을 사용하여 작성하는 방법을 알아 내려고 노력했습니다. 내가 볼 수있는 유일한 방법은 일종의 데이터 구조를 사용하고 n을 2로 나누고 n이 홀수 일 때 값을 저장하는 것입니다. 그런 다음 for 루프를 작성하고 값이 데이터 구조에 포함되어 있으면 각 반복마다 점검하십시오. 이것은 비교적 비용이 많이 드는 작업처럼 느껴집니다.

재귀 버전보다 효율성이 떨어질 가능성이 있습니까?

1. 내가 얻을 수없는 한나라당 작업 :

   나는이 때문에하고 있어요.

2. 큰 숫자 클래스를 작성하고 함께 작업하는 것을 배우고 있다고 생각합니다.

Answer 1

큰 숫자로 작업하려면 바퀴를 다시 열지 말고 GNU MP Bignum Library을 살펴보십시오.

재귀 대 반복 질문과 관련하여 답은 언제나 동일하게 작성 될 수 있다는 것입니다. tail call으로 만 호출하는 재귀 함수는 while 루프만큼 효율적입니다 (, 컴파일러에서 꼬리 호출 최적화를 지원하지만 가장 일반적인 컴파일러는을 제공). 예를 들어, 당신이 묘사하는 빠른 지수 함수의 꼬리 재귀 버전 (의사 코드)입니다 :

function fastExp(base, exponent, accumulator) { 
    if(exponent == 0) { 
    return accumulator; 
    } else if(exponent % 2 == 0) { 
    return fastExp(base * base, exponent/2, accumulator); 
    } else { 
    return fastExp(base, exponent-1, base * accumulator); 
    } 
} 

루핑 조건이 exponent != 0이다 루프 등이 재귀 함수를 생각하고, 재귀 호출은 루프 시작 부분에 goto과 같습니다. (당신은 당신이 시작할 때 그런데, accumulator = 1로를 호출해야합니다.) 그것은 다음과 동일하다 :

function fastExp(base, exponent) { 
    var accumulator = 1; 
    while(exponent != 0) { 
    if(exponent % 2 == 0) { 
     base *= base; 
     exponent /= 2; 
    } else { 
     exponent -= 1; 
     accumulator *= base; 
    } 
    } 
    return accumulator; 
} 

그래서 당신은 그들이 동일하다는 것을 볼 수있다, 따라서 작업의 같은 번호를 수행합니다.

Answer 2

하면 1의 시퀀스와 0 s..ie 전부를 저장하는 경우. 바이너리 형식에서 2^N 단순히 단일 한 앞에는 0 S의 서열이다 이것이 내가 필립

0,123,516을 제안 것 같은 표준 임의 정밀도 라이브러리와 함께 갈 것입니다 학습 운동은하지 않는는, 어쩌면 당신은, 등

2^1 = 10 
2^2 = 100 
2^3 = 1000 
2^4 = 10000 

등 단순히 코드에 사실을 사용할 수 있습니다