TransWikia.com

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

Computer Science Asked by John Flemin on November 8, 2021

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.

One 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.

Answered by Jaeyoon Kim on November 8, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP