Karatsuba乘法适用于不等大小,非幂2的操作数

Question

使用不等大小的输入操作数实现Karatsuba大数乘法的最有效方法是什么,其大小不是2的幂,甚至可能不是偶数？填充操作数意味着额外的内存,我想尝试使其具有内存效率.

我在非偶数大小的Karatsuba中注意到的一件事是,如果我们试图将数字分成尽可能接近偶数的"一半",一半将有m + 1个元素而另一个m,其中m = floor(n/2),n是分割数中的元素数.如果两个数字具有相同的奇数,那么我们需要计算两个大小为m + 1的数量的乘积,需要n + 1个存储,而n是偶数时的n.所以我正确地猜测奇数尺寸的Karatsuba可能需要比偶数尺寸更多的内存？

Answer 1

大多数时候,操作数的长度不会是2的幂.我认为这是罕见的情况.大多数时候会有不同长度的操作数.但对于Karatsuba算法来说这不是问题.

实际上,我在这里看不到任何问题.这个开销(奇数长度)非常轻,绝对不是什么大问题.关于不同长度的问题 - 我们假设X = 1234且Y = 45

所以,a = 12,b = 34,c = 0,d = 45那么,之后 X * Y = 10 ^ 4 * ac + 10 ^ 2 (ad + bc) + bd

ac = 0;
bd = 34 * 45;
ad + bc = (a + b) * (c + d) - ac - bd = 540;

并且,如果我们假设,我们可以轻松地乘以2位数 - 你可以得到答案= 55530.同样,在任何计算器中只需乘以1234*45 :)所以,我看不到任何长度不同的内存问题数字.