# Multiplication by a constant - how?

## Sergey Solyanik <Sergey.Solyanik@bentley.com>14 Mar 1997 00:30:31 -0500

From comp.compilers

Related articles
Multiplication by a constant - how? Sergey.Solyanik@bentley.com (Sergey Solyanik) (1997-03-14)
Re: Multiplication by a constant - how? rweaver@ix.netcom.com (1997-03-16)
Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16)
Re: Multiplication by a constant - how? d.sand@ix.netcom.com (Duane Sand) (1997-03-16)
Re: Multiplication by a constant - how? harwood@trinidad.progress.com (1997-03-16)
Re: Multiplication by a constant - how? dlmoore@ix.netcom.com (David L Moore) (1997-03-16)
Re: Multiplication by a constant - how? preston@tera.com (1997-03-21)
[4 later articles]
| List of all articles for this month |

 From: Sergey Solyanik Newsgroups: comp.compilers Date: 14 Mar 1997 00:30:31 -0500 Organization: BSI Keywords: arithmetic, optimize

MicroSoft Visual C seems to be capable to generate multiplication by a
constant using sequence of shifts and adds no longer than 6 operations
(total), using at most two registers. The optimization is used always
and does not seem to be confined to any special cases. Does anybody
know what algorithm is used and where can I look for information?

Examples:

a = a * 127; // 1111111 bin

=> mov eax, dword ptr [a]
mov ecx, eax
shl eax, 7
sub eax, ecx

a = a * 11101; // 10101101011101 bin

=> mov eax, dword ptr [a]
mov ecx, eax
lea eax, [eax+eax*8]
lea eax, [ecx+eax*4]
lea eax, [eax+eax*4]
lea eax, [eax+eax*4]
lea eax, [eax+eax*2]
lea eax, [ecx+eax*4]

a = a * 11229; // 10101111011101 bin

=> mov eax, dword ptr [a]
mov ecx, eax
lea eax, [eax+eax*2]
lea eax, [ecx+eax*4]
lea eax, [eax+eax*8]
shl eax, 05
sub eax, ecx
lea eax, [eax+eax*2]

...etc

Thanks and regards --

Sergey Solyanik
Bentley Systems, Inc

Sergey.Solyanik@bentley.com
[In the computer theory biz this topic is known as addition chains. I know
lots of heuristics but no general optimal scheme. -John]

--

Post a followup to this message