Exercise1-18 <---> Exercise1-20

Exercise 1.19.

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a <- a + b and b <- a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq, where Tpq transforms the pair (a,b) according to a <- bq + aq + ap and b <- bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps: 

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(This exercise was suggested to us by Joe Stoy, based on an example in Kaldewaij 1990. )

Ru: Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов. Вспомните трансформацию переменных состояния a и b процесса fib-iter из раздела 1.2.2: a <- a + b и b <- a. Назовем эту трансформацию T и заметим, что n-кратное применение T, начиная с 1 и 0, дает нам пару Fib(n + 1) и Fib(n). Другими словами, числа Фибоначчи получаются путем применения Tn, n-ой степени трансформации T, к паре (1,0). Теперь рассмотрим T как частный случай p = 0, q = 1 в семействе трансформаций Tpq, где Tpq преобразует пару (a, b) по правилу a <- bq + aq + ap, b <- bp + aq. Покажите, что двукратное применение трансформации Tpq равносильно однократному применению трансформации Tp'q' того же типа, и вычислите p' и q' через p и q. Это дает нам прямой способ возводить такие трансформации в квадрат, и таким образом, мы можем вычислить Tn с помощью последовательного возведения в квадрат, как в процедуре fast-expt. Используя все эти идеи, завершите следующую процедуру, которая дает результат за логарифмическое число шагов: 

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; вычислить p'
                   <??>      ; вычислить q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(Это упражнение нам предложил Джо Стой на основе примера из Kaldewaij 1990.)

Scheme solution:

Tpq:

a <- bq + aq + ap

b <- bp + aq

T2pq:

a <- (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p

b <- (bp + aq)p + (bq + aq + ap)q

So, in Tp'q':

p' = p2 + q2

q' = 2pq + q2

Let's put this in Scheme code pattern, which is given in exercise: 

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (square p) (square q))
                   (+ (* 2 p q)  (square q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

Haskell solution: 

fib n = fib'iter 1 0 0 1 n
  where
    fib'iter a b p q count
        | count == 0 = b
        | even count = fib'iter a b (p*p + q*q) (2*p*q + q*q) (count `div` 2)
        | otherwise  = fib'iter (b*q + a*q + a*p) (b*p + a*q) p q (count - 1)

Another Haskell solution (from http://www.codecodex.com/wiki/index.php?title=Fibonacci_sequence#Haskell ) 

fib_mat 0 = 1
fib_mat 1 = 1
fib_mat n = fst $ fst $ pow (n-1) ((1,1),(1,0))
  where
    pow 0 _ = ((1,0),(0,1))
    pow 1 m = m
    pow n m = let (q,r) = divMod n 2
                  y = pow q m
                  z = prod y y
              in if r == 0 then z else prod z m

    prod ((a,b),(c,d)) ((a',b'),(c',d'))
        = ( ( a*a' + b*c', a*b' + b*d' )
          , ( c*a' + d*c', c*b' + d*d' ) )

And finest Haskell solution from Lennart Augustsson ( http://www.reddit.com/comments/61rmh/algorithm_death_match_arbitrary_precision_c_and/c02kayq ) 

type GS = (Integer, Integer)
instance Num GS where
    (a,b) * (c,d) = (a*(c+d) + b*c, a*c + b*d)

fib n = fst (x^n)
  where x = (1,0) :: GS

OCaml solution: 

let fib n =
  let rec fib_iter a b p q count =
    if count = 0 then
      b
    else if count mod 2 = 0 then
      fib_iter a b (p*p + q*q) (2*p*q + q*q) (count / 2)
    else
      fib_iter (b*q + a*q + a*p) (b*p + a*q) p q (count - 1)
  in
    fib_iter 1 0 0 1 n

Standard ML solution: 

fun fib n = let
  fun fib_iter (a, b, p, q, count) =
    if count = 0 then
      b
    else if count mod 2 = 0 then
      fib_iter (a, b, p*p + q*q, 2*p*q + q*q, count div 2)
    else
      fib_iter (b*q + a*q + a*p, b*p + a*q, p, q, count - 1)
in
  fib_iter (1, 0, 0, 1, n)
end

Oberon/Component Pascal solution: 

PROCEDURE Fib (n : INTEGER) : INTEGER;
VAR a, b, p, q, count, t : INTEGER;
BEGIN
  a := 1; b := 0; p := 0; q := 1; count := n;
  WHILE count # 0 DO
    IF ODD(count) THEN
      t := a*q;
      a := b*q + t + a*p;
      b := b*p + t;
      DEC(count)
    ELSE
      t := p;
      p := p*p   + q*q;
      q := 2*t*q + q*q;
      count := count DIV 2
    END
  END;
  RETURN b
END Fib;

Exercise1-18 <---> Exercise1-20

Comments

Блин, как же я когда-то мучился с этой задачкой, а до такого простого решения (p' = p2 + q2, q' = 2pq + q2) не допетрил... :о( Решил на Хаскелле с привлечением умножения матриц, получил монстра: 
fib n | n < 3      = 1
      | odd n      = f1
      | otherwise  = f2
  where
    (f1, f2) = fibm ((n-1) `div` 2)

    fibm n = ((1, 1, 1, 2) |^| n) |#| (1, 1)

    mat |^| n = m_fpow n mat (1, 0, 0, 1)
      where
        m_fpow 0 _ w = w
        m_fpow k m w  | even k    = m_fpow (k `div` 2)  (m |*| m)      w
                      | otherwise = m_fpow (k  -    1)      m      (m |*| w)

    (a11,a12,a21,a22) |#| (b11,b21)  = (a11*b11 + a12*b21, a21*b11 + a22*b21)

    (a11,a12,a21,a22) |*| (b11,b12,b21,b22) = (m2+m3, t1+m5+m6, t2-m7, t2+m5)
      where
        s1 = a21+a22; s2 = s1-a11;  s3 = a11-a21; s4 = a12-s2
        s5 = b12-b11; s6 = b22-s5;  s7 = b22-b12; s8 = s6-b21
        m1 =  s2*s6;  m2 = a11*b11; m3 = a12*b21; m4 = s3*s7
        m5 =  s1*s5;  m6 = s4*b22;  m7 = a22*s8
        t1 =  m1+m2;  t2 = t1+m4

потом нашёл более простой и быстрый вариант по ссылке http://www.codecodex.com/wiki/index.php?title=Fibonacci_sequence#Haskell , мда... :о))

Posted by Geniepro at 2007-09-18 21:45:22

I found this exercise a lot easier to solve by resorting to linear algebra.

If we consider the column vector [a b]T, the transformation T and Tpq can be expressed by square matrices: T = [1 1; 1 0] Tpq = [p+q q; q p]

Multiplying T or Tpq by the aforementioned vector actually computes the desired transformation.

Therefore, we can compute Tp'q' in a straightforward way as Tp'q' = Tpq2

Posted by 151 at 2008-06-25 01:44:01 X

:) :)) :( ;) :\ |) X-( B) Markup

Exercise1-19 (last edited 2009-03-24 02:02:17 by FirstnameLastname)