3 ms·
The reason it isn't actually important to have a specific algorithmic implementation is that - like other exotic multiplication algorithms with better big-O com
by MrEldritch 8y ago
The reason it isn't actually important to have a specific algorithmic implementation is that - like other exotic multiplication algorithms with better big-O complexity than the usual ones - the constant factors are much, much bigger, to the point where they would only become noticeably faster for absurdly huge integers. The theoretical aspect of this is the interesting part.
- db48x 8y agoIn fact, in this case the algorithm is only intended for numbers with 2^4096 bits. See section 5 of the paper: In this section we present the main integer multiplication algorithm. We actually give a family of algorithms, parameterised by a dimension parameter d > 2. Let n_0 := 2^(d^12) > 2^4096, and suppose that we wish to multiply integers with n bits. For n < n_0, we may use any convenient base-case multiplication algorithm, such as the classical O(n^2) algorithm.