4
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – njuffa
    Commented Jun 21, 2020 at 0:30
  • $\begingroup$ 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. $\endgroup$
    – John Flemin
    Commented Jun 21, 2020 at 1:07
  • $\begingroup$ 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) $\endgroup$
    – John Flemin
    Commented Jun 21, 2020 at 1:10
  • $\begingroup$ 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. $\endgroup$
    – njuffa
    Commented Jun 21, 2020 at 2:55
  • $\begingroup$ 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! $\endgroup$
    – gnasher729
    Commented Jun 21, 2020 at 9:13

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.