Exercise1-16 <---> Exercise1-18
Exercise 1.17.
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.
Ru: Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении. Подобным же образом можно производить умножение с помощью повторяющегося сложения. Следующая процедура умножения (в которой предполагается, что наш язык способен только складывать, но не умножать) аналогична процедуре expt: (define (* a b)
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
Этот алгоритм затрачивает количество шагов, линейно пропорциональное b. Предположим теперь, что, наряду со сложением, у нас есть операции double, которая удваивает целое число, и halve, которая делит (четное) число на 2. Используя их, напишите процедуру, аналогичную fast-expt, которая затрачивает логарифмическое число шагов.
Scheme solution:
(define (* a b)
(cond ((= b 0) 0)
((even? b) (double (* a (halve b))))
(else (+ a (* a (- b 1))))))
Haskell solution:
fast'mul a b | b == 0 = 0
| even b = double (fast'mul a (halve b))
| otherwise = a + fast'mul a (b-1)
OCaml solution:
let rec fast_mul a b =
if b = 0 then
0
else if b mod 2 = 0 then
double (fast_mul a (halve b))
else
a + fast_mul a (b-1)
Standard ML solution:
fun fast_mul (a, b) =
if b = 0 then
0
else if b mod 2 = 0 then
double (fast_mul (a, halve b))
else
a + fast_mul (a, b-1)
Oberon/Component Pascal solution:
PROCEDURE FastMul (a, b : INTEGER) : INTEGER;
VAR c : INTEGER;
BEGIN
IF b = 0 THEN
c := 0
ELSIF ODD(b) THEN
c := a + FastMul (a, b-1)
ELSE
c := Double (FastMul (a, Halve (b)))
END;
RETURN c
END FastMul;
Exercise1-16 <---> Exercise1-18