fibnat.py

##n番目のフィボナッチ数をLで割ったあまり
def sq((a,b)):
    return ((a*a+2*a*b)%L,(a*a+b*b)%L)

def succ((a,b)):
    return ((a+b)%L,a%L)

def fibb(n):
    if n==1:return (1,0)
    if n&1:return succ(fibb(n-1))
    else:return sq(fibb(n/2))

def fib(n):
    return fibb(n+1)[1]

fibnat.scm

(define (sq x) (let ((a (car x))(b (cdr x))) (cons (% (+(* a a)(* 2 a b))L) (%(+(* a a)(* b b))L))))
(define (succ x) (let ((a (car x))(b (cdr x))) (cons (% (+ a b) L) a)))
(define fibb (lambda (n) (if (= n 1) (cons 1 0) (if (odd? n) (succ (fibb (- n 1))) (sq (fibb (/ n 2)))))))
(define (fib x) (cdr (fibb (+ 1 x))))

(define % remainder)

matsubi_fib.scm

(define (sq x) (let ((a (car x))(b (cdr x))) (cons (% (+(* a a)(* 2 a b))L) (%(+(* a a)(* b b))L))))
(define (succ x) (let ((a (car x))(b (cdr x))) (cons (% (+ a b) L) a)))
(define fibb (lambda (n func) (if (= n 1) (func (cons 1 0)) (if (odd? n)  (fibb (- n 1) (lambda (x) (func (succ x)))) (fibb (/ n 2) (lambda (x) (func (sq x))))))))
(define (fib x) (cdr (fibb (+ 1 x) (lambda (n) n))))

(define % remainder)

short_fib.py

def fib(n):
 return int(pow(1.618033988,n)+.5)