Thread: Fibonacci and decimal representation bounds

  1. #1
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694

    Fibonacci and decimal representation bounds

    This is one task for hw, but I really have no clue. Do you?

    Given b and k to be positive integers and F_k < b < F_(k+1), where Fk is the k-th fibonacci number.

    Let n(b) to be the number of digits that represent b, in the decimal system.

    Give the best in your opinion upper and lower bounds for n(b). The bounds have k inside them.
    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. #2
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Well, the sequence continues infinitely so in all reality, it'd take an arbitrary number of bits to represent an arbitrary number in the sequence (or in between values thereof). If b is some value in-between two terms in the sequence, then you can use that to narrow down how many bits you would truly require.

    It'd basically be an arbitrarily sized unsigned integer.

    I'm not actually sure how libraries like GMP work in the sense that they're arbitrarily precise but I'm assuming you'd just declare a structure with a bitfield, right? Like, you can declare bitfields in structs as large as you want, right?

    Edit :

    Okay, I did find something. This is a very simple suggested way of implementing a big number : http://www.cplusplus.com/forum/lounge/32041/

    I'm actually not sure about the specifics of your assignment but if I was given that question, that's what I would write, that theoretically an arbitrary number of bits should be used but physical constraints sort of limit that so it all depends where you want b to be.
    Last edited by MutantJohn; 01-30-2014 at 10:52 AM.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    So here's the Wikipedia page: Fibonacci number - Wikipedia, the free encyclopedia
    And here's the OEIS page: A000045 - OEIS

    I would make a mapping of k versus the number of digits in F_(k), paying extra attention to where the number of digits changes. E.g. F_(7) is the first two digit number, F_(12) the first three digit number, etc. Then, see what expression you can find that maps k to number of digits. Also note, it says "best in your opinion". I don't know that they're actually looking for the best, or most accurate, but want to see what you can come up with.

    Note, I think the OEIS page has one or two little blurbs that can help you, but I'm no math expert.

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I also thought what anduril said, but I couldn't find the mapping. Will look again in the 2nd link.

    It seems that the golden ratio φ (you know, the number of Phidias of Acropolis) is the key to the answer here.
    Last edited by std10093; 01-30-2014 at 11:25 AM.
    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

  5. #5
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    @MutantJohn:
    I think this is more a "pure math" question, and not about programming or how to represent such numbers in a computer. std10093 can confirm.

  6. #6
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I do confirm.
    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

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Good. I think you're right about φ. Now, how to take φ and k, and get the number of digits. Start by using φ and k to estimate the k'th term of the Fibonacci sequence. From there, it should be fairly easy to get the number of digits.

    Note, my attempt gave the following. I'm limited to 92 terms based on the size of an unsigned long long on my system. Not perfect, but reasonably accurate:
    Code:
    Term  Fibonacci number      Digits  Est Digits  
    ----  --------------------  ------  ------------
       2                     1       1  0.417975
       3                     2       1  0.626963
       4                     3       1  0.835951
       5                     5       1  1.044938
       6                     8       1  1.253926
       7                    13       2  1.462913
       8                    21       2  1.671901
       9                    34       2  1.880889
      10                    55       2  2.089876
      11                    89       2  2.298864
      12                   144       3  2.507852
      13                   233       3  2.716839
      14                   377       3  2.925827
      15                   610       3  3.134815
      16                   987       3  3.343802
      17                  1597       4  3.552790
      18                  2584       4  3.761778
      19                  4181       4  3.970765
      20                  6765       4  4.179753
      21                 10946       5  4.388740
      22                 17711       5  4.597728
      23                 28657       5  4.806716
      24                 46368       5  5.015703
      25                 75025       5  5.224691
      26                121393       6  5.433679
      27                196418       6  5.642666
      28                317811       6  5.851654
      29                514229       6  6.060642
      30                832040       6  6.269629
      31               1346269       7  6.478617
      32               2178309       7  6.687604
      33               3524578       7  6.896592
      34               5702887       7  7.105580
      35               9227465       7  7.314567
      36              14930352       8  7.523555
      37              24157817       8  7.732543
      38              39088169       8  7.941530
      39              63245986       8  8.150518
      40             102334155       9  8.359506
      41             165580141       9  8.568493
      42             267914296       9  8.777481
      43             433494437       9  8.986469
      44             701408733       9  9.195456
      45            1134903170      10  9.404444
      46            1836311903      10  9.613431
      47            2971215073      10  9.822419
      48            4807526976      10  10.031407
      49            7778742049      10  10.240394
      50           12586269025      11  10.449382
      51           20365011074      11  10.658370
      52           32951280099      11  10.867357
      53           53316291173      11  11.076345
      54           86267571272      11  11.285333
      55          139583862445      12  11.494320
      56          225851433717      12  11.703308
      57          365435296162      12  11.912295
      58          591286729879      12  12.121283
      59          956722026041      12  12.330271
      60         1548008755920      13  12.539258
      61         2504730781961      13  12.748246
      62         4052739537881      13  12.957234
      63         6557470319842      13  13.166221
      64        10610209857723      14  13.375209
      65        17167680177565      14  13.584197
      66        27777890035288      14  13.793184
      67        44945570212853      14  14.002172
      68        72723460248141      14  14.211160
      69       117669030460994      15  14.420147
      70       190392490709135      15  14.629135
      71       308061521170129      15  14.838122
      72       498454011879264      15  15.047110
      73       806515533049393      15  15.256098
      74      1304969544928657      16  15.465085
      75      2111485077978050      16  15.674073
      76      3416454622906707      16  15.883061
      77      5527939700884757      16  16.092048
      78      8944394323791464      16  16.301036
      79     14472334024676221      17  16.510024
      80     23416728348467685      17  16.719011
      81     37889062373143906      17  16.927999
      82     61305790721611591      17  17.136987
      83     99194853094755497      17  17.345974
      84    160500643816367088      18  17.554962
      85    259695496911122585      18  17.763949
      86    420196140727489673      18  17.972937
      87    679891637638612258      18  18.181925
      88   1100087778366101931      19  18.390912
      89   1779979416004714189      19  18.599900
      90   2880067194370816120      19  18.808888
      91   4660046610375530309      19  19.017875
      92   7540113804746346429      19  19.226863

  8. #8
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Oh, I totally read that problem wrong, ha ha. I thought it was asking how you code something like that. I thought they wanted the upper and lower bounds on the number of bits, not digits. Oh my God.

  9. #9

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    Note, my attempt gave the following. I'm limited to 92 terms based on the size of an unsigned long long on my system.
    O_o

    Quick and Dirty: Useful classes

    Certainly nothing like "GMP" or anything, but for a quick fix for sampling like this thread, a decent set of utilities.

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

  11. #11
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    It's ok MutantJohn.

    The number of results by anduril is ok, so need for GMP or such here, at least for now.

    @anduril, can you explain the fourth of your column?
    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

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by std10093 View Post
    @anduril, can you explain the fourth of your column?
    That is the estimated number of digits in F_(k) my formula produces. Basically, it is the bounding values for n(b) in your problem. I use a very rough forumula, compared to the more accurate ones linked in Epy's post. But if you haven't read those links yet, I recommend trying to figure out a rough formula on your own. I think this is the purpose of the assignment, and it's a good mental exercise anyway. "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).

  13. #13
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Quote Originally Posted by phantomotap View Post
    Certainly nothing like "GMP"
    True, I tried with it and get very inaccurate results. (or my code sucks :P )
    Last edited by std10093; 01-30-2014 at 06:04 PM.
    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

  14. #14
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by std10093 View Post
    True, I tried with it and get very inaccurate results. (or my code sucks :P )
    What exactly did you try with GMP? Maybe your estimate formula is wrong. You could post your code.

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    What exactly did you try with GMP? Maybe your estimate formula is wrong. You could post your code.
    O_o

    Well, I think he was referring to using the "useful classes" I linked, but yeah, he should post the code.

    If nothing else, I'm sure iMalc would like to correct any bugs.

    Soma
    “Salem Was Wrong!” -- Pedant Necromancer
    “Four isn't random!” -- Gibbering Mouther

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, 07: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