Karatsuba-Ofman乘法器是俄羅斯人Karatsuba于1962年提出的，主要思想是采用分治算法計(jì)算整數(shù)乘法，將計(jì)算復(fù)雜度向前推進(jìn)到$O(n^{lo{g}_{2}3})$，而此前普遍認(rèn)為整數(shù)乘法的計(jì)算復(fù)雜度是$O(n^2)$。
來看一個(gè)例子：假設(shè)$n=2l$，$x=x_1{2}^l+x_0$，$y=y_1{2}^l+y_0$是$2l$-位整數(shù)，于是：
$xy=(x_1{2}^l+x_0)(y_1{2}^l+y_0)$
$=x_1?y_1{2}^{2l}+[(x_0+x_1)?(y_0+y_1)?x_1{y}_1?x_0?y_0]2^l+x_0{y}_0$
$xy$可以通過3個(gè)$l$-位的整數(shù)乘法（而不是$2l$-位的整數(shù)乘法）和2個(gè)乘法，2個(gè)減法算式計(jì)算出來。
若$l$數(shù)值較大，加法和減法相對(duì)乘法的計(jì)算代價(jià)可以忽略。在經(jīng)典算例中，程序可以反復(fù)迭代到中位數(shù)，并一直執(zhí)行到滿足閾值（可能的值是機(jī)器字長(zhǎng)度）的條件才停止。
對(duì)于大小適中的整數(shù)，Karatsuba算法的執(zhí)行上限是需要考慮的因素。不同于傳統(tǒng)方法，Karatsuba算法的執(zhí)行盡可能減少移位請(qǐng)求（對(duì)于$2^l$和$2^{2l}$乘法），并且高效使用面向字節(jié)的操作。例如：采用拆分字節(jié)的邊界的方法有可能更好，一個(gè)指定階段的分裂可以拆分成2個(gè)以上片段。
例1（Karatsuba-Ofman方法）：考慮224-位整數(shù)$x$和$y$的乘法，運(yùn)算設(shè)備的字節(jié)長(zhǎng)度為$W=32$。2個(gè)深度為2的方法展現(xiàn)如下圖所示，顯然，圖a的裂項(xiàng)從數(shù)學(xué)上看可能更為優(yōu)雅并且在代碼上更具備重用性。然而，卻需要更多的移位操作，這是因?yàn)榱炎儾⒎且宰珠L(zhǎng)單位為邊界進(jìn)行。如果56-位數(shù)的乘法的代價(jià)近似于64-位數(shù)乘法，顯然裂項(xiàng)對(duì)于硬件容量利用不足，這是因?yàn)槿鐖Db所示，9個(gè)64位乘法與1個(gè)32位、8個(gè)64位乘法的代價(jià)完全不同。另外，圖b的列項(xiàng)建立在字長(zhǎng)單位為邊界的基礎(chǔ)上，由于存在加法移位，具有更多的復(fù)雜的跨項(xiàng)計(jì)算。例如，深度為2的跨項(xiàng)具有形式

上圖展示了224-位的整數(shù)分裂成深度為2的二叉樹。圖a所示的$xy$乘積包括采用3個(gè)$112?112$位乘法，每個(gè)執(zhí)行又采用3個(gè)5656位的乘法。b圖所示的xy包括采用一個(gè)9696位乘法(列項(xiàng)為一個(gè)3232位和2個(gè)6464位乘法)和2個(gè)128128位的乘法（每個(gè)產(chǎn)生3個(gè)$64?64$位乘法）。
如下：
$(x_0+x_1)(y_0+y_1)?x_1{y}_1?x_0{y}_0$
其中，$x_0+x_1$和$y_0+y_1$在圖a為57-位數(shù)，在圖b為65-位數(shù)。雖然$(x_0+x_1)(y_0+y_1)$可以被1個(gè)6464位乘法和2個(gè)加法計(jì)算出來，圖b列項(xiàng)的代價(jià)仍然有點(diǎn)大。

上圖展現(xiàn)了192-位整數(shù)的深度為2的裂項(xiàng)。圖a的乘法$xy$具有3個(gè)$96?96$的乘法，每個(gè)乘法執(zhí)行1個(gè)$32?32$和2個(gè)$64?64$的乘法（每個(gè)乘法需要3個(gè)32*32位乘法），總共需要21個(gè)$32?32$位乘法。圖b或圖c，僅需要18個(gè)$32?32$位乘法就可以完成計(jì)算。
例2（192位數(shù)乘法）：考慮Karatsuba-Ofman算法應(yīng)用于192-位整數(shù)乘法的例子，假設(shè)設(shè)備字長(zhǎng)$W=32$。按上圖所示的3個(gè)深度位2的方法，圖a需要21個(gè)$32?32$位乘法，圖b和圖c只需要18個(gè)。主要的思路是$3l$-位整數(shù)$x=x_2{2}^{2}l+x_1{2}^l+x_0$和$y=y_2{2}^{2l}+y_1{2}^l+y_0$能夠計(jì)算如下：
有限域的乘法性能在橢圓曲線機(jī)制中是非常重要的。囿于硬件乘法器和傳播成本的限制，執(zhí)行以上算法勢(shì)必會(huì)引起明顯的瓶頸。

總結(jié)

以上是生活随笔為你收集整理的Karatsuba-Ofman乘法器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。