大整數算法[12] 有符號乘法，整數乘法

大整數算法[12] 有符號乘法，整數乘法

        ★ 引子

        前面三篇文章講了 Comba 乘法和 Karatsuba 乘法，有了這兩個算法，就可以很輕松的構造有符號數乘法。

        順便提一下：講 Comba 乘法的實現的時候，給出了 x86 環境下的內聯匯編實現，最近添加了 GCC x64 環境的內聯匯編，已經補充到帖子當中。

        ★ 實現

        有符號數的乘法，基本實現是這樣：大的整數用 Karatsuba 乘法搞定，小的整數用 Comba 乘法搞定。對於大的整數，Karatsuba 乘法會不斷遞歸計算，直到輸入的整數小到一定規模，就改用 Comba 方法直接計算，這樣的話，既可以降低乘法的時間復雜度，但又不會在小整數上花過多的時間計算。具體的實現代碼如下：

int bn_mul_bn(bignum *z, const bignum *x, const bignum *y)
{
    int ret;
    bignum ta[1], tb[1];

    bn_init(ta);
    bn_init(tb);

    if(BN_MIN(x->used, y->used) >= KARATSUBA_MUL_CUTOFF)
    {
        BN_CHECK(bn_mul_karatsuba(z, x, y));
    }
    else
    {
        if(x == z)
        {
            BN_CHECK(bn_copy(ta, x));
            x = ta;
        }
        if(y == z)
        {
            BN_CHECK(bn_copy(tb, y));
            y = tb;
        }

        BN_CHECK(bn_grow(z, x->used + y->used));
        BN_CHECK(bn_set_word(z, 0));
        z->used = x->used + y->used;

        bn_mul_comba(z, x, y);
        z->sign = (x->sign == y->sign) ? 1 : -1;
    }

clean:
    bn_free(ta);
    bn_free(tb);

    return ret;
}

       算法一開始會檢查輸入的 x 和 y 的大小，如果 x 和 y 的數位都大於或等於分割點 KARATSUBA_MUL_CUTOFF，就使用 Karatsuba 乘法進行計算，否則使用 Comba 方法。

       使用 Comba 方法的時候，先增加目標結果的精度，以便能夠無損地存儲計算結果，然後把 z 設為 0，調用 Comba 方法的函數進行計算，最後設置符號位（同號得正，異號得負）。所有計算完成後，清除臨時變量的內存。由於 ta 和 tb 一開始就初始化了，所以即使沒有分配內存，在清除的時候也不會出錯。

       在使用 Comba 方法時，為了處理輸入和輸出是同一個變量的情況（x = x * y，y = x * y，x = x * x，y = y * y），需要使用臨時變量 ta 和 tb。當有這種情況發生時，先把輸入的整數拷貝到臨時變量中，然後再把 x 或 y 指向 ta 或 tb，這樣就避免了在計算中把 x 或 y 置為 0（因為 z 一開始會被設為 0）。

        ★ 總結

        因為有了前面的鋪墊，所以這個算法沒有什麼好講的。下一篇講講講單數位乘法，單數位乘法不能按照單數位加法減法那種方法來做，因為使用 Comba 或 Karatsuba 會增加計算量，所以單獨實現更合理。

   【回到本系列目錄】 

版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4451758.html