algorithmx86cpu-architecturealumicro-architecture

How modern X86 processors actually compute multiplications?


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


Solution

  • 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: <c45d9d2e-039d-4085-a617-d90f7a3b1f93@googlegroups.com> — 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: <d92d1961-a3e4-441e-8b3d-b9ce6bd24b58@googlegroups.com> — 14 January 2020)

    See Wikipedia for information on Dadda tree multipliers.