On 2025-08-25 00:15, Colin Paice wrote:
Sometimes the compilers are better than humans... for example multiply
is
expensive, and divide is even more expensive but the compiler can
handle
constants
*Multiply *
x * 10 =x * 8 + x * 2
= (x shift left 3 bits) + (x shift left 1 bit)
shifts can be done in parallel then added (two clock ticks)
Yes, this is an old one, dating from the 1950s.
*Divide*
x/3 = x * 341 /1024
= x * 341 >> 10 bits
17 / 3 = 17 * 341 /1024 = 5 (2+ 1 clock ticks)
Divsion by 10 is interesting, gives the exact answer:
j = k + 1
m = j +2j
n = m + m/16
p = n + n/256
q = p/32
No division here; these are logical shifts.
More details in my paper, "Division by 10", of 1991.
These numbers (341, 1024) are not unique
1024/3 = 341: 1/3 = 341/1024
65536/3 = 21845 : 1/3 = 21845/65536
I thought this amazing - multiply and divide without using multiply or
divide instructions.
Other factors might be found in "Hacker's Delight".
Colin
