Karatsuba algorithm: Difference between revisions

Revision as of 18:39, 2 June 2021

Revision as of 18:42, 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 dividedsplit in that ten. For example, num1 = 12345 and k = 3. Then high1 = 12 and low1 = 345.

<syntaxhighlight lang="C">

Line 168:

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

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

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

high1, low1 = split_num(num1, k)