Like Tree2Likes

Fibonacci and decimal representation bounds

This is a discussion on Fibonacci and decimal representation bounds within the Tech Board forums, part of the Community Boards category; No, I was reffering to the GMP, but yes, I can say for sure that this is a buggy code ...

  1. #16
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    No, I was reffering to the GMP, but yes, I can say for sure that this is a buggy code of mine. Couldn't get a really good approach and the last thing I tried was something like this:
    Code:
    double test_dig(double a) {// LOG (Phi^1000/√5)
      double phi = 1.618033;
      double sqrt_5 = 2.2360679775;
      //return (a*phi - (0.34948500216));
      std::cout << pow(phi, a) << std::endl;
      return log10(pow(phi, a)/sqrt_5);
    }
    
    int main() {
            double aa = 1000;
            
            std::cout << "1 = " << test_dig(aa) << std::endl;
            std::cout <<"2 = " << test_dig(2) << std::endl;
            std::cout <<"3 = " << test_dig(3) << std::endl;
            std::cout <<"5 = " << test_dig(5) << std::endl;
            std::cout <<"8 = " << test_dig(8) << std::endl;
            std::cout <<"13 = " << test_dig(13) << std::endl;
            aa = 21;
            std::cout << aa << " = " << test_dig(aa) << std::endl;
            aa = 34;
            return 0;
    }
    However, I did face the same fact as anduril:
    ""Tuning" it to be more accurate would be fun if I had the time, but probably also goes beyond my current math skills (which have degraded significantly since I finished school)."
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  2. #17
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Well, the Fibonacci sequence grows polynomially (specifically, quadratically), therefore the number of digits is going to be proportional to log(k). I am too lazy to put tighter bounds than that...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #18
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by brewbuck View Post
    Well, the Fibonacci sequence grows polynomially (specifically, quadratically), therefore the number of digits is going to be proportional to log(k). I am too lazy to put tighter bounds than that...
    The link of Epy provides a better-ready one, based on this thought and mine (the relation with phi)
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #19
    Epy
    Epy is offline
    Fortran lover Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    978
    Quote Originally Posted by brewbuck View Post
    Well, the Fibonacci sequence grows polynomially (specifically, quadratically), therefore the number of digits is going to be proportional to log(k). I am too lazy to put tighter bounds than that...
    It grows exponentially and so the digits are proportional to k.

  5. #20
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,370
    It grows exponentially and so the digits are proportional to k.
    O_o

    The growth "trends" but is never constant.

    The secondary "term"--not mathematics guy--is a constant `log(φ)'.

    The tertiary "term" is also a constant `log(5)/2'.

    As it grows, the measure is more "geometric" with "n".

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

  6. #21
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Quote Originally Posted by Epy View Post
    It grows exponentially and so the digits are proportional to k.
    You're right. That wrong piece of information has been in my head for a very long time...
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #22
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,370
    O_o

    So this latest post shows up and I spend ten minutes trying to figure out how the it could have actual exponential growth.

    *derp*

    I got muddled up in thinking about `floor(log10(fib(n)))'.

    Soma
    “Often out of periods of losing come the greatest strivings toward a new winning streak.” -- Fred Rogers
    “Salem Was Wrong!” -- Pedant Necromancer

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Convert Decimal IP To Dotted Decimal Notation
    By MaSSaSLaYeR in forum C Programming
    Replies: 11
    Last Post: 11-16-2011, 06:18 PM
  2. out of bounds
    By IDK_22 in forum C++ Programming
    Replies: 10
    Last Post: 02-22-2009, 10:55 PM
  3. how to convert decimal to hexa decimal in C/
    By kalamram in forum C Programming
    Replies: 4
    Last Post: 09-03-2007, 08:39 AM
  4. decimal to binary, decimal to hexadecimal and vice versa
    By Unregistered in forum C++ Programming
    Replies: 9
    Last Post: 12-08-2001, 11:07 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21