Results 1 to 10 of 15

Thread: Fun with Fibonacci

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    57
    Posts
    95
    Rep Power
    25

    Fun with Fibonacci

    If F(n) is the nth number in the Fibonacci sequence and F(0)=0, F(1)=1 and F(n)=F(n-2)+F(n-1) then...

    If n is a multiple of 3 then F(n) is even.
    If n is a multiple of 15 then the last digit of F(n) is a zero.

    F(n) and F(n+60) have the same last digit.
    F(n) and F(n+300) have the same last two digits.
    F(n) and F(n+1500) have the same last three digits.
    F(n) and F(n+15000) have the same last four digits.
    F(n) and F(n+150000) have the same last five digits.
    F(n) and F(n+1500000) have the same last six digits.

    If you allow negative values for n then F(-n)=-F(n) if n is even and F(-n)=F(n) if n is odd.

    For large values of n the number of (decimal) digits in F(n) is approximately 0.209 n - 0.35, eg. F(1,000,000,000) has 208,987,640 digits. The exact formula is CEILING(n * log10(PHI) - log10(SQRT(5))) for larger n.
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

  2. #2
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    I made some Fibonacci definitions using Racket (<-- descendant of Scheme <-- dialect of Lisp).
    I ran the definitions from within DrRacket (the Racket IDE).
    (I think that running the definitions, compiles and loads them.)

    Then, I used the definitions from the Racket REPL (read-eval-print loop).

    Below, you can see the definitions, and the REPL interactions.

    First, I tested, fib, to determine if it functioned correctly.

    Next, I timed it for, (fib 100000), 1.739 seconds.

    Then, I timed it for, (fib 1000000), 306.756 seconds.

    Finally, I calculated the number of digits in, (fib 1000000), 208988.



    ; code -----------------------------------------------------------------
    
    #lang racket
    
    (define big-fib 0)
    
    (define (fib-time n)
      (let ([t1 (current-milliseconds)])
        (set! big-fib (fib n))
        (let ([t2 (current-milliseconds)])
          (/ (- t2 t1) 1000.0))))
    
    (define (fib n)
      (define (fib-iter a b count)
        (if (= count 0)
            b
            (fib-iter (+ a b) a (- count 1))))
      (fib-iter 1 0 n))
    
    ; REPL interactions ----------------------------------------------------
    
    Welcome to DrRacket, version 5.1 [3m].
    Language: racket; memory limit: 128 MB.
    > (fib 0)
    0
    > (fib 1)
    1
    > (fib 2)
    1
    > (fib 3)
    2
    > (fib 4)
    3
    > (fib 5)
    5
    > (fib 6)
    8
    > (fib 7)
    13
    > (fib-time 100000)
    1.739
    > (fib-time 1000000)
    306.756
    > (define big-fib-string (number->string big-fib))
    > (define big-fib-list (string->list big-fib-string))
    > (define big-fib-digits (length big-fib-list))
    > big-fib-digits
    208988
    >
    
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  3. #3
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    57
    Posts
    95
    Rep Power
    25
    Dan,

    Between fib(100,000) and fib(1,000,000) you have a time factor of 176. When I do the same with BigInt I get a factor of 107. I'm very impressed with Racket since that's an all-purpose language and you wrote the "driving" algorithm in Racket itself, while I did my utmost to optimise big-integer processing and wrote the driving algorithm in PowerBASIC.

    BigInt agrees: fib(1,000,000) has 208,988 decimals.
    Boole and Turing, help me!

    Primary programming: 200 MHz ARM StrongARM, RISC OS 4.02, BASIC V, ARM assembler.
    Secondary programming: 3.16 GHz Intel Core 2 Duo E8500, Vista Home Premium SP2, thinBasic, x86 assembler.

  4. #4
    Dan, have tried making an executable to see if the time is about the same?
    Last edited by jack; 09-04-2011 at 14:23.

  5. #5
    Dan, here's fib implementation that uses the indendity fib(3*n)=5*fib(n)^3+3*(-1)^n*fib(n) if n is odd otherwise it uses the indentity fib(3*n+1)=fib(n+1)^3+3*fib(n+1)*fib(n)^2-fib(n)^3, (I embedded your fib function.)
    if you substitute fib3n in your benchmark it's about four times faster
    (define (fib3n n)
      (define (fib-iter a b count) 
        (if (= count 0) 
            b 
            (fib-iter (+ a b) a (- count 1)))) 
      (if (< n 77)
          (fib-iter 1 0 n)
          (let ([m (quotient n 3)])
            (let ([f (fib-iter 1 0 m)])
              (if (< (* 3 m) n)
                  (let ([f1 (fib-iter 1 0 (+ 1 m))])
                    (- (+ (* f1 f1 f1) (* 3 f1 f f)) (* f f f)))
                  (+ (* 5 f f f) (* 3 (expt -1 m) f)))))))
    
    Last edited by jack; 10-04-2011 at 01:48.

  6. #6
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    No time now, guys, later.


    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Similar Threads

  1. Fibonacci sequence
    By macleay in forum Shout Box Area
    Replies: 1
    Last Post: 22-08-2011, 15:39
  2. Fibonacci by Oxygen
    By ErosOlmi in forum O2 JIT Compiler / Assembler / Oxygen project
    Replies: 13
    Last Post: 18-11-2010, 14:25

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •