Извините, янимагу

[self-mad]

Под катом — рассчёт n-го числа Фиббоначи за O(log(n)) на Scheme

//Я на самом деле уверен, что это ужасный код, учитывая, что я только начинаю и даже не в курсе великой магии макросов

(define (fib n) (define (psquared p q) (+ (* p p) (* q q))) (define (qsquared p q) (+ (* 2 (* p q)) (* q q))) (define (a-trans p q a b) (+ (* p a) (* q b))) (define (b-trans p q a b) (+ (* q a) (* q b ) (* p b))) (define (fibhelp a b p q n) (cond ((= n 0) b) ((= (remainder n 2) 0) (fibhelp a b (psquared p q) (qsquared p q) (/ n 2))) (else (fibhelp (a-trans a b p q) (b-trans a b p q) p q (- n 1)))) ) (define init-p 0) (define init-q 1) (define first-fib 1) (define second-fib 1) (cond ((< n 1) 0) ((< n 2) first-fib) (else (fibhelp first-fib second-fib init-p init-q (- n 2))) ) )