Exercise1-15 <---> Exercise1-17

Exercise 1.16.

Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.

(Hint: Using the observation that (b^n/2)² = (b²)^n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product abⁿ is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

Ru: Напишите процедуру, которая развивается в виде итеративного процесса и реализует возведение в степень за логарифмическое число шагов, как fast-expt. (Указание: используя наблюдение, что (b^n/2)² = (b²)^n/2, храните, помимо значения степени n и основания b, дополнительную переменную состояния a, и определите переход между состояниями так, чтобы произведение abⁿ от шага к шагу не менялось. Вначале значение a берется равным 1, а ответ получается как значение a в момент окончания процесса. В общем случае метод определения инварианта (invariant quantity), который не изменяется при переходе между шагами, является мощным способом размышления о построении итеративных алгоритмов.)

Scheme solution:

(define (fast-exp-iter b n)
  (define (exp b n a)
    (cond ((= n 0) a)
          ((even? n) (exp (square b) (/ n 2) a))
          (else (exp b (- n 1) (* b a)))))
  (exp b n 1))

Haskell solution:

fast'exp'iter b n = exp' b n 1
  where
    exp' b n a | n == 0    = a
               | even n    = exp' (b*b) (n `div` 2)    a
               | otherwise = exp'   b   (n   -   1) (a * b)

OCaml solution:

let fast_exp_iter b n =
  let rec exp' b n a =
    if n = 0 then
      a
    else if n mod 2 = 0 then
      exp' (b*b) (n/2)   a
    else
      exp'   b   (n-1) (a*b)
  in
    exp' b n 1

Standard ML solution:

fun fast_exp_iter (b, n) = let
  fun exp' (b, n, a) =
    if n = 0 then
      a
    else if n mod 2 = 0 then
      exp' (b*b, n div 2,  a )
    else
      exp' ( b , n  -  1, a*b)
in
  exp' (b, n, 1)
end

Oberon/Component Pascal solution:

PROCEDURE FastExpIter (b : REAL; n : INTEGER) : REAL;
VAR a, c : REAL; 
    k : INTEGER;
BEGIN
  a := 1.0; c := b; k := n;
  WHILE k # 0 DO
    IF ODD(k) THEN
      a := a * c;
      DEC(k)
    ELSE
      c := c * c;
      k := k DIV 2
    END
  END;
  RETURN a
END FastExpIter;

Exercise1-15 <---> Exercise1-17

Comments

I have the same solution: (define (fast-exp-iter b n) (define (exp b n a) (cond ((= n 0) a) ((even? n) (exp (square b) (/ n 2) a)) (else (exp b (- n 1) (* b a))))) (exp b n 1))

Posted by IvanVeselov at 2007-09-13 16:13:05

What you say about it (define (fast-expt-iter a b power) (cond ((= power 0) a) ((= power 1) (* a b)) ((even? power) (fast-expt-iter a (* b b) (/ power 2))) (else (fast-expt-iter (* a b) (* b b) (/ (- power 1) 2))))) (define (fast-expt b power) (fast-expt-iter 1 b power))

Posted by 84 at 2008-09-03 13:50:47 X

Add your comment Markup