매우 큰 숫자를 나누는 알고리즘

Question

나누기 (정수 구분, 부동 부분은 중요하지 않음) 알고리즘 (100-1000 자리와 같이 매우 큰 수)을 작성해야합니다 (할당되기 때문에 제 3 자 라이브러리를 사용할 수 없음). . http://en.wikipedia.org/wiki/Fourier_division 알고리즘을 찾았지만 올바른 방향인지는 알 수 없습니다. 의견 있으십니까? 과제의 일부가 완전히 원래의 것이 었하지 않는 한

1) check divisior < dividend, otherwise it's zero (because it will be an int division) 
2) start from the left 
3) get equal portion of digits from the dividend 
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1 
5) multiply divisor by 1-9 through the loop 
6) when it exceeds the dividend portion, previous multiplier is the answer 
7) repeat steps 3 to 5 until reaching to the end 

Answer 1

크 누스, 도널드, 컴퓨터 프로그래밍의 예술, ISBN 0-201-89684-2, 볼륨 2 : Seminumerical 알고리즘, 섹션 4.3.1 : 고전 알고리즘

Answer 2

, 나는 알고리즘 I에 갈 것이다 (그리고 나는 당신을 가정) 손으로 큰 부문을 수행하기위한 초등학교에서 배웠다.

Answer 3

나는 '초등 학교에서와 같이'긴 길을 나누는 것이 잠재적 인 길 일 것이라고 생각합니다. 원래 숫자를 문자열로 받는다고 가정하고 있으므로 각 숫자를 구문 분석하면됩니다. 예 :

단계 0 :

/----------------- 
13 | 453453453435.... 

1 단계 : "얼마나 많은 시간 (13)는 4 0

 0 
    /----------------- 
13 | 453453453435.... 

2 단계로 이동 않습니다"(13)는 45에 몇 번 가는가? 3

 03 
    /----------------- 
13 | 453453453435.... 
    - 39 
    -- 
     6 

3 단계 : "얼마나 많은 시간 (13)이 전략을 63 4

등 등으로 이동 않습니다, 당신은 어떤 수의 길이 만 정말 메모리에 충분한 숫자를 개최 할 수 있습니다 int (제수)와 double (배당)입니다. (이 조건을 올바르게 가정하면) 결과 문자열의 마지막 숫자로 결과를 저장합니다.

숫자가없고 계산이 발생하지 않는 지점에 도달하면 1 번 이상 들어가면 이미 문자열로 포맷 된 결과를 반환합니다 (잠재적으로 int보다 클 수 있기 때문).

Answer 4

당신은 아마 긴 나눗셈 식으로 뭔가를 시도해야하지만 숫자 대신 컴퓨터 단어를 사용합니다.

고급 언어에서는 가장 큰 고정 소수점 정수의 절반 인 "숫자"를 고려하는 것이 가장 편리합니다. 장 구간 분할 방법의 경우 고정밀 분할이 임의 정밀도 제수의 가장 중요한 부분 만 처리 할 수 ​​있기 때문에 부분 중간 결과가 1만큼 벗어날 수있는 경우를 처리해야합니다.

임의 정밀도 산술을 수행하는 더 빠르고 더 복잡한 방법이 있습니다. 적절한 wikipedia page을 확인하십시오. 특히, Newton-Raphson 방법은주의 깊게 구현 될 때 부서의 시간 성능이 임의 정밀도 곱셈의 일정한 요소 내에 있음을 보장 할 수 있습니다.

Answer 5

큰 수를 구현하는 가장 쉬운 나누기 알고리즘은 shift와 subtract입니다.

if numerator is less than denominator then finish 
shift denominator as far left as possible while it is still smaller than numerator 
set bit in quotient for amount shifted 
subtract shifted denominator from numerator 
repeat 
the numerator is now the remainder 

전환은 리터럴 일 필요는 없습니다. 예를 들어, 빼기 전에 전체 값을 실제로 이동하는 대신 왼쪽으로 이동 한 값을 다른 값에서 빼는 알고리즘을 작성할 수 있습니다. 비교를 위해서도 마찬가지입니다.

긴 구분의 단계 중 하나가 긴 구분이므로 긴 구분을 구현하기가 어렵습니다. 제수가 int이면, 당신은 꽤 쉽게 쉽게 나누어집니다.