3 ms·
Speaking of Karatsuba, in 1993 I wrote a C++ big integer package and used Karatsuba. I had some questions about how to use it when the two numbers being multipl
by tzs 9y ago
Speaking of Karatsuba, in 1993 I wrote a C++ big integer package and used Karatsuba. I had some questions about how to use it when the two numbers being multiplied are not the same length. I did some experiments, and noticed hints at some patterns in the data I was seeing. I asked about this on sci.math, but as far as I know no one ever gave an explanation.
If anyone is curious and wants to figure this out, here's my old sci.math post [1].
[1] https://groups.google.com/d/msg/sci.math/MX3MLCQ0zzA/XTqUoZk2im0J https://groups.google.com/d/msg/sci.math/MX3MLCQ0zzA/XTqUoZk...
- coldsauce 9y agoWow! I find it remarkable that you have had this question open for 25 years without a single answer.
- gnulinux 9y agoDid you eventually find an answer?
- delinka 9y ago"...the two numbers being multiplied are not the same length." Do you mean as counted in bits? If so, prepend zeroes until they are the same length. Does this negatively affect the algorithm's results? EDIT: When I say 'prepend' I mean on the MSB end. In typical arithmetic on paper, that'd be adding leading zeroes (prepending) onto the numbers.
- taejo 9y agoYou can do that - it's the "textbook" solution - but you can probably do better by not making your inputs larger: in the worst case you're going from multiplying N digits by 1 digit to N digits by N digits.
- saagarjha 9y agoMight be something to do with caching or fitting operands in registers?