title: Karatsuba Multiplication for unequal size, non-power-of-2 operands
body: <p>What's the most efficient way to implement <a href="http://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="noreferrer">Karatsuba</a> 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 <em>memory</em>-efficient.</p>
  
  <p>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?</p>