3 ms·
It's not uncommon in scientific computing for the algorithm used to be automatically adjusted based on the input. An example of this is if you want to multiply
by siraben 6y ago
It's not uncommon in scientific computing for the algorithm used to be automatically adjusted based on the input. An example of this is if you want to multiply very large integers. Karatsuba is first used, then Toom-Cook, then Schönhage–Strassen.
Karatsuba: θ(n^1.58)
Toom-Cook: θ(n^1.46)
Schönhage–Strassen: O(n log(n) log(log(n)))
Benchmarking is really the only thing that can reveal this kind of thing, otherwise you'll end up with a theoretically fast but practically slow algorithm.
- BeetleB 6y agoDon't you need insanely high numbers before Karatsuba outperforms the simple O(n^2) algorithm? From Wikipedia: > As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits
- moonchild 6y ago4096-bit keys are standard for RSA, for example.
- senderista 6y agoAnother example is quicksort falling back to insertion sort as a recursive base case for some n=k (instead of recursing all the way to one element).