[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/YpIgShGQ    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Jul 23:
; fibonacci numbers

(define (make-matrix rows columns . value)
  (do ((m (make-vector rows)) (i 0 (+ i 1)))
      ((= i rows) m)
    (if (null? value)
        (vector-set! m i (make-vector columns))
        (vector-set! m i (make-vector columns (car value))))))

(define (matrix-rows x) (vector-length x))

(define (matrix-cols x) (vector-length (vector-ref x 0)))

(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))

(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))

(define-syntax for
  (syntax-rules ()
    ((for (var first past step) body ...)
      (let ((ge? (if (< first past) >= <=)))
        (do ((var first (+ var step)))
            ((ge? var past))
          body ...)))
    ((for (var first past) body ...)
      (let* ((f first) (p past) (s (if (< first past) 1 -1)))
        (for (var f p s) body ...)))
    ((for (var past) body ...)
      (let* ((p past)) (for (var 0 p) body ...)))))

(define (matrix-multiply a b)
  (let ((ar (matrix-rows a)) (ac (matrix-cols a))
        (br (matrix-rows b)) (bc (matrix-cols b)))
    (if (not (= ac br))
        (error 'matrix-multiply "incompatible matrices")
        (let ((c (make-matrix ar bc 0)))
          (for (i ar)
            (for (j bc)
              (for (k ac)
                (matrix-set! c i j
                  (+ (matrix-ref c i j)
                     (* (matrix-ref a i k)
                        (matrix-ref b k j)))))))
          c))))

(define (fib-r n)
  (cond ((zero? n) 0)
        ((< n 2) 1)
        (else (+ (fib-r (- n 1)) (fib-r (- n 2))))))

(define (fib-i n)
  (let loop ((n n) (f-1 1) (f-2 0))
    (if (zero? n) f-2
      (loop (- n 1) (+ f-1 f-2) f-1))))

(define (matrix-power m n)
  (cond ((= n 1) m)
        ((even? n)
          (matrix-power
            (matrix-multiply m m)
            (/ n 2)))
        (else (matrix-multiply m
                (matrix-power
                  (matrix-multiply m m)
                  (/ (- n 1) 2))))))

(define (fib-m n)
  (if (zero? n) 0
    (matrix-ref (matrix-power #(#(1 1) #(1 0)) n) 1 0)))

(time (display (fib-r 25)) (newline))
(time (display (fib-i 25000)) (newline))
(time (display (fib-m 25000)) (newline))


Output:
1
2
3
4
5
6
75025
cpu time: 10 real time: 75 gc time: 0
21954383555173030127807919148417209228490152223021557731451781127306623039982943883267310466977945532053447789511262879249321074277598649342389821271167000317023037581958331036091294783904894461090483531753647896023484077580249370783686222110280961428352592444708597429502479591730972971623526477512621198677489930449129788797302569454458871015985618528962408140946927219687925337982098609517463613938366079927050677100426207495007870012444175219878282744861963454097306999352486464480020994861720163408376221776254124881281835658238396811171475547840505577280497290764697852580918352378322451981389840912053934270867149239717640329604557541576368425538894540014339146367544914283895971346311130607438943726278698200780958269936947332930446203224041647084628106016969053337141620250841232902580338474709873632863922691594707073352162342891731746210915161327957042027991686940745388609739385687213054343998668027691253209167033978095596735703595258017865560021078274414539862767751625135062285905704743279755630794810946034661771129621261174405424347029151027998776643601668128975857440939626560529124238861131004612301427841460237117774205263152296380080149898573354916222065534328012435095624820387675200869971461610829066542024464229461137094069181446980196032624875044012403229642052200211413566229676357382234153337919908970086213041247507423210366778255874969067438963323643664961380931226103957879354697384207870258028725278842975999355024542015704816219975089555733150418809852037964675375675222997136226343633919669517811393620154294748245938743367234093817280458383573076740362329761729648498042175099300883073811637142163473196728542864568337684804226936776080367782088881358067961615858316246373433627323275529747475697240353727979625063567322076787903440004157536448402430858406937052414964517022034744937112947826964215660734325599665675573538758410526674131551019706191944832517439819740986140506254878543596251511651415270222121099180278295753782016097573025838953642113511919634000472763785338765264449619972174644768164103411445132547991934407958738645498931064009836979048546251816408572779082805930792609223625978885077369451586932680176815860451532508284458931534683102878058331199254091763847799991797925439867689112513498993904590424817166245312871082243446303881978512871071673104523003463650997468363309947301947327864551712035534879979165673056210960054240466328267162556672765028694125496464150876075988560627610324275167538562974806208469829226804402407894926748004450724290064602524059028499781439494258792206626526497264789913488498549763049980296252421806378787590574226047126518841802505360377946865717166068911319244741990807779309097580982803493650228877708981212947537034815749719553587416722072726597433851980905698152289702456694087939770602756659148688009692099704422330315770106618250494767360447695110245152793822499918977082605667351043297532794230171504223232002618663752808187498561271446172142920706630531150512826863140622015956861022857904529464336919104925028180985700701537351443373008714843649892786227516217270805562370936709290544103347776453402144800309556131699491089562077937143917640435044783246849170485832111985713053519848585557313899923504434894589099348339426350890609134009093644428725241352919341931605857780487611748443613810921897385067695943707572755921311231388427974347743194415409226833259754015081919595779600533639774073856897752044377637053455058712929015137222925183986456595375433122811828691587061103153821835682157694778786799429989630811360456676380608300587271624702899596696771081088637658867420118277775810890298563760042666720708612545456634707364997939290430991171498259602076764251097135935396244869013627624285782413136250262569763105966447864309008059632014470649651597717542559278502562088747761828804368423158145811955623401522427389323261240759969258694659866791266895384513578965744304224037115923123340136912517826579241888622557294190865643839950691753442580789076724858132822671420014662160060292760473482383061488488437068945071733990896915201872614506633425611306791456457671763247767089968843917827670882191270172241914682121418927082102694595321058885612073626573300380509475661675363078193788220946015150048141994989362588427966045522542553548406944721109199680016107826513060762736083510203030087621735400122712773161206417437397170099074998235309312849940687702132966450657447715656061712014176365975048707883485018667188684158999168283234250830400656149069398862673252457077775277687700680721586552800533257194717206937172689277021194747270431910243887014823739342015403939055735781523881651750036449516062936842303072047865186118401083903504442544340498354087649850999350506035606091865660173814044784938561092865618402665607761115884409442042493551455808245134144979794612868169975000315223112255314300181978801473442688282332779146194551018411523341712851118606806237176984304108507915433639635115169977229246135426696091280477423550091782970213406999961153049622653874886614706715392184925700388352189432893761114094696637751033905100343373987178536727536362703063030868995576313179198048436787355867956068455931062219695338964333961913451782174449643479001069903253526899196430613467544838316226807341377036587231777596875
cpu time: 70 real time: 518 gc time: 50
21954383555173030127807919148417209228490152223021557731451781127306623039982943883267310466977945532053447789511262879249321074277598649342389821271167000317023037581958331036091294783904894461090483531753647896023484077580249370783686222110280961428352592444708597429502479591730972971623526477512621198677489930449129788797302569454458871015985618528962408140946927219687925337982098609517463613938366079927050677100426207495007870012444175219878282744861963454097306999352486464480020994861720163408376221776254124881281835658238396811171475547840505577280497290764697852580918352378322451981389840912053934270867149239717640329604557541576368425538894540014339146367544914283895971346311130607438943726278698200780958269936947332930446203224041647084628106016969053337141620250841232902580338474709873632863922691594707073352162342891731746210915161327957042027991686940745388609739385687213054343998668027691253209167033978095596735703595258017865560021078274414539862767751625135062285905704743279755630794810946034661771129621261174405424347029151027998776643601668128975857440939626560529124238861131004612301427841460237117774205263152296380080149898573354916222065534328012435095624820387675200869971461610829066542024464229461137094069181446980196032624875044012403229642052200211413566229676357382234153337919908970086213041247507423210366778255874969067438963323643664961380931226103957879354697384207870258028725278842975999355024542015704816219975089555733150418809852037964675375675222997136226343633919669517811393620154294748245938743367234093817280458383573076740362329761729648498042175099300883073811637142163473196728542864568337684804226936776080367782088881358067961615858316246373433627323275529747475697240353727979625063567322076787903440004157536448402430858406937052414964517022034744937112947826964215660734325599665675573538758410526674131551019706191944832517439819740986140506254878543596251511651415270222121099180278295753782016097573025838953642113511919634000472763785338765264449619972174644768164103411445132547991934407958738645498931064009836979048546251816408572779082805930792609223625978885077369451586932680176815860451532508284458931534683102878058331199254091763847799991797925439867689112513498993904590424817166245312871082243446303881978512871071673104523003463650997468363309947301947327864551712035534879979165673056210960054240466328267162556672765028694125496464150876075988560627610324275167538562974806208469829226804402407894926748004450724290064602524059028499781439494258792206626526497264789913488498549763049980296252421806378787590574226047126518841802505360377946865717166068911319244741990807779309097580982803493650228877708981212947537034815749719553587416722072726597433851980905698152289702456694087939770602756659148688009692099704422330315770106618250494767360447695110245152793822499918977082605667351043297532794230171504223232002618663752808187498561271446172142920706630531150512826863140622015956861022857904529464336919104925028180985700701537351443373008714843649892786227516217270805562370936709290544103347776453402144800309556131699491089562077937143917640435044783246849170485832111985713053519848585557313899923504434894589099348339426350890609134009093644428725241352919341931605857780487611748443613810921897385067695943707572755921311231388427974347743194415409226833259754015081919595779600533639774073856897752044377637053455058712929015137222925183986456595375433122811828691587061103153821835682157694778786799429989630811360456676380608300587271624702899596696771081088637658867420118277775810890298563760042666720708612545456634707364997939290430991171498259602076764251097135935396244869013627624285782413136250262569763105966447864309008059632014470649651597717542559278502562088747761828804368423158145811955623401522427389323261240759969258694659866791266895384513578965744304224037115923123340136912517826579241888622557294190865643839950691753442580789076724858132822671420014662160060292760473482383061488488437068945071733990896915201872614506633425611306791456457671763247767089968843917827670882191270172241914682121418927082102694595321058885612073626573300380509475661675363078193788220946015150048141994989362588427966045522542553548406944721109199680016107826513060762736083510203030087621735400122712773161206417437397170099074998235309312849940687702132966450657447715656061712014176365975048707883485018667188684158999168283234250830400656149069398862673252457077775277687700680721586552800533257194717206937172689277021194747270431910243887014823739342015403939055735781523881651750036449516062936842303072047865186118401083903504442544340498354087649850999350506035606091865660173814044784938561092865618402665607761115884409442042493551455808245134144979794612868169975000315223112255314300181978801473442688282332779146194551018411523341712851118606806237176984304108507915433639635115169977229246135426696091280477423550091782970213406999961153049622653874886614706715392184925700388352189432893761114094696637751033905100343373987178536727536362703063030868995576313179198048436787355867956068455931062219695338964333961913451782174449643479001069903253526899196430613467544838316226807341377036587231777596875
cpu time: 0 real time: 6 gc time: 0


Create a new paste based on this one


Comments: