Karatsuba algorithm: Difference between revisions

Revision as of 21:09, 7 April 2021

Revision as of 18:39, 2 June 2021

Line 157:

Here is the pseudocode for this algorithm, using numbers represented in base ten. For the binary representation of integers, it suffices to replace everywhere 10 by 2.<ref>{{cite book |last= Weiss |first= Mark A. |date= 2005 |title= Data Structures and Algorithm Analysis in C++ |publisher= Addison-Wesley|page= 480|isbn= 0321375319}}</ref>

split_num receives a number and a ten. Then, it returns two numbers divided in that ten. For example, num1 = 12345 and k = 3. Then high1 = 12 and low1 = 345.

The second argument of the split_at function specifies the number of digits to extract from the ''right'': for example, split_at("12345", 3) will extract the 3 final digits, giving: high="12", low="345".

<syntaxhighlight lang="C">

Line 164:

return num1 × num2

/* Calculates the sizeten ofwhere to divide the numbers.number */

mk = floor( min(size_base10(num1), size_base10(num2)) / 2)

m2 = floor(m / 2)

/* m2 = ceil(m / 2) will also work */

/* Split the digit sequences in the middle. */

/*IMPORTANT: split_num receives a number and a ten. Then, it returns two numbers divided in that ten.

high1, low1 = split_at(num1, m2)

For example, num1 = 12345 and k = 3. Then high1 = 12 and low1 = 345. */

high2, low2 = split_at(num2, m2)

high1, low1 = split_atsplit_num(num1, m2k)

high2, low2 = split_atsplit_num(num2, m2k)

/* 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 ^ (m2k × 2)) + ((z1 - z2 - z0) × 10 ^ m2k) + z0

</syntaxhighlight>