karatsuba乘法

算法概述Kararsuba乘法是一種快速乘法。 此算法主要用於兩個大數相乘。 ，而Karatsuba算法的複雜度僅為3n

算法概述

Kararsuba乘法是一種快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出，並於1962年得以發表。此算法主要用於兩個大數相乘。普通乘法的複雜度是n，而Karatsuba算法的複雜度僅為3n≈3n（log3是以2為底的）。

算法描述

步驟簡介

Karatsuba算法主要套用於兩個大數的相乘，原理是將大數分成兩段後變成較小的數位，然後做3次乘法，並附帶少量的加法操作和移位操作。
現有兩個大數，x，y。
首先將x，y分別拆開成為兩部分，可得x1，x0，y1，y0。他們的關係如下：
x = x1 * 10 + x0；
y = y1 * 10 + y0。其中m為正整數，m < n，且x0，y0 小於 10。
那么 xy = (x1 * 10 + x0)(y1 * 10 + y0)
=z2 * 10 + z1 * 10 + 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，
故x0 * y0 便可以由加減法得到。

實例展示

設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 * 1000 + 11538 * 1000 + 272205 = 83810205。

效率分析

對於給定的n位大數，算法的複雜度不超過3n≈ 3n。

偽代碼描述

procedurekaratsuba(num1,num2)if(num1<10)or(num2<10)returnnum1*num2/*calculatesthesizeofthenumbers*/m=max(size(num1),size(num2))m2=m/2high1,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)