Hacker News new | ask | show | jobs
by bogomipz 3174 days ago
>"or unroll the (fixed iteration) shift-and-add loop"

Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"

1 comments

The shift-and-add algorithm for multiplication is usually implemented as a loop that iterates for the number of bits of the operand, so e.g. for an 8-bit x 8-bit multiplication, the loop runs 8 times. (An "early out" algorithm when one of the operands becomes 0 is also common, but let's not complicate things here.) It's trivial to unroll this loop into the 8 individual shift-and-add steps.