임의 정밀도 (bignum) 정수에 대한 곱셈 알고리즘

Question

숙제 프로젝트를위한 작은 bignum 라이브러리를 쓰고 있습니다. Karatsuba 곱셈을 구현할 것이지만 그 전에는 순진한 곱셈 루틴을 작성하고 싶습니다.

"현대 컴퓨터 계산"이라는 제목의 Paul Zimmerman이 작성한 가이드를 따르고 있습니다. freely available online입니다.

페이지 4에는 Gradeschool 곱셈을 수행하는 BasecaseMultiply라는 알고리즘에 대한 설명이 있습니다.

단계 2, 3을 이해합니다. 여기서 B^j는 1, j 배의 자리 이동입니다. 그러나 단계 1과 3을 이해하지 못합니다. 여기에 A * b_j가 있습니다. bignum 곱셈이 아직 정의되지 않았다면이 곱셈은 어떻게 수행 될 것인가?

이 알고리즘의 "*"연산은 반복되는 덧셈 방법일까요?

여기까지 필자가 작성한 부분이 있습니다. 그들은 대부분의 경우 올바른 것으로 보인다, 그래서 나는 단위를 테스트 한 :

다음과 같이 내의 bignum에 사용하는 구조는 다음과 같습니다

#define BIGNUM_DIGITS 2048 
typedef uint32_t u_hw; // halfword 
typedef uint64_t u_w; // word 

typedef struct { 
    unsigned int sign; // 0 or 1 
    unsigned int n_digits; 
    u_hw digits[BIGNUM_DIGITS]; 
} bn; 

현재 루틴 :

bn *bn_add(bn *a, bn *b); // returns a+b as a newly allocated bn 
void bn_lshift(bn *b, int d); // shifts d digits to the left, retains sign 
int bn_cmp(bn *a, bn *b); // returns 1 if a>b, 0 if a=b, -1 if a<b 

Answer 1

I을 잠시 전에 곱셈 알고리즘을 작성했고 맨 위에이 주석이 있습니다. 두 개의 숫자 x와 y가 같은 크기 (같은 n_digits)라면, 이것을 곱하면 n을 얻습니다. 그러면 두 자리 숫자가 생깁니다. 알고리즘의 복잡성 중 일부는 n_digits가 두 입력에 대해 동일하지 않은 경우 어떤 비트가 곱셈되지 않는지를 계산하여 얻습니다.

오른쪽에서부터 n0은 x0 * y0이고 오버플로가 저장되지 않습니다. 이제 n1은 x1 * y0과 y1 * x0의 합계이고 이전 오버플로는 자릿수 크기만큼 이동합니다. 64 비트 수학에서 32 비트 숫자를 사용하는 경우 이는 n0 = low32 (x0 * y0)를 의미하며 오버플로로 high32 (x0 * y0)를 전달합니다. 32 비트 숫자를 실제로 사용한 경우 64 비트를 초과하지 않고 가운데 열을 추가 할 수 없으므로 30 또는 31 비트 숫자를 사용하는 것입니다.

숫자 당 30 비트가있는 경우 두 개의 8 자리 숫자를 함께 사용할 수 있습니다. 먼저이 알고리즘을 작성하여 n_digits가 8 인 두 개의 작은 버퍼를 허용하고 산술에 원시 수학을 사용합니다. 그런 다음 임의의 크기의 n_digits를 사용하고 shift 및 add 메서드와 함께 첫 번째 버전을 사용하여 한 번에 8x8 자릿수를 곱합니다.

/* 
    X*Y = N 

          x0  y3 
          \ / 
          \/ 
           X  
         x1  /|\  y2 
         \ /| \ / 
         \/| \/ 
          X | X  
        x2  /|\ | /|\  y1 
        \ /| \ |/| \ / 
        \/| \|/ | \/ 
         X | X | X  
       x3  /|\ | /|\ | /|\  y0 
       \ /| \ |/| \ |/| \ /
       \/| \|/ | \|/ | \/
        V | X | X | V 
        |\ | /|\ | /|\ | /| 
        | \ |/| \ |/| \ |/| 
        | \|/ | \|/ | \|/ | 
        | V | X | V | 
        | |\ | /|\ | /| | 
        | | \ |/| \ |/| | 
        | | \|/ | \|/ | | 
        | | V | V | | 
        | | |\ | /| | | 
        | | | \ |/| | | 
        | | | \|/ | | | 
        | | | V | | | 
        | | | | | | | 
       n7 n6 n5 n4 n3 n2 n1 n0 
*/ 

Answer 2

A * b_j를 수행하려면 bignum을 한자리 숫자로 곱하는 초등학교 배정을 수행해야합니다. 2 자리 제품을 함께 추가해야합니다.

bn *R = ZERO; 
for(int i = 0; i < n; i++) { 
    bn S = {0, 2}; 
    S.digits[0] = a[i] * b_j; 
    S.digits[1] = (((u_w)a[i]) * b_j) >> 32; // order depends on endianness 
    bn_lshift(S, i); 
    R = bn_add(R, S); 
} 

물론 이것은 매우 비효율적입니다.