Karatsuba algorithm: Difference between revisions

Revision as of 22:32, 21 July 2020

Revision as of 07:23, 12 August 2020

Line 163:

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++ |___location= |publisher= Addison-Wesley|page= 480|isbn= 0321375319}}</ref>

It'sThe importantsecond toargument note thatof the "split_at" function worksspecifies asthe followsnumber of digits to extract from the ''right'': for example, split_at("12345", 3) returnswill extract the 3 final digits, giving: high="12", low="345".

<syntaxhighlight lang="C">

Line 173:

m = min(size_base10(num1), size_base10(num2))

m2 = floor(m / 2)

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

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