Do there exist fast multiplication algorithms for two integers with one of them being static?

Question

Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). But there is always the assumption that both numbers are equally arbitrary.
Are there algorithms that are even faster under the assumption that for every time N changes, M changes K times with K being 2^20 or more?
An algorithm that given an integer, constructs/primes a special fast algorithm to compute a product just for that integer.
The only algorithm of this kind that I was able to find and that gave rise to this question is described in this paper: https://sci-hub.tw/10.1007/s00224-020-09986-5
C code provided by the author (GMP lib): http://www.fit.vutbr.cz/~ibarina/tmp/n.c
Summary: Uses the Collatz conjecture to do multiplication, O(Nk) where k is the number of odd integers in the Collatz sequence of a given odd operand. If k < log N it can beat current state of the art multiplication algorithms.

Jaeyoon Kim · Answer

If $N$ is fixed (at least for a very long time), why not do some pre-computation. For example, you can pre-compute the product of $N$ with any 16-bit integer. Just save these values in a lookup table (there are only $2^{16} = 65536$ elements).
Represent $M$ in base $2^{16}$. i.e. $M = a_0 + a_1 * 2^{16} + a_2 * 2^{32} ldots a_{63}(2^{16})^{63}$.
Well, $M = (N * a_0) + (N * a_1) * 2^{16} + (N * a_2) * 2^{32} ldots ( N * a_{63}) * (2^{16})^{63}$. Instead of computing $N * a_i$, we can search the lookup table.

Do there exist fast multiplication algorithms for two integers with one of them being static?

One Answer

Add your own answers!

Ask a Question