정수 나누기 7

Question

추이 내 대답에 :

Is this expression correct in C preprocessor

여기 내 장점 중 조금 해요, 나는 방법이 특정 최적화 작품을 이해하려고 노력 중이 야.

이 질문에 대해 언급 한 바와 같이

, GCC는 7에 의해 정수 나누기를 최적화 :로 C로 다시 변환

mov edx, -1840700269 
mov eax, edi 
imul edx 
lea eax, [rdx+rdi] 
sar eax, 2 
sar edi, 31 
sub eax, edi 

:

int32_t divideBySeven(int32_t num) { 
    int32_t temp = ((int64_t)num * -015555555555) >> 32; 
    temp = (temp + num) >> 2; 
    return (temp - (num >> 31)); 
} 

이의 첫 번째 부분을 살펴 보자 :

를

int32_t temp = ((int64_t)num * -015555555555) >> 32; 

왜이 번호입니까?

음, 2^64를 7로 나누고 튀어 나오는 것을보십시오.

2^64/7 = 2635249153387078802.28571428571428571429 

마치 엉망으로 보입니다. 8 진수로 변환하면 어떻게 될까요?

0222222222222222222222.22222222222222222222222 

그건 아주 우연한 일치 패턴이 아닙니다. 우연의 일치는 아닙니다. 저는 우리가 7이 0b111이라는 것을 기억하고 우리가 99로 나눌 때 10 진수로 반복되는 패턴을 얻는 경향이 있다는 것을 알고 있습니다. 따라서 7으로 나눌 때 8 진수로 반복되는 패턴을 얻을 수 있습니다.

번호가 어디서 들어 왔습니까?

(int32_t)-1840700269는 (uint_32t)2454267027

* 7 = 17179869189

과 동일하며 마지막 17179869184 17179869189 7은 2^34의 배수에 가장 가까운 것을 의미 2^34

이다. 아니면 다른 방법 2454267027 7 곱하면이 숫자는 8 진수 무엇 2

의 전력에 매우 가까운 uint32_t에 맞는 가장 큰 숫자가 넣어?

0222222222223 

왜 이것이 중요한가요? 음, 우리는 7로 나누고 싶습니다.이 숫자는 2^34/7 ... 대략입니다. 그래서 우리가 곱한 다음 34 번 왼쪽으로 시프트하면 정확한 숫자에 아주 가까운 숫자를 얻어야합니다.

마지막 두 줄은 근사 오차를 패치하도록 설계된 것처럼 보입니다.

아마이 분야에 대한 지식 및/또는 전문 지식이 조금있는 사람이이 문제를 확인할 수 있습니다.

>>> magic = 2454267027 
>>> def div7(a): 
... if (int(magic * a >> 34) != a // 7): 
...  return 0 
... return 1 
... 
>>> for a in xrange(2**31, 2**32): 
... if (not div7(a)): 
...  print "%s fails" % a 
... 

실패는 근사 나를 넘어 비트가 실패하는 이유 분류 충분히 재미있게 0b11001100110011001100110011010001

입니다 3,435,973,841에서 시작하고, 패치를 고쳐 이유도있다.누가 여기에 내려 놓은 것 이상으로 마법이 작동하는지 어떻게 알 수 있습니까?

Answer 1

알고리즘의 첫 번째 부분은 역수로 7을 곱합니다.이 경우 정수 곱하기와 오른쪽 비트 시프트를 사용하여 역수를 계산합니다.

먼저 32 비트 정수로 -1840700269 (8 진수 -015555555555) 값을 확인합니다. 이것을 부호없는 32 비트 정수로 읽으면 값이 2454267027 (8 진수 22222222223)이됩니다. 2454267027/2^34은 1/7에 매우 근접한 근사치입니다.

왜이 숫자와이 2의 거듭 제곱을 선택합니까? 우리가 사용하는 정수가 클수록 근사값은 가깝습니다. 이 경우 2454267027이 64 비트 int를 오버플로하지 않고 부호있는 32 비트 int를 곱할 수있는 가장 큰 정수 (위의 특성을 충족) 인 것 같습니다.

다음으로 오른쪽으로 >> 34으로 바로 이동하고 결과를 32 비트 정수로 저장하면 가장 낮은 두 자리 비트의 정확도가 떨어집니다. 이러한 비트는 정수 나누기에 적합한 바닥을 결정하는 데 필요합니다.

두 번째 줄이 x86 코드에서 올바르게 번역되었는지 잘 모르겠습니다. 이 시점에서 temp은 약 num * 4/7이므로 num * 4/7 + num과 비트 시프트는 약 num * 1/7 + num * 1/4으로 매우 큰 오류입니다.

예를 들어, 입력 57을 사용하십시오 (여기서 57 // 7 = 8). 나뿐만 아니라 코드에서 아래의 확인 :

• 57 * 2454267027 = 139893220539
• 139893220539 >> 32 = 32 (약 57 * 4/7 = 32.5714...이 시점에서)를
• 32 + 57 = 89
• 89 >> 2 = 22
(응?이 시점에서 8 곳 부근에 있습니다.)

어쨌든, 마지막 줄에서는이 방법으로 부호있는 정수 나누기를 계산 한 후 조정합니다. 나는 서명 부문에 해커의 기쁨에서 섹션에서 인용 :

코드는 자연스럽게 바닥 분할 결과를 계산하고, 그래서 우리는 0 결과를 향해립니다 기존의를 계산하기 위해 보정이 필요합니다. 배당금이 음수이면 배당금에 더하기로 계산하는 세 가지 계산 방법으로 을 수행 할 수 있습니다.

이 경우 (다른 게시물 참조) 부호있는 시프트를 수행 한 것으로 보입니다. 따라서 음수 일 경우 -1을 뺍니다. +1의 결과를 제공합니다.

이것은 모두 할 수있는 것이 아닙니다. 여기 심지어 더 미친 사람이 blog post about how to divide by 7 with just a single multiplication입니다.