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

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.

• Could you state where have you looked for potential answers so far (this avoids duplication of effort)? Do these piece-wise constant factors have any particular structure, e.g. very few 1-bits? In general, any multiplication method that uses recoding of the operands should be able to benefit from reduced work when one of the operands is constant, e.g. Booth-encoding for hardware multipliers, or FFT prep work in FFT-based software multiplication. Neither of these examples would seem to apply to operands of length 1024 bits, though. – njuffa Jun 21 '20 at 0:30
• I have not been able to find anything, my last statement is a conjecture. And there is no structure to rely on in either operand, both are arbitrary. I conjectured that there may be some algorithm involving a tradeoff - algorithm that does analysis of the operand that is held static. And it simply doesn't make sense to do it for an integer that is never seen again. – John Flemin Jun 21 '20 at 1:07
• Actually, I got the idea from a recent paper that utilizes the Collatz conjecture to do multiplication, it can be extremely efficient for some integers and through bruteforce I imagine any arbitrary integer could be broken down to one that satisfies the requirement and a remainder. But hopefully its not the only algorithm of its kind? sci-hub.tw/10.1007/s00224-020-09986-5 GMP C code: fit.vutbr.cz/~ibarina/tmp/n.c (it does beat GMP for these types of integers, ones that have short collatz trajectories) – John Flemin Jun 21 '20 at 1:10
• It would improve the question if that background information would be edited into it, as comments on this site are rather ephemeral and not everybody reads comments. – njuffa Jun 21 '20 at 2:55
• The proportion of n-bit integers with log n odd numbers in their Collatz sequence is ridiculously small. For n=1024 about 2^100/10! That is one in 2^924 * 10! – gnasher729 Jun 21 '20 at 9:13

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.