way, bu t suc h a computatio n i s a pointles s wast e o f thei r power . A
more efficien t bu t stil l elementar y multiplicatio n algorith m is :
Input: Tw o number s a an d b.
Algorithm:
Let p 0 an d t = a.
While t 0
Let k = 1.
While t 10k
Multiply k b y 10
End
Reduce t b y k an d ad d kb t o p.
End
Output: p
This algorithm is geared to the decimal system in which multiplicatio n
by power s o f 10 is easy—jus t shif t th e digit s th e require d numbe r o f
places t o th e left . Instea d o f addin g b repeatedly t o p, thi s algorith m
finds th e larges t powe r o f 10 tha t i s les s tha n o r equa l t o a , cal l i t
10e
k (whic h one can do by inspection i n the decima l system), add s
10e
time s b to p al l a t onc e (t o find
10eb
does not , o f course , requir e
multiplication, jus t writin g e zero s afte r 6) , an d reduce s b y
10e
th e
number o f time s b still need s t o b e adde d t o p.
This mor e efficien t algorith m i s simila r t o th e algorith m tha t i s
taught i n school , excep t tha t i t begin s wit h th e leftmos t digi t o f a
rather tha n th e rightmost , an d i t doe s not assum e tha t multiplicatio n
by a single-digi t numbe r i s easy ; fo r example , i f a 32 , i t generate s
the produc t a s p = (10 x b) + (10 x b) + (10 x b) + b + b instead o f a s
p = ( 2 x b) + (3 0 x b) the wa y th e usua l algorith m does .
Computers represen t number s i n th e binar y system , no t th e dec -
imal system , s o multiplication b y 2 , rather tha n multiplicatio n b y 10,
is th e eas y operatio n fo r the m t o do , becaus e i n binar y arithmeti c
multiplication b y 2 is accomplishe d b y puttin g a zer o t o th e righ t o f
the number . I n adaptin g th e abov e multiplicatio n algorith m fo r us e
on a computer , therefore , i t i s natura l t o chang e 10 t o 2 i n th e tw o
places wher e i t occurs . O f cours e a n algorith m fo r multiplicatio n i s
hard-wired int o th e circuitr y o f th e compute r wher e th e use r neve r
needs t o b e concerne d wit h it , bu t student s o f numbe r theor y shoul d
give though t t o wha t th e circuitr y i s accomplishing .
Previous Page Next Page