Page 1 of 2 12 LastLast
Results 1 to 10 of 15

Thread: Fun with Fibonacci

  1. #1
    Member Johannes's Avatar
    Join Date
    Nov 2010
    Location
    Wuustwezel, Belgium
    Age
    56
    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
    56
    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

  7. #7
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152

    n^n

    I had an idea I wanted to try as soon as I got home, before I looked at anything else.

    So, I worked on this.

    Basically, I wanted to see if I could get Racket to do a calculation that would produce a 5 million digit number.

    Why, 5 million?

    If you assume that each line on a page can display 100 digits, and a page has 50 lines, then, 5 million digits corresponds to 1000 pages.

    So, I wanted to see if Racket could calculate a number that would be 1000 pages long.

    By default, DrRacket uses 128 MB. I found in the "Racket" menu, how to change the memory to be unlimited, and, I did that.

    I decided to use as my function, n^n.

    The number of digits in n^n, is, --> ceiling(n * log10(n)).

    In order to get 5 million digits, I figured out that I needed n to be approximately, 844,000.

    So, I used 844,123, --> so that Racket would not have a lot of zero multiplications.

    For, 844,123, ceiling(n * log10(n)) = 5,002,616.

    Below, is the code, and the REPL interactions.

    It took Racket less than 22 seconds on my mediocre computer, to do the calculation of the number.

    Interestingly, it took Racket longer than 22 seconds to do the calculation of the number of digits in the number.

    (I played around with using n^n^n, instead of n^n, but, that function grows too fast. I can't imagine what n^n^n^n would do. Probably, for n = 3, my computer would explode!)

    (I guess, at least in this case, it doesn't matter if you use, "#lang scheme", or, "#lang racket".)

    (Now that I've, "scratched this itch", I can return to Fibonacci.)



    ; code -----------------------------------------------------------------------
    
    #lang scheme
    
    (define big-n^n 0)
    
    (define (n^n-time n)
      (let ([t1 (current-milliseconds)])
        (set! big-n^n (n^n n))
        (let ([t2 (current-milliseconds)])
          (/ (- t2 t1) 1000.0))))
    
    
    (define (n^n n) (expt n n))
    
    (define (num-digits n)
      (let* ([n-string (number->string n)]
             [n-list (string->list n-string)]
             [n-digits (length n-list)])
        n-digits))
    
    ; REPL interactions ----------------------------------------------------------
    
    Welcome to DrRacket, version 5.1 [3m].
    Language: scheme.
    > (n^n-time 844123)
    21.527
    > (num-digits big-n^n)
    5002616
    >
    
    Last edited by danbaron; 10-04-2011 at 07:11.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  8. #8

  9. #9
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    I verified that you are absolutely correct about fib3n, Johan.
    I got more than a 6 times speed increase.

    ; code ----------------------------------------------------------------
    
    #lang scheme
    (define big-fib 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))
    
    (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)))))))
    
    (define (fib-time f n)
      (let ([t1 (current-milliseconds)])
        (set! big-fib (f n))
        (let ([t2 (current-milliseconds)])
          (/ (- t2 t1) 1000.0))))
    
    ; REPL interactions ---------------------------------------------------
    
    Welcome to DrRacket, version 5.1 [3m].
    Language: scheme.
    > (fib-time fib 1000000)
    272.155
    > (fib-time fib3n 1000000)
    42.503
    >
    

    Last edited by danbaron; 11-04-2011 at 07:18.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  10. #10
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    You asked about running an executable, Johan.
    I made an executable from the following file.
    It ran in a console window.

    #lang scheme
    (define big-fib 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))
    
    (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)))))))
    
    (define (fib-time f n)
      (let ([t1 (current-milliseconds)])
        (set! big-fib (f n))
        (let ([t2 (current-milliseconds)])
          (/ (- t2 t1) 1000.0))))
    
    (print (fib-time fib 1000000))
    (printf "\n")
    (print (fib-time fib3n 1000000))
    (printf "\n")
    (read-line)
    

    The times were,

    203.772 and 25.764.

    While from within DrRacket, they were, 272.155, and 42.503.

    So, there is somewhat of a speed increase.

    The downside for executables is that, just to print, "hello", the file size is 4699 KB - at least it is for me.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Page 1 of 2 12 LastLast

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
  •