Skip to content

Instantly share code, notes, and snippets.

@vdloo

vdloo/fibint.scm

Last active August 29, 2015 14:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save vdloo/b3eed782c0b69617d718 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save vdloo/b3eed782c0b69617d718 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. vdloo revised this gist Jul 3, 2014. 1 changed file with 17 additions and 10 deletions.
    27 changes: 17 additions & 10 deletions fibint.scm
    View file
    Original file line number Diff line number Diff line change
    @@ -15,9 +15,13 @@
    )
    )

    (define (mulmod a b p r)
    (define (mulmod a b p)
    (mulmod_rec a b p 0)
    )

    (define (mulmod_rec a b p r)
    (if (> b 0)
    (mulmod (addmod a a p)
    (mulmod_rec (addmod a a p)
    (arithmetic-shift b -1)
    p
    (if (= 1 (bitwise-and b 1)) (addmod a r p) r)
    @@ -26,12 +30,16 @@
    )
    )

    (define (powmod a e p r)
    (define (powmod a e p)
    (powmod_rec a e p 1)
    )

    (define (powmod_rec a e p r)
    (if (> e 0)
    (powmod (mulmod a a p 0)
    (powmod_rec (mulmod a a p)
    (arithmetic-shift e -1)
    p
    (if (= 1 (bitwise-and e 1)) (mulmod r a p 0) r)
    (if (= 1 (bitwise-and e 1)) (mulmod r a p) r)
    )
    r
    )
    @@ -41,17 +49,15 @@
    (define (q) 12200160415121876909)
    (define (v) 833731445503647576)
    (define (v_inv) 2606778372125104897)
    (mulmod (submod (powmod (+ 1 (v)) n (q) 1)
    (powmod (- (+ (q) 1) (v)) n (q) 1)
    (mulmod (submod (powmod (+ 1 (v)) n (q))
    (powmod (- (+ (q) 1) (v)) n (q))
    (q)
    )
    (mulmod (v_inv)
    (powmod 2 (- (q) 1 n) (q) 1)
    (powmod 2 (- (q) 1 n) (q))
    (q)
    0
    )
    (q)
    0
    )
    )

    @@ -68,4 +74,5 @@
    (define (multifib n)
    (fib-iter n 1 0)
    )

    (multifib 93)
  2. vdloo revised this gist Jul 3, 2014. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion fibint.scm
    View file
    Original file line number Diff line number Diff line change
    @@ -68,4 +68,4 @@
    (define (multifib n)
    (fib-iter n 1 0)
    )
    (multifib 64)
    (multifib 93)
  3. vdloo created this gist Jul 3, 2014.
    71 changes: 71 additions & 0 deletions fibint.scm
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,71 @@
    #!/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 r)
    (if (> b 0)
    (mulmod (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 r)
    (if (> e 0)
    (powmod (mulmod a a p 0)
    (arithmetic-shift e -1)
    p
    (if (= 1 (bitwise-and e 1)) (mulmod r a p 0) r)
    )
    r
    )
    )

    (define (fib n)
    (define (q) 12200160415121876909)
    (define (v) 833731445503647576)
    (define (v_inv) 2606778372125104897)
    (mulmod (submod (powmod (+ 1 (v)) n (q) 1)
    (powmod (- (+ (q) 1) (v)) n (q) 1)
    (q)
    )
    (mulmod (v_inv)
    (powmod 2 (- (q) 1 n) (q) 1)
    (q)
    0
    )
    (q)
    0
    )
    )

    (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 64)