10 Replies - 11824 Views - Last Post: 06 February 2017 - 12:54 PM

#1 rasil9kudu   User is offline

  • New D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 19-December 15

program to find nth term of fibnoacci sequence

Posted 20 December 2015 - 10:52 PM

Description:it is a simple program that outputs nth term of the fibnoacci sequence,it is my first program there is an equation to find nth term an =(an-2)+(an-1) where n >2
#include <iostream>
#include <cmath>

double fib(int n) {
    const double phi = (1.0 + sqrt(5.0)) / 2.0;
    const double psi = -1.0/phi;
    return (pow(phi, n) - pow(psi, n)) / sqrt(5.0); 
}

int main()  {
    for (int i = 1; i < 20; i++) {
        std::cout << fib(i) << std::endl;
    }
}


Is This A Good Question/Topic? 0
  • +

Replies To: program to find nth term of fibnoacci sequence

#2 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7361
  • View blog
  • Posts: 15,285
  • Joined: 16-October 07

Re: program to find nth term of fibnoacci sequence

Posted 21 December 2015 - 07:17 AM

Interesting. Note, starting at fib(72) this fails. Also, the return type shouldn't really be float.
Was This Post Helpful? 0
  • +
  • -

#3 rasil9kudu   User is offline

  • New D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 19-December 15

Re: program to find nth term of fibnoacci sequence

Posted 21 December 2015 - 07:47 AM

View Postbaavgai, on 21 December 2015 - 07:17 AM, said:

Interesting. Note, starting at fib(72) this fails. Also, the return type shouldn't really be float.

sorry ,i am a newbie why shouldnt that be float,and thanks for pointing that
Was This Post Helpful? 0
  • +
  • -

#4 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7361
  • View blog
  • Posts: 15,285
  • Joined: 16-October 07

Re: program to find nth term of fibnoacci sequence

Posted 21 December 2015 - 08:33 AM

Well, it's not programmatically wrong; it's your program, you can do as you will. Rather, it's a definition.

A Fibonacci number is an integer.

This post has been edited by baavgai: 21 December 2015 - 08:33 AM

Was This Post Helpful? 1
  • +
  • -

#5 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7361
  • View blog
  • Posts: 15,285
  • Joined: 16-October 07

Re: program to find nth term of fibnoacci sequence

Posted 21 December 2015 - 08:49 AM

If you're curious, I actually checked this with a Python program:
from math import sqrt

def fibFunc(n):
    sr5 = sqrt(5.0)
    phi = (1.0 + sr5) / 2.0
    psi = -1.0 / phi
    return (pow(phi, n) - pow(psi, n)) / sr5

def fib(n):
    if not hasattr(fib, "memo"):
        fib.memo = [0,1,1]
    while len(fib.memo)<=n:
        fib.memo.append(fib.memo[-1] + fib.memo[-2])
    return fib.memo[n]

for n in range(60,75):
    x, y = fibFunc(n), fib(n)
    print(n, int(x)==y, y, x)



Results:
60 True 1548008755920 1548008755920.003
61 True 2504730781961 2504730781961.005
62 True 4052739537881 4052739537881.0083
63 True 6557470319842 6557470319842.014
64 True 10610209857723 10610209857723.021
65 True 17167680177565 17167680177565.037
66 True 27777890035288 27777890035288.062
67 True 44945570212853 44945570212853.09
68 True 72723460248141 72723460248141.17
69 True 117669030460994 117669030460994.28
70 True 190392490709135 190392490709135.44
71 True 308061521170129 308061521170129.7
72 False 498454011879264 498454011879265.2
73 False 806515533049393 806515533049395.0
74 False 1304969544928657 1304969544928660.0



Hmm... in C++...
#include <iostream>
#include <cmath>
#include <vector>

double fibFunc(int n) {
	const double phi = (1.0 + sqrt(5.0)) / 2.0;
	const double psi = -1.0 / phi;
	return (pow(phi, n) - pow(psi, n)) / sqrt(5.0);
}

unsigned long long fib(unsigned n) {
	static std::vector<unsigned long long> *memo(NULL);
	if (!memo) {
		memo = new std::vector<unsigned long long>(); memo->push_back(0); memo->push_back(1); memo->push_back(1);
	}
	while (memo->size() <= n) { memo->push_back(*(memo->rbegin()) + *(++memo->rbegin())); }
	return memo->at(n);
}

int main() {
	std::cout.precision(17);
	for (int i = 50; i < 75; i++) {
		double x = fibFunc(i);
		unsigned long long y = fib(i);
		std::cout << i
			<< ' ' << (((unsigned long long)(round(x))==y)?"True":"False")
			<< ' ' << y << ' ' << x << std::endl;
	}
}



Results:
50 True 12586269025 12586269024.999998
51 True 20365011074 20365011074
52 True 32951280099 32951280098.999992
53 True 53316291173 53316291172.999985
54 True 86267571272 86267571271.999985
55 True 139583862445 139583862444.99997
56 True 225851433717 225851433716.99997
57 True 365435296162 365435296161.99994
58 True 591286729879 591286729878.99988
59 True 956722026041 956722026040.99988
60 True 1548008755920 1548008755919.9998
61 True 2504730781961 2504730781960.9995
62 True 4052739537881 4052739537880.999
63 True 6557470319842 6557470319841.999
64 True 10610209857723 10610209857722.998
65 True 17167680177565 17167680177564.996
66 True 27777890035288 27777890035287.996
67 True 44945570212853 44945570212852.992
68 True 72723460248141 72723460248140.984
69 True 117669030460994 117669030460993.98
70 True 190392490709135 190392490709134.97
71 True 308061521170129 308061521170129
72 True 498454011879264 498454011879263.88
73 True 806515533049393 806515533049392.88
74 True 1304969544928657 1304969544928656.8



Well, that's interesting. Looks like my C++ floating point is significantly better than my python one!

Right, moving forward with the C++:
74 True 1304969544928657 1304969544928656.8
75 True 2111485077978050 2111485077978049.5
76 False 3416454622906707 3416454622906706
77 False 5527939700884757 5527939700884755



Ok, looks like good to 75 on this one. Of course, at some point, in C++, your precision will fail and you'll roll back over. Note how I ended up resorting the the ugly "unsigned long long" instead of int.
Was This Post Helpful? 0
  • +
  • -

#6 rasil9kudu   User is offline

  • New D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 41
  • Joined: 19-December 15

Re: program to find nth term of fibnoacci sequence

Posted 22 December 2015 - 05:26 AM

Thanks for the tip :-)
Was This Post Helpful? 0
  • +
  • -

#7 mjmpe   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 08-April 16

Re: program to find nth term of fibnoacci sequence

Posted 09 April 2016 - 06:37 PM

Floating point rounding errors will always occur at some point. I recommend using this method for nth term:

#include<iostream>

int main()
{
    unsigned long long currentVal = 0;
    unsigned long long lastCurrentVal = 0;
    unsigned long long oldCurrentVal = 1;
    unsigned long long n;

    std::cout<<"Enter a number to find its term in the Fibonacci sequence: ";
    std::cin>>n;

    for(unsigned long long j = 0;j < n;++j)
        {
            currentVal = lastCurrentVal + oldCurrentVal;
            oldCurrentVal = lastCurrentVal;
            lastCurrentVal = currentVal;
        }

    std::cout<<"\n\n"<<currentVal;

    std::cin.get();
    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#8 mjmpe   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 08-April 16

Re: program to find nth term of fibnoacci sequence

Posted 09 April 2016 - 07:14 PM

That works up to n=93 with 100% accuracy.
Was This Post Helpful? 0
  • +
  • -

#9 mjmpe   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 08-April 16

Re: program to find nth term of fibnoacci sequence

Posted 10 April 2016 - 02:15 PM

Here's a version with type checking. It works perfectly and warns you if you enter a string rather than an integer, a zero, or a negative:

#include<iostream>

int main()
{
    unsigned long long currentVal = 0;
    unsigned long long lastCurrentVal = 0;
    unsigned long long oldCurrentVal = 1;
    int n;
    std::string input;
    bool inputNotValid = true;
    bool errorFound = false;
    bool zeroDetected = false;
    bool tooLarge = false;
    bool miscIssue = false;
    int len;
    int couldBeLarge;

while(1)
{
    currentVal = 0;
    lastCurrentVal = 0;
    oldCurrentVal = 1;

    while(inputNotValid == true)
    {
        inputNotValid = false;

        if(errorFound == false)
        std::cout<<"\nEnter a number to find that term in the Fibbonacchi Sequence: ";
        else if(miscIssue == true)
        std::cout<<"\nValid positive intergers only please.  Try again: ";
        else if(zeroDetected == true)
        std::cout<<"\nNon zero numbers only please.  Try again: ";
        else if(tooLarge == true)
        std::cout<<"\nNumbers must be smaller than 94.  Try again: ";


        std::cin>>input;

        errorFound = false;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = false;

        for (char abc: input)
        if(abc != '0' && abc != '1' && abc != '2' && abc != '3' && abc != '4' && abc != '5' && abc != '6' && abc != '7' && abc != '8' && abc != '9' && abc != '\n' && abc != '\r')
        {
        inputNotValid = true;
        errorFound = true;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = true;
        }

        if(input == "0")
        {
        inputNotValid = true;
        zeroDetected = true;
        errorFound = true;
        tooLarge = false;
        miscIssue = false;
        }

        if(miscIssue == false)
        {
            len = input.length();
            couldBeLarge = std::stoi(input);

            if(len > 3 || couldBeLarge > 93)
            {
                inputNotValid = true;
                zeroDetected = false;
                errorFound = true;
                tooLarge = true;
                miscIssue = false;
            }
        }
    }

    n = std::stoi(input);

    for(int j = 0;j < n;++j)
        {
            currentVal = lastCurrentVal + oldCurrentVal;
            oldCurrentVal = lastCurrentVal;
            lastCurrentVal = currentVal;
        }
        std::cout<<currentVal;
        std::cout<<"\n";

        inputNotValid = true;
        errorFound = false;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = false;
}
    return 0;
}



Also warns if number is > 93.
Was This Post Helpful? 0
  • +
  • -

#10 mjmpe   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 08-April 16

Re: program to find nth term of fibnoacci sequence

Posted 10 April 2016 - 02:59 PM

That version had a bug. Here's the new code:
#include<iostream>

int main()
{
    unsigned long long currentVal = 0;
    unsigned long long lastCurrentVal = 0;
    unsigned long long oldCurrentVal = 1;
    int n;
    std::string input;
    bool inputNotValid = true;
    bool errorFound = false;
    bool zeroDetected = false;
    bool tooLarge = false;
    bool miscIssue = false;
    int len;
    unsigned long long couldBeLarge = 0;

while(1)
{
    currentVal = 0;
    lastCurrentVal = 0;
    oldCurrentVal = 1;

    while(inputNotValid == true)
    {
        inputNotValid = false;

        if(errorFound == false)
        std::cout<<"\nEnter a number to find that term in the Fibonacci Sequence: ";
        else if(miscIssue == true)
        std::cout<<"\nValid positive integers only please.  Try again: ";
        else if(zeroDetected == true)
        std::cout<<"\nNon zero numbers only please.  Try again: ";
        else if(tooLarge == true)
        std::cout<<"\nNumbers must be smaller than 94.  Try again: ";


        std::cin>>input;

        errorFound = false;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = false;

        for (char abc: input)
        if(abc != '0' && abc != '1' && abc != '2' && abc != '3' && abc != '4' && abc != '5' && abc != '6' && abc != '7' && abc != '8' && abc != '9' && abc != '\n' && abc != '\r')
        {
        inputNotValid = true;
        errorFound = true;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = true;
        }

        if(input[0] == '0')
        {
                    if(input == "0")
                    {
                        inputNotValid = true;
                        zeroDetected = true;
                        errorFound = true;
                        tooLarge = false;
                        miscIssue = false;
                    }
                    else
                    {
                        inputNotValid = true;
                        errorFound = true;
                        zeroDetected = false;
                        tooLarge = false;
                        miscIssue = true;
                    }
        }

        len = input.length();
        if(len == 2 && miscIssue != true)
        couldBeLarge = std::stoi(input);

        if(miscIssue == false)
        {

            if(len > 2 || couldBeLarge > 93)
            {
                inputNotValid = true;
                zeroDetected = false;
                errorFound = true;
                tooLarge = true;
                miscIssue = false;
            }
        }
    }

    n = std::stoi(input);

    for(int j = 0;j < n;++j)
        {
            currentVal = lastCurrentVal + oldCurrentVal;
            oldCurrentVal = lastCurrentVal;
            lastCurrentVal = currentVal;
        }
        std::cout<<currentVal;
        std::cout<<"\n";

        inputNotValid = true;
        errorFound = false;
        zeroDetected = false;
        tooLarge = false;
        miscIssue = false;
}
    return 0;
}



That last version, I mean.
Was This Post Helpful? 0
  • +
  • -

#11 hexagod   User is offline

  • D.I.C Regular

Reputation: 11
  • View blog
  • Posts: 403
  • Joined: 29-October 16

Re: program to find nth term of fibnoacci sequence

Posted 06 February 2017 - 12:54 PM

I like it!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1