Revision as of 15:20, 19 December 2022 edit 2804:d41:a1a8:2c00:351a:8208:e1e0:1dc7 (talk) →Implementation: Changed the calculation of the size of numbers in pseudocode. We need the max lenght of num1 or num2, not the minimum. ← Previous edit		Revision as of 13:03, 25 January 2023 edit undo Frap (talk \| contribs) Extended confirmed users, File movers, Pending changes reviewers, Rollbackers 35,585 edits →Implementation: format code Next edit →
Line 103: 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="Cc"> function karatsuba (num1, num2) if (num1 < 10) or (num2 < 10) return num1 × num2 /* fall back to traditional multiplication / / Calculates the size of the numbers. / m = max (size_base10(num1), size_base10(num2)) m2 = floor (m / 2) / m2 = ceil (m / 2) will also work / / Split the digit sequences in the middle. / high1, low1 = split_at (num1, m2) high2, low2 = split_at (num2, m2) / 3 recursive 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 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

Karatsuba algorithm: Difference between revisions