Which algorithm to choose for a huge integer multiplication, depending on N size

Question

In my free time I'm preparing for interview questions like: implement multiplying numbers represented as arrays of digits. Obviously I'm forced to write it from the scratch in a language like Python or Java, so an answer like "use GMP" is not acceptable (as mentioned here: Understanding Schönhage-Strassen algorithm (huge integer multiplication)).

For which exactly range of sizes of those 2 numbers (i.e. number of digits), I should choose

1. School grade algorithm
2. Karatsuba algorithm
3. Toom-Cook
4. Schönhage–Strassen algorithm ?

Is Schönhage–Strassen O(n log n log log n) always a good solution? Wikipedia mentions that Schönhage–Strassen is advisable for numbers beyond 2^2^15 to 2^2^17. What to do when one number is ridiculously huge (e.g. 10,000 to 40,000 decimal digits), but second consists of just couple of digits?

Does all those 4 algorithms parallelizes easily?

Answer 1

You can browse the GNU Multiple Precision Arithmetic Library's source and see their thresholds for switching between algorithms.

More pragmatically, you should just profile your implementation of the algorithms. GMP puts a lot of effort into optimizing, so their algorithms will have different constant factors than yours. The difference could easily move the thresholds around by an order of magnitude. Find out where the times cross as input size increases for your code, and set the thresholds correspondingly.

I think all of the algorithms are amenable to parallelization, since they're mostly made up up of divide and conquer passes. But keep in mind that parallelizing is another thing that will move the thresholds around quite a lot.