Reduce r b y ka an d ad d k t o q
End
Output: Th e quotien t q an d th e remainde r r o f th e division .
(In decimal arithmetic, 10 would replace 2 in the two places it occurs. )
These tw o algorithm s begi n wit h th e solutio n (q, r) = (0 , b) o f
b = ga+r ; the y modify (g , r) a t eac h step in such a way that b = qa+r
remains tru e an d r i s reduced , an d the y terminat e whe n r a. (I f
a = 0 , eithe r algorith m endlessl y subtract s 0 fro m b.) I n th e first
algorithm, a i s repeatedl y subtracte d fro m r an d 1 i s adde d t o q
until r i s les s tha n a , bu t i n th e secon d thes e operation s ar e don e i n
batches—subtracting 2
ea
fro m r an d addin g 2
e
t o / , wher e e i s a s
large a s possible .
Once again , th e core ide a i s tha t o f counting. Arithmetic—th e
operations o f addition , subtraction , multiplication , an d divisio n wit h
remainder—are mer e elaborations .
Exercises fo r Chapte r 1
Study Questions .
1. Thin k throug h ho w you woul d explai n th e meanin g an d trut h
of th e commutativ e la w ab = ba o f multiplicatio n t o a n intelligen t
eight-year-old.
2. D o th e sam e fo r th e associativ e la w o f multiplicatio n (ab)c =
a(bc) an d th e distributiv e la w a(b + c ) = ab + ac.
3. Man y o f the computation s i n later chapter s wil l deal with ver y
large numbers—fiftee n o r mor e digit s a t times . Somewha t surpris -
ingly, it can be tricky to do such computations o n easily available com-
puters usin g easil y availabl e softwar e becaus e mos t computation s ar e
done usin g floating poin t arithmetic , whic h limit s th e accurac y wit h
which larg e number s ca n b e represented . A progra m calle d UBASI C
is available fo r Window s computer s wit h whic h th e algorithm s i n th e
chapter ca n be programmed easily . Tr y to download UBASI C t o you r
own compute r i f yo u hav e Windows , or , i f not , tr y t o develo p som e
means o f implementing thes e algorithm s o n your computer . UBASI C
is i n fac t fa r mor e tha n i s needed. Al l tha t i s neede d i s a convenien t
Previous Page Next Page