3
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • $\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
    Commented Mar 26, 2019 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
    Commented Mar 26, 2019 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
    Commented Mar 27, 2019 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
    Commented Mar 27, 2019 at 0:11
  • 1
    $\begingroup$ CPU designers are versed in acceleration techniques of all kinds, more than anybody else and more than you could imagine. So an easy answer is: the lookup technique is not effective in practical applications. Remember anyway that the famous Pentium bug event revealed that some lookup table was used in the implementation of division. $\endgroup$
    – user16034
    Commented Jan 19, 2023 at 11:17

3 Answers 3

Reset to default
4
$\begingroup$

Some integer multiplication algorithms do use lookup tables.

The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a 200 digit table. (Many joked that CADET stood for "Can't Add, Doesn't Even Try").

The IBM 1620 Model II had a simple ALU for addition and subtraction, but still used the same 200 digit table for multiplication.

While one might think that multiplying two 8-bit numbers together would require a table of 2^16 = 65,536 values, the "quarter square multiplication" technique uses a much smaller table of 510 values. Using such table-lookups is apparently the fastest way to multiply two arbitrary 8-bit numbers on the 6502 and Microchip PIC and other simple processors. Surprisingly, the quarter-square multiplication technique on the 8086 and 8088 is faster than the built-in multiply instruction when multiplying two arbitrary 8-bit numbers.

More expensive processors often include a larger, more complex ALU that multiplies "small" numbers in fewer CPU cycles than the 8086. While memory speeds have improved over the years, processor speeds have far outpaced memory speeds, and so recent high-end processors can generally multiply "small" numbers in much less time than a single main-memory memory cycle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You really explained everything well, thanks! I liked the "Can't Add, Doesn't Even Try". Amazing to think that Intel's chips used to be faster by using quarter-square table lookup! $\endgroup$
    – Matt Groff
    Commented Jan 24, 2023 at 21:43
5
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\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
    Commented Mar 27, 2019 at 0:52
  • $\begingroup$ @Bulat, I know -- but the question refers specifically to multiplying integers, not elements of a finite field. $\endgroup$
    – D.W. ♦
    Commented Mar 27, 2019 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
    Commented Mar 27, 2019 at 1:29
  • $\begingroup$ @Bulat, not CLMUL? $\endgroup$
    – Peter Taylor
    Commented Mar 27, 2019 at 7:46
  • 1
    $\begingroup$ @MattGroff, don't ask us. Do the evaluation yourself! Implement it, compare to the other alternatives, see whether your idea is better in any way. Who knows, maybe you'll discover something awesome! It sounds like you won't be convinced until you try. $\endgroup$
    – D.W. ♦
    Commented Mar 27, 2019 at 15:35
0
$\begingroup$

A lookup table for integer entries up to $n$ has size $O(n^2\log n)$. For $b$ bits numbers, this is $O(b\,2^{2b})$.

FFT's are usually implemented with double precision floating-point arithmetic. With proper scaling, fixed-point and sacrificing a lot of accuracy, you might do with $b=20$ or so ($50$ Gb)...

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.