십진수 bignum을 사용한 나눗셈 알고리즘

Question

편집 : 내 bignum 클래스를 리베이스하여 std::bitset을 사용하고 방금 벌금을 잘 구현했습니다. 나는 비트를 저장할 클래스를 모른다. (std::bitset)

나는 내부 표현으로 십진수를 사용하기 위해 std::string으로 bignum 클래스를 만들고 있습니다.

while N ≥ D do N := N - D end return N

을 물론 그것은 느렸다 : 나는 간단한 알고리즘 부문을 구현했습니다. 나는 long division을 구현하려고 시도했으나 소수 문자로하기에는 너무 어려웠습니다.

미리 감사드립니다.

Answer 1

D를 매우 자주 빼는 대신 D^2n 형식의 가장 높은 값을 찾고 하위를 찾으려고 할 수 있습니다. 나머지까지 나머지 값 단계 이상 반복

D.

미만 의사 코드를

0 result=0 
1 powerOfD = D 
2 while (powerOfD*powerOfD<N) 
3 powerOfD=powerOfD*powerOfD 
4 result = result+powerOfD/D, N=N-powerOfD; 
5 if(N>D) 
6 goto 1 
7 return result 

예 31/3 (N = 31, D = 3)

0 result=0 
1 powerD = 3; 
2 3*3 < 31 TRUE 
3 powerOfD= 3*3; 
2 9*9 < 31 FALSE 
4 result=0+9/3; N=31 - 9 
5 22> 3 TRUE 
6 goto 1 
1 powerD = 3 
2 3*3 < 22 TRUE 
3 powerOfD= 3*3; 
2 9*9 < 31 FALSE 
4 result=3+9/3; N=22 - 9 
5 13> 3 TRUE 
6 goto 1 
1 powerD = 3 
2 3*3 < 13 TRUE 
3 powerOfD= 3*3; 
2 9*9 < 31 FALSE 
4 result=6+9/3; N=13 - 9 
5 4> 3 TRUE 
6 goto 1 
1 powerD = 3 
2 3*3 < 4 ALSE 
4 result=9+3/3; N=4-3 
5 1> 3 FALSE 
7 return 10