Why not use a faster algorithm, like the Karatsuba algorithm[1] or the Toom-Cook[2] algorithm?
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/XTqUoZk...
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.
From your [1]: "As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits."
Toom-3 doesn't get faster than Karatsuba (couldn't find numbers quickly). See e.g. https://fossies.org/linux/gmp/tune/README for a discussion.
Reminds me of a demo by my algorithms professor. A certain sorting method (I think binary) requires picking a good pivot to keep complexity down. Picking a random pivot point generally gives good results, but results in an O(n^2) algorithm when asymptotically examined. An algorithm for "perfect" point picking (mean of means I believe) was demonstrated. It resulted in a complexity of O(n) (linear). However, the scale to the linear term was 22. Therefore, in nearly every case, picking randomly would outperform it.
I did not realize Karatsuba required such large numbers to outperform. When I first learned about it, I was under the impression that it would be more effective even for barely "large" numbers
It follows that, for sufficiently large n, Karatsuba's
algorithm will perform fewer shifts and single-digit
additions than longhand multiplication, even though its
basic step uses more additions and shifts than the
straightforward formula. For small values of n, however,
the extra shift and add operations may make it run
slower than the longhand method. The point of positive
return depends on the computer platform and context.
As a rule of thumb, Karatsuba is usually faster when
the multiplicands are longer than 320–640 bits.