Create a gist now

Instantly share code, notes, and snippets.

@vdloo /fibint.scm
Last active Aug 29, 2015

What would you like to do?
Fibonacci in finite fields, in racket
#!/usr/bin/env racket
#lang racket
(define (addmod a b p)
(if (> (- p b) a)
(+ a b)
(- (+ a b) p)
)
)
(define (submod a b p)
(if (>= a b)
(- a b)
(+ (- p b) a)
)
)
(define (mulmod a b p)
(mulmod_rec a b p 0)
)
(define (mulmod_rec a b p r)
(if (> b 0)
(mulmod_rec (addmod a a p)
(arithmetic-shift b -1)
p
(if (= 1 (bitwise-and b 1)) (addmod a r p) r)
)
r
)
)
(define (powmod a e p)
(powmod_rec a e p 1)
)
(define (powmod_rec a e p r)
(if (> e 0)
(powmod_rec (mulmod a a p)
(arithmetic-shift e -1)
p
(if (= 1 (bitwise-and e 1)) (mulmod r a p) r)
)
r
)
)
(define (fib n)
(define (q) 12200160415121876909)
(define (v) 833731445503647576)
(define (v_inv) 2606778372125104897)
(mulmod (submod (powmod (+ 1 (v)) n (q))
(powmod (- (+ (q) 1) (v)) n (q))
(q)
)
(mulmod (v_inv)
(powmod 2 (- (q) 1 n) (q))
(q)
)
(q)
)
)
(define (fib-iter n count result)
(display "Computing fib for ")(display count)(display ": ")(display result)(newline)
(when (< count n)
(fib-iter n
(+ count 1)
(fib count)
)
)
)
(define (multifib n)
(fib-iter n 1 0)
)
(multifib 93)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment