Multiplication via vectorized tables; several times faster than normal?

[JamesWasil]

Here is the paper for it as PDF which has 2 different methods proposed to achieve this:
Integer Multiplication In Time O (n log n)
https://hal.archives-ouvertes.fr/hal-02070778/document

[Shelwien]

Nice, but misleading; its about multiplication of long numbers rather than common integers used in programming.
Also O(n*log(n)) complexity is defined for Turing machines, who knows how it would compare to cpu instructions,
and what's the minimum n where it becomes useful.

[thorfdbg]

Nice, but misleading; its about multiplication of long numbers rather than common integers used in programming. Also O(n*log(n)) complexity is defined for Turing machines, who knows how it would compare to cpu instructions, and what's the minimum n where it becomes useful.

Probably an old trick. There is an analysis of long multiplication in Knuth, "The Art of Programming", Vol.2. The observation is that multiplication of long numbers has some commonalities with convolution, and thus a multiplication can be replaced by a fourier transformation, a digit-wise multiplication, and a backwards transformation. Fourier is O(n*log(n)), thus multiplication can be done in the same complexity. I'm not sure whether there was an analysis of practiability, but if the numbers are "long enough", it will pay. Just unclear what "long enough" is.

[schnaader]

Probably an old trick. There is an analysis of long multiplication in Knuth, "The Art of Programming", Vol.2. The observation is that multiplication of long numbers has some commonalities with convolution, and thus a multiplication can be replaced by a fourier transformation, a digit-wise multiplication, and a backwards transformation. Fourier is O(n*log(n)), thus multiplication can be done in the same complexity. I'm not sure whether there was an analysis of practiability, but if the numbers are "long enough", it will pay. Just unclear what "long enough" is.

This is known as the Schönhage-Strassen algorithm - and "long enough" seems to be somewhere above 10,000 decimal digits:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^(2^15) to 2^(2^17) (10,000 to 40,000 decimal) digits.The GNU Multi-Precision Library uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture. There is a Java implementation of Schönhage–Strassen which uses it above 74,000 decimal digits.

Also, it has an upper bound of O(n * log n * log log n) - worse than O(n * log n) - and is mentioned in the paper, so there seems to be an improvement indeed.

[Shelwien]

I wonder if its possible to apply some of these optimizations to numeral system conversion.
For example, I recently made this: https://encode.su/threads/3122-dec2b...on-digits-file
and it has long multiplications... but *base is O(N)... but *base^(N/k) might be "long enough" and would allow to create k threads.
So then, I wonder if this can be applied to entropy coding?

[JamesWasil]

I wonder if its possible to apply some of these optimizations to numeral system conversion.
For example, I recently made this: https://encode.su/threads/3122-dec2b...on-digits-file
and it has long multiplications... but *base is O(N)... but *base^(N/k) might be "long enough" and would allow to create k threads.
So then, I wonder if this can be applied to entropy coding?

I was thinking yes, and that characteristics from this approach could be beneficial for your encoders and others who want to speed up multiplication.

If you find that not all sequences are large enough or uniform to use it, it could still be used as a hybrid multiplier.

E.g: If a number or sequence is in a certain range of digits where you know it will be safe to use a table, you can utilize the faster algorithm that does the multiplication in its place. If it is a shorter sequence than the safe range, then normal multiplication would be used. It wouldn't speed up everything, but with error checking (or range analysis) and switching between the two, you could alternate between them and possibly make multiplication faster to improve encoding times.