karatsuba乘法

Karatsuba乘法是一種快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出，并于1962年得以發(fā)表。[1]此算法主要用于兩個大數(shù)相乘。普通乘法的復(fù)雜度是n2，而Karatsuba算法的復(fù)雜度僅為3nlog3≈3n1.585（log3是以2為底的）[2]。

目錄

1?算法描述

??步驟簡介

??實例展示

2?效率分析

3?偽代碼描述

算法描述

編輯

步驟簡介

Karatsuba算法主要應(yīng)用于兩個大數(shù)的相乘，原理是將大數(shù)分成兩段后變成較小的數(shù)位，然后做3次乘法，并附帶少量的加法操作和移位操作。 現(xiàn)有兩個大數(shù)，x，y。 首先將x，y分別拆開成為兩部分，可得x1，x0，y1，y0。他們的關(guān)系如下： x = x1 * 10m?+ x0； y = y1 * 10m?+ y0。其中m為正整數(shù)，m < n，且x0，y0 小于 10m。 那么 xy = (x1 * 10m?+ x0)(y1 * 10m?+ y0) =z2 * 102m?+ z1 * 10m?+ z0，其中： z2 = x1 * y1； z1 = x1 * y0 + x0 * y1； z0 = x0 * y0。 此步驟共需4次乘法，但是由Karatsuba改進以后僅需要3次乘法。因為： z1 = x1 * y0+ x0 * y1 z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0， 故z1 便可以由一次乘法及加減法得到。

實例展示

設(shè)x = 12345，y=6789，令m=3。那么有： 12345 = 12 * 1000 + 345； 6789 = 6 * 1000 + 789。 下面計算： z2 = 12 * 6 = 72； z0 = 345 * 789 = 272205； z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。 然后我們按照移位公式（xy = z2 * 10 + z1 * 10 + z0）可得： xy = 72 * 10002?+ 11538 * 1000 + 272205 = 83810205。

效率分析

編輯 對于給定的n位大數(shù)，算法的復(fù)雜度不超過3nlog3?≈ 3n1.585。

偽代碼描述

編輯

1 2 3 4 5 6 7 8 9 10 11 12 13

procedurekaratsuba(num1,num2) if(num1<10)or(num2<10) returnnum1*num2 /*calculatesthesizeofthenumbers*/ m=max(size(num1),size(num2)) m2=m/2 high1,low1=split_at(num1,m2) high2,low2=split_at(num2,m2) /*3callsmadetonumbersapproximatelyhalfthesize*/ z0=karatsuba(low1,low2) z1=karatsuba((low1+high1),(low2+high2)) z2=karatsuba(high1,high2) return(z2*10^(m))+(（z1-z2-z0）*10^(m/2))+(z0)

轉(zhuǎn)載于:https://www.cnblogs.com/freeopen/p/5482949.html

總結(jié)

以上是生活随笔為你收集整理的karatsuba乘法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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