It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$.

Now, multiplying two $n$-bit naturals together can be assisted by using an FFT of size $O(n / \log(n))$. It seems to me that we can then perform the multiplications and additions for the FFT using the lookup tables.

I'm wondering why this method doesn't or hasn't seemed to get any attention. Is it because of memory bandwidth problems?

It just seems to me that using tables would be quicker, so I'm hoping that someone can provide me with a better intuition.

  • $\begingroup$ Modern CPUs usually supports very efficient multiplication of N-bit integers and can address 2^N bytes of memory. But any lookup table which can be useful will have size > 2^2N. So it cannot be directly addressed, and with 64-bit CPUs, will require entire Earth to store the data. $\endgroup$ – Bulat Mar 26 '19 at 23:54
  • $\begingroup$ @Bulat: a lookup table of $2^{2N}$, with $N=\log(n)/2$, would only require a lookup table of approximately a million words, in order to multiply two million-bit integers in the manner I describe above. $\endgroup$ – Matt Groff Mar 26 '19 at 23:57
  • $\begingroup$ Of course, since it contains multiplication table for 10-bit integers. Let me describe it other way. If N-byte integer can be stored in RAM, then CPU almost always can multiply log(N)-bit integers natively. Moreover, when CPU supports multiplication of log(N)/2-bit integers, N-bit integers will probably be too large even for HDDs attached (i.e. any external memory). And even more - performing a few N-bit operations to multiply two 2N-bit integers is still much faster than reading one word from RAM (not cache). $\endgroup$ – Bulat Mar 27 '19 at 0:05
  • $\begingroup$ So, for 64-bit CPU your table should support multiplication of at least 128-bit integers to make any sense. It's easy to check that it will be larger than the entire Universe (~2^260 elementary particles) $\endgroup$ – Bulat Mar 27 '19 at 0:11
  • $\begingroup$ @Bulat: I realize that multiplying $N$ bit integers is usually done by a CPU when they are appropriately small enough. However, theoretically, for $N$ much greater than the size of a few billion bits, we can use the FFT to break apart the integers we multiply down to CPU size, and thus we have an algorithm that is faster than the current "fastest" integer multiplication algorithms. As far as I know, they proceed to break integers into multivariate equations with many DFTs, but these are asymptotically slower than the method I describe above. So I'm wondering why they are used. $\endgroup$ – Matt Groff Mar 27 '19 at 0:13

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long. If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication. Typically we want to multiply numbers that are larger than that. And when we do want to multiply small numbers, using the CPU's built-in multiply instruction is usually faster than using a lookup table.

So there is no size (that I'm aware of) where a lookup table is a good solution for multiplying two numbers.

Now you're thinking that maybe the numbers that are generated by FFT should be multiplied with lookup tables. But those are just numbers, and as I said above, there is pretty much no situation where the fastest way to multiply two numbers is with a lookup table. It doesn't matter how those numbers were generated -- whether by FFT or by any other process.

So I'd say the reason it doesn't have more attention is because it doesn't deserve attention; it seems unlikely to be faster or better than existing schemes.

Lookup tables are occasionally used in cryptographic code, where constant-time access is needed. This is not because they are faster -- they're not; they're slower -- but because they have other properties that are beneficial. I don't know of any specific examples, but it wouldn't surprise me to discover that someone had used a lookup table for multiplication in some constant-time cryptographic code.

  • $\begingroup$ Lookup tables are used f.e. for Galois Field multiplication. Fastest GF(2^n) multiplication algos multiply data in 4-bit pieces using SSE PSHUFB instruction which is a sort of SIMD performing multiple 4-bit lookup operations at once. It uses an SSE word (128 bits = 16 4-bit elements) as the lookup table. $\endgroup$ – Bulat Mar 27 '19 at 0:52
  • $\begingroup$ @Bulat, I know -- but the question refers specifically to multiplying integers, not elements of a finite field. $\endgroup$ – D.W. Mar 27 '19 at 0:52
  • $\begingroup$ I'm sorry to ask this, but if a multiplication algorithm of two $n$ bit integers used a lookup table of $n$ bits or less, or maybe $O(n)$ bits, could this possibly be considered as a fast, useful, or good algorithm? Say it multiplies these $n$ bit numbers in $o(n \log(n))$... $\endgroup$ – Matt Groff Mar 27 '19 at 1:29
  • $\begingroup$ @Bulat, not CLMUL? $\endgroup$ – Peter Taylor Mar 27 '19 at 7:46
  • $\begingroup$ Not an example for 16 or 32 but, The Galois field of AES $GF(2^8)$ can be implemented by table lookup, though it has only $2^8 \times 2^8$. Also, one can use Karatsuba-Offman to multiply 32-bit numbers effectively if he has a table implementation for 16-bit. I've never seen a performance test. $\endgroup$ – kelalaka Mar 27 '19 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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