Skip to content

Instantly share code, notes, and snippets.

@anirudhjayaraman
Created October 13, 2015 17:02
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anirudhjayaraman/87d141779c0c9bb28d8c to your computer and use it in GitHub Desktop.
Pseudocode for Karatsuba Multiplication Algorithm
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
@ADYASHAPATTANAYAK
Copy link

THank U

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment