Exercise1-17 <---> Exercise1-19
Exercise 1.18.
Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.
(This algorithm, which is sometimes known as the "Russian peasant method" of multiplication, is ancient. Examples of its use are found in the Rhind Papyrus, one of the two oldest mathematical documents in existence, written about 1700 B.C. (and copied from an even older document) by an Egyptian scribe named A'h-mose.)
Ru: Используя результаты упражнений 1.16 и 1.17, разработайте процедуру, которая порождает итеративный процесс для умножения двух чисел с помощью сложения, удвоения и деления пополам, и затрачивает логарифмическое число шагов.
(Этот алгоритм, который иногда называют «методом русского крестьянина», очень стар. Примеры его использования найдены в Риндском папирусе, одном из двух самых древних существующих математических документов, который был записан (и при этом скопирован с еще более древнего документа) египетским писцом по имени А’х-мосе около 1700 г. до н.э.)
Scheme solution:
(define (* a b)
(define (mul a b c)
(cond ((= b 0) c)
((even? b) (mul (double a) (halve b) c))
(else (mul a (- b 1) (+ a c)))))
(mul a b 0))
Haskell solution:
fast'mul'iter a b = mul a b 0
where
mul a b c | b == 0 = c
| even b = mul (double a) (halve b) c
| otherwise = mul a (b - 1) (a + c)
OCaml solution:
let fast_mul_iter a b =
let rec mul a b c =
if b = 0 then
c
else if b mod 2 = 0 then
mul (double a) (halve b) c
else
mul a (b - 1) (a + c)
in
mul a b 0
Standard ML solution:
fun fast_mul_iter a b = let
fun mul (a, b, c) =
if b = 0 then
c
else if b mod 2 = 0 then
mul (double a, halve b, c )
else
mul ( a , b - 1, a + c)
in
mul (a, b, 0)
end
Oberon/Component Pascal solution:
PROCEDURE FastMulIter (a, b : INTEGER) : INTEGER;
VAR c, d, k : INTEGER;
BEGIN
c := 0; d := a; k := b;
WHILE k # 0 DO
IF ODD(k) THEN
c := d + c;
DEC(k)
ELSE
d := Double (d);
k := Halve (k)
END
END;
RETURN c
END FastMulIter;
Exercise1-17 <---> Exercise1-19