Karatsuba 알고리즘 오버플로

Question

나는 Karatsuba's algorithm on Wikipedia 을 연구 해왔다. 나 혼란 스러웠다. 왜이 알고리즘에 오버플로가 있었는지, 나는이 문제를 해결하기 위해 그가 만든 단계를 이해하지 못했다. 내 문제의 스크린 샷은

Answer 1

는 않을까에만 스타터 양수을 고려하십시오. 8 비트 숫자/숫자 x0,x1,y0,y1을 가질 수 있습니다.

x0*y0 -> 8bit * 8bit -> 16 bit 

그것은 16 비트 결과까지 생산됩니다

우리는 8 비트 곱셈을 적용합니다. 최고 값은 다음과 같습니다

FFh*FFh = FE01h 
255*255 = 65025 

이제 우리는 카라 츠바에

X = x0 + x1<<8 
Y = y0 + y1<<8 
Z = X*Y = z0 + z1<<8 + z2<<16 

지금 zi

z2 = x1*y1   -> 16 bit 
z1 = x1*y0 + x0*y1 -> 17 bit 
z0 = x0*y0   -> 16 bit 

주 z1 그의 비트 폭 볼 수 있도록 돌아 오면됩니다 상단으로 17 비트 값은

65025+65025 = 130050 

따라서 각 zi은 8 비트를 오버플로합니다. 이를 처리하기 위해 가장 낮은 8 비트 만 취하고 나머지는 더 높은 자리에 더합니다 (캐리 전파와 같음). 그래서 :

z1 += z0>>8; z0 &= 255; 
z2 += z1>>8; z1 &= 255; 
z3 = z2>>8; 
Z = z0 + z1<<8 + z2<<16 + z3<<24 

그러나 일반적으로 HW 구현은 자체적으로 이것을 처리하고 결과를 하나가 아닌 두 단어로 제공합니다.

따라서 16 비트 곱셈의 결과는 32 비트입니다. 8 비트 하위 결과를 추가하는 경우 3 개의 숫자를 함께 추가하거나 9 비트 (또는 8 비트 + 1 자리 올림)를 하나씩 추가하고 전파 할 때 최소 10 비트가 필요합니다.

부호가있는 값을 여기에 추가하려면 부호를 위해 또 하나의 비트가 필요합니다. 그것을 피하려면 피연산자의 기호를 기억하고 abs 값을 사용하십시오 ... 그리고 원래 기호에 따라 결과의 부호를 설정하십시오.

• C++ 32bit * 32bit multiplication without asm
• Fast bignum square computation