You can multiply much more efficiently the way Egyptians used to do (
http://www.jimloy.com/egypt/mult.htm[
^]): let
M
x
N
, you will find the '
1
' bits in
M
and add
N
multiplied by the corresponding powers of
2
, obtained by doubling.
Here is Python code that does it using only additions and comparisons:
M= 5
N= 9
# Accumulator
A= 0
while M > 0:
# Power of 2
W= 1
NW= N
# Find the leftmost bit in M
while W + W < M:
# Duplicate
W= W + W
NW= NW + NW
# Accumulate
A= A + NW
# Erase the bit from M
M= M - W
print A
Just compile this code to LittleMan assembly.
Note. This algorithm will perform
O(m^2)
additions, where
m
is the number of bits in
M
. [Maybe
O(m)
can be achieved, I am unsure.] In any case, this is far better than
O(M)
achieved by successive additions.
You can adapt these ideas to implement division, by subtracting
N
-times-a-power-of-
2
from
M
.