fastfib.clj

;; Anything you type in here will be executed
;; immediately with the results shown on the
;; right.


(import 'java.lang.Math)

(def fibmatrix [[1 1] [1 0]])

(defn matrix-times [[[a1 a2] [a3 a4]] [[b1 b2] [b3 b4]]]
  (let [ c1 (+' (*' a1 b1) (*' a2 b3))
         c2 (+' (*' a1 b2) (*' a2 b4))
         c3 (+' (*' a2 b1) (*' a4 b3))
         c4 (+' (*' a2 b2) (*' a4 b4))
        ]
  [[c1 c2] [c3 c4]]))

(defn matrix-square [m] (matrix-times m m))

(defn log2 [n] (/ (Math/log n) (Math/log 2)))

(defn iterate-n [n f x]
  (if (< n 1)
    x
    (recur (- n 1) f (f x))))

(defn fastfibmatrix [n]
  (let [ floor  (Math/floor (log2 n))
         delta  (Math/floor (- n (Math/pow 2 floor))) 
         ]
    (matrix-times (if (< delta 1)
                    [[1 0] [0 1]]
                    (fastfibmatrix delta))
                  (iterate-n floor matrix-square fibmatrix))))

(defn fastfib [n] (get-in (fastfibmatrix n) [0 0]))

(fastfib 10000)

; 54438373113565281338734260993750380135389184554695967026247715841208582865622349017083051547938960541173822675978026317384359584751116241439174702642959169925586334117906063048
; 08979353147610846625907275936789915067796008830659796664196582493772180038144115884104248099798469648737533718002816376331778192794110136926275097950980071359671802381471066991
; 26442147752544785876745689638080029622651331113599297627266794414001015758000435107774659358053625024617079180592264146790056907523218958681423678495938807564234837543863426396
; 35970733756260098962462668746112041739819404875062443709868654315626847186195620146126642232711815040367018825205314845875817193533529827837800351902529239517836689467661917953
; 88471244102846393544948461445077876252952096188759727288922076853739647586954315917243453719361126374392633731300589616724805173798630636811500308839674958710261952463135244749
; 95052041983051871683216232838597946272459197714546282183996957892237989121994317754697052161310810965599506382972612538482420078971090547540284381496119304650618661701229832889
; 64352733750792786069444761853525144421077928045979904561298129423809156055033032338919609162236698759922782923191896688017718575555520994653320128446502371153715141749290913104
; 89720345557750719664542523286202201950609148358522388271101670843305116994211577515125551025165593188816404834412955703882547752111157739578011586839707260256561482495646053870
; 02803313118614853998053970315557275296933995860798503815814462764338588285295358034248508454264464716815310015331804795674363968156533261525095711274804119281960221488491482843
; 89124178520174507305538928717857923509417743383331506898239354421988805429332440371194867215543576548565499134519271098919802665184564927827827212957649240235507595558205647569
; 36539487331765900020637312657064350970948264971003873351747771340331902810557566793178947002411880309460403436295347199746139227479154973035641263307423082405199999610154978466
; 7340458326852960388301120765629245998136251652347093963049734046445106365304163630823669242257761468288461791843224793434406079917883360676846711185597501N