How modern X86 processors actually compute multiplications?

Question

I was watching some lecture on algorithms, and the professor used multiplication as an example of how naive algorithms can be improved...

It made me realize that multiplication is not that obvious, although when I am coding I just consider it a simple atomic operation, multiplication requires a algorithm to run, it does not work like summing numbers.

So I wonder, what algorithm modern desktop processors actually use? I guess they don't rely on logarithm tables, and don't make loops with thousands of sums...

Answer 1

Mitch Alsup (who worked on Motorola 88K, Ross SPARC, AMD x86, etc.) has stated on the comp.arch newsgroup:

All modern multiplier designers use the Dadda method for building the tree.

(Message-ID: <[email protected]> — 14 December 2018)

and (with respect to availability of recent references for what multiplication mechanisms are used by AMD/Intel/NVIDIA):

Only in the patent office.

(Message-ID: <[email protected]> — 14 January 2020)

See Wikipedia for information on Dadda tree multipliers.

Answer 2

There are an array of multiplication procedures that can be used in a CPU. E.g., Booth multiplier for 2's complement binary numbers taught in most computer architecture/organization course. Multiplication in binary is simpler than multiplication in decimal representation. Calculating partial products is simple. The multiplicand,M,(if multiplier bit is 1) or 0(if a multiplier bit is 0). Compare that with decimal where it could be anything between (0*M to 9*M). Whenever somebody design a custom CPU (like soft-core on a FPGA) a developer can choose appropriate multiplication procedures. Some commonly used are CORDIC multipliers, Radix-2,Radix-4,Radix-8... booth multipliers. All this multiplier algorithm generate partial product (like the manual multiplication). All the partial products are added to have the final product. There are multiple ways this is done in modern processors like using Dadda multiplier, Wallace tree.

Put simply, every processor designer can use any multiplier algorithm to generate partial products and add partial products to get final results. Depending on binary representation used internally in the processor registers, register size in bits, the most optimum algorithm will vary.