2017-12-22 22 views
1

볼륨 2의 섹션 4.3.2의 알고리즘 D를 의 컴퓨터 프로그래밍의 D. E. Knuth가 구현했습니다.Knuth long division 알고리즘

단계 D3에서 q = floor(u[j+n]*BASE+u[j+n-1]/v[n-1])r = u[j+n]*BASE+u[j+n-1] mod v[n-1]을 계산해야합니다. 여기에서 u (배수) 및 v (제수)는 길이가 각각 m+nn 인 단 정밀도 * 배열입니다. BASE은 32 비트 또는 64 비트의 이진 컴퓨터에 대해 각각 2^32 또는 2^64와 동일한 표현 기반입니다.

제 질문은 qr의 정밀도에 대한 것입니다. 알고리즘의 나머지 부분을 이해함에 따라 단 정밀도 *로 간주되지만 결과에 맞게 배정도 *가 필요한 많은 경우를 쉽게 찾아 낼 수 있습니다.

이러한 값은 어떻게 계산 되나요? 어떤 정밀도?

* 단 정밀도/배정 밀도는 부동 소수점 연산이 아니라 정수 계산을 나타냅니다.

답변

0

제수가 정규화되면 (최상위 비트가 설정 됨) 몫은 항상 단일 단어에 맞습니다. 2 개의베이스 표현의 힘으로, 표준화는 값싼 왼쪽 쉬프트 연산에 의해 수행됩니다.

Link to a more detailed and formal answer.