multiplication by constant - quick comparison of algorithms

For all numbers in [2, 10000], there is a total number of 64612 one's in
their binary represenations, and the following compares the total number
of add/sub/shift instructions used to perform all of the multiplications.


Cliff's Bernstein (Preston Briggs)
==========================================================
#insts 81751 70616
#insts/

Note: Cliff's algorithm generates many "shift by zero" and "add by zero"
instructions. The above numbers have already removed these nop
instructions.


It should be interesting to compare them when LEA instruction is allowed.
By allowing the following LEA instructions:


LEA( b, i, s ) = b + i << s, where s = 1, 2, or 3


I have an algorithm that achieves:


#insts 53670
#insts/

The question is how we can push the ratio of #insts/ I will summarize my approach in a later message.


Youfeng Wu
--

Return to the comp.compilers page.
Search the comp.compilers archives again.