method o f carryin g ou t algorithm s fo r high-leve l countin g lik e th e
ones i n th e chapter .
Computations.
4. O n a programmable calculator—o r o n a computer—implemen t
the tw o multiplicatio n algorithm s give n i n th e text . (Se e Exercis e 3 .
For this exercise , you needn't ge t int o really larg e numbers, s o round -
off erro r shoul d pos e n o proble m an d yo u ca n us e ordinar y compu -
tations.) O n a computer , thoug h perhap s no t o n a calculator , yo u
might b e surprise d t o fin d ho w quickl y th e firs t algorith m find s prod -
ucts o f number s wit h 3 , 4, o r 5 digits. Fo r large r numbers , th e naiv e
first algorith m wil l becom e unworkable , bu t th e speede d u p secon d
algorithm shoul d d o fine .
5. Sinc e th e calculato r o r compute r i s doin g th e calculations ,
there i s n o poin t i n usin g decima l instea d binar y numbers . Tr y bot h
10 an d 2 i n th e algorithm s an d se e whethe r yo u fin d an y significan t
difference i n thei r executio n times .
6. O n paper , multipl y 3 3 and 2 1 in th e usua l way . Conver t bot h
numbers t o binar y an d multipl y the m i n binary . Conver t th e binar y
result t o decima l t o verif y tha t th e answer s coincide .
7. Comput e 7 x 9876543210987654321x 1234567890987654321.
8. Writ e a n implementatio n o f th e algorith m fo r divisio n wit h
remainder an d us e i t t o find th e quotien t an d th e remainde r whe n
9876543210987654321 i s divide d b y 5432109876. (I n thi s case , th e
quotient i s so large that eve n a very fas t compute r canno t fin d i t i n a
reasonable tim e b y successivel y addin g 1. Th e mor e efficien t metho d
that add s power s o f 2 to q must b e used. )
Previous Page Next Page