Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

caculate the 200th Fibonacci number

JiaJia Member Posts: 20
Hi, knight-errant,

How to get the 200th Fibonacci number F(200)? I don't know how to estimate its lenth, and where to put the very big number. so no way to go on...
F(n)=F(n-1) + f(n-2) where f(0)= 0, f(1)= 1

Thank you for your time.

Jia

Comments

  • Josh CodeJosh Code Member Posts: 675
    : Hi, knight-errant,
    :
    : How to get the 200th Fibonacci number F(200)? I don't know how to estimate its lenth, and where to put the very big number. so no way to go on...
    : F(n)=F(n-1) + f(n-2) where f(0)= 0, f(1)= 1
    :
    : Thank you for your time.
    :
    : Jia
    :

    I created a program that calculates basically any fibinacci number. It probably won't work for fib(10000000), but it does work for fib(200). My program was made in Delphi and it wasn't easy.

    I could send you the source, if you want.

    What I did was basically make a new type of number. This new type was actually a dynamic array of word. I made some functions to store normal integer values into the array. I also made a function that could add 2 of these arrays together. The actual fibinocci function was programmed a lot like a normal fibinocci function based on integer math except that it called my functions to add the values together.

    Also, there was a function to convert the values in the array to hexidecimal to display the result.

    The way the adding worked, was in a loop from the lowest order part of the number to the highest order, simply adding each word at a time. If the sum of 2 words was greater than FFFFh, a 1 was carried to the next addition.












    ps: the 200th fibinocci number is 017903BD1BD927DC58766E6533A576B3F1535622h

  • DariusDarius Member Posts: 1,666
    : : Hi, knight-errant,
    : :
    : : How to get the 200th Fibonacci number F(200)? I don't know how to estimate its lenth, and where to put the very big number. so no way to go on...
    : : F(n)=F(n-1) + f(n-2) where f(0)= 0, f(1)= 1
    : :
    : : Thank you for your time.
    : :
    : : Jia
    : :
    :
    : I created a program that calculates basically any fibinacci number. It probably won't work for fib(10000000), but it does work for fib(200). My program was made in Delphi and it wasn't easy.
    :
    : I could send you the source, if you want.
    :
    : What I did was basically make a new type of number. This new type was actually a dynamic array of word. I made some functions to store normal integer values into the array. I also made a function that could add 2 of these arrays together. The actual fibinocci function was programmed a lot like a normal fibinocci function based on integer math except that it called my functions to add the values together.
    :
    : Also, there was a function to convert the values in the array to hexidecimal to display the result.
    :
    : The way the adding worked, was in a loop from the lowest order part of the number to the highest order, simply adding each word at a time. If the sum of 2 words was greater than FFFFh, a 1 was carried to the next addition.
    :

    Basically, that's what you need to do. You need to use arbitrary/extended precision calculation. As the Art of Assembly (webster.ucr.edu) already has a good section on extended precision arithmetic at the assembly level, I'll simply refer you to that. On a side note, I'd recommend the iterative version of the fibonacci sequence is very straightforward and it isn't exponential in complexity (it's linear). There actually is an even better method that's only logarithmic in time complexity, but it isn't as straightforward (and while it isn't that complex, you don't really need it here). Outputting in hexadecimal isn't hard at all from that, outputting decimal is more difficult because the first digit potentially depends on the last digit (whereas hexadecimally no digit depends on any other digit). This is an artifact of using "digits" that are base an integer power of 16 (you'll likely be using base 2^32 or 2^16 "digits" which are an integer power of 16 (2^32=16^8 2^16=16^4).)

    As a note to Josh Code, if you implement the code the way you describe it then you can easily make it as simple to output in decimal as it is to output in hexadecimal now simply use "digits" that are based on an integer power of 10, i.e. "carry" if x is less than 10,000 (or any other power of ten you feel like). Then printing out each "digit" separately in decimal will be the same as printing the whole number in decimal.

    "We can't do nothing and think someone else will make it right."
    -Kyoto Now, Bad Religion

  • JiaJia Member Posts: 20
    Hi, Josh and Darius,
    Thank you for your detailed explanations.

    I got the Josh's idea, I try to use the "dynamic array" concept in my assembly coding, but I don't know Delphi, if it's not that difficult to read the code, I'd like to have a look at it.

    Darius's idea is very attractive, I need some time to think it over. Are you sure the web address :"webster.ucr.edu" is right?

    Thanks a lot!

    : : : Hi, knight-errant,
    : : :
    : : : How to get the 200th Fibonacci number F(200)? I don't know how to estimate its lenth, and where to put the very big number. so no way to go on...
    : : : F(n)=F(n-1) + f(n-2) where f(0)= 0, f(1)= 1
    : : :
    : : : Thank you for your time.
    : : :
    : : : Jia
    : : :
    : :
    : : I created a program that calculates basically any fibinacci number. It probably won't work for fib(10000000), but it does work for fib(200). My program was made in Delphi and it wasn't easy.
    : :
    : : I could send you the source, if you want.
    : :
    : : What I did was basically make a new type of number. This new type was actually a dynamic array of word. I made some functions to store normal integer values into the array. I also made a function that could add 2 of these arrays together. The actual fibinocci function was programmed a lot like a normal fibinocci function based on integer math except that it called my functions to add the values together.
    : :
    : : Also, there was a function to convert the values in the array to hexidecimal to display the result.
    : :
    : : The way the adding worked, was in a loop from the lowest order part of the number to the highest order, simply adding each word at a time. If the sum of 2 words was greater than FFFFh, a 1 was carried to the next addition.
    : :
    :
    : Basically, that's what you need to do. You need to use arbitrary/extended precision calculation. As the Art of Assembly (webster.ucr.edu) already has a good section on extended precision arithmetic at the assembly level, I'll simply refer you to that. On a side note, I'd recommend the iterative version of the fibonacci sequence is very straightforward and it isn't exponential in complexity (it's linear). There actually is an even better method that's only logarithmic in time complexity, but it isn't as straightforward (and while it isn't that complex, you don't really need it here). Outputting in hexadecimal isn't hard at all from that, outputting decimal is more difficult because the first digit potentially depends on the last digit (whereas hexadecimally no digit depends on any other digit). This is an artifact of using "digits" that are base an integer power of 16 (you'll likely be using base 2^32 or 2^16 "digits" which are an integer power of 16 (2^32=16^8 2^16=16^4).)
    :
    : As a note to Josh Code, if you implement the code the way you describe it then you can easily make it as simple to output in decimal as it is to output in hexadecimal now simply use "digits" that are based on an integer power of 10, i.e. "carry" if x is less than 10,000 (or any other power of ten you feel like). Then printing out each "digit" separately in decimal will be the same as printing the whole number in decimal.
    :
    : "We can't do nothing and think someone else will make it right."
    : -Kyoto Now, Bad Religion
    :
    :

  • Chris BrownChris Brown USAMember Posts: 4,624 ✭✭

    _________ [ http://forcoder.org ] free video tutorials and ebooks about < Delphi Scratch Assembly JavaScript Java C C# Perl PHP Objective-C MATLAB Python Visual Basic .NET Visual Basic Ruby R C++ Go PL/SQL Swift Crystal Lisp Bash Prolog Kotlin ABAP Fortran COBOL ML F# Scheme Julia Transact-SQL FoxPro VBScript Lua Clojure SAS Awk Alice D Dart LabVIEW Ada Hack Erlang Rust Scala Logo Apex /> _____________

Sign In or Register to comment.