Menu
What's the most efficient way to implement Karatsuba large number multiplication with input operands of unequal size and whose size is not a power of 2 and perhaps not even an even number? Padding the operands means additional memory, and I want to try and make it memory-efficient.
One of the things I notice in non-even-number size Karatsuba is that if we try to divide the number into "halves" as close to even as possible, one half will have m+1 elements and the other m, where m = floor(n/2), n being the number of elements in the split number. If both numbers are of the same odd size, then we need to compute products of two numbers of size m+1, requiring n+1 storage, as opposed to n in the case when n is even. So am I right in guessing that Karatsuba for odd sizes may require slightly more memory than for even sizes?
888
The point of the Karatsuba algorithm is to break large numbers down into smaller numbers so that any multiplications that occur happen on smaller numbers. Karatsuba can be used to multiply numbers in all base systems (base-10, base-2, etc.).
It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs. single-digit products ...
This algorithm takes O(n^2) time. Using Divide and Conquer, we can multiply two integers in less time complexity.
In order to multiply two integers of n-bits, Karatsuba algorithm uses divide and conquer technique and takes O(nlog 3) bit operations. Karatsuba algorithm performs multiplication operation by replacing some multiplications with subtraction and addition operations which are less costly (Karatsuba and Ofman, 1963).
You can multiply the numbers by powers of 10 so that each of them have even numbers of digits. Apply karatsuba algorithm and them divide the answer by the the factor of powers of 10 that you multiplied the original 2 numbers to make them even.
Eg: 123*12
Compute 1230*1200 and divide the answer with 1000.
150
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
