answersLogoWhite

0

The problem with generating Fibonacci numbers is that they get large very fast. They will eventually exceed the range of even 64 bit integers. In C++, one way to solve this issue is to write a dynamic, arbitrary decimal class.

You could create a linked list, where each element represents a digit. The first element is the units digit, the second the tens digit, the third the hundreds digit, and so forth.

Imbed this linked list into a decimal number class, and provide operators to do various math operations such as addition between two instances of the class. When implementing operator+, for instance, iterate through the elements of both classes, adding them, and applying the carries in each step. If need be, invoke the AddDigit method of the linked list to make the r-value larger by one digit.

With this class, implementing construct, destruct, copy, assign, add, and print, you can generate a Fibonacci sequence using the algorithm of keeping three numbers, and iterating each sequence by adding the prior two numbers and then moving numbers around. (More efficient would be to rotate pointers to the three instances, rather than copying them.) As the instances get reused, it would also be helpful if you did not just delete elements, but, rather, allowed for them to be reused by keeping track of how many are in use versus how many are allocated. (Or you could just zero the excees digits. That is your choice, and it is part of your overall design. Keep in mind that you do know how long the list is, by knowing which element is the last element.)

As you develop this class, you will find more uses that involve other operations, such as multiply and divide. You can extend the class as necessary.

The following example demonstrates a very basic implementation that will generate Fibonacci numbers up to a given length (200 digits in the example, but you could easily generate arbitrary length from user input). The program can also be easily adapted to produce the nth Fibonacci. The implementation of the bignum class could be improved enormously by embedding a pointer to std::vector and implementing a move constructor (like a copy constructor, but ownership of the resources is swapped rather than shared). Also, storing one character per element is highly inefficient, it would be far better to store multiple digits in 64-bit elements. However I've kept the class as simple as possible for the purpose of clarity.

#include

#include

class bignum

{

friend std::ostream& operator<<(std::ostream& os, const bignum& n);

public:

bignum(unsigned int n=0);

bignum operator+(const bignum& );

size_t size()const{return(list.size());}

private:

std::list list;

};

bignum::bignum(unsigned int n)

{

if( n )do

{

unsigned char digit=n%10;

list.push_front( digit );

} while( n/=10 );

}

bignum bignum::operator+(const bignum& n)

{

bignum result;

unsigned char carry=0, digit=0;

std::list::const_reverse_iterator first = list.rbegin();

std::list::const_reverse_iterator second = n.list.rbegin();

while( first!=list.rend() second!=n.list.rend() carry )

{

digit=carry;

if( first!=list.rend() ) digit+=*first++;

if( second!=n.list.rend() ) digit+=*second++;

carry=digit/10;

digit%=10;

if( digit first!=list.rend() second!=n.list.rend() carry )

result.list.push_front( digit );

}

return( result );

}

std::ostream& operator<<(std::ostream& os, const bignum& n)

{

if( !n.list.size() )

os<<'0';

else for( std::list::const_iterator it=n.list.begin(); it!=n.list.end(); ++it )

os<<(unsigned int)*it;

return( os );

}

int main()

{

bignum* num1 = new bignum(0); std::cout<<*num1<

bignum* num2 = new bignum(1); std::cout<<*num2<

// generate the Fibonacci sequence up to a length of 200 digits

while(num2->size()<200)

{

bignum* num3 = new bignum( *num1+*num2 );

delete(num1);

num1 = num2;

num2 = num3; std::cout<<*num2<

}

delete( num2 ); num2 = NULL;

delete( num1 ); num1 = NULL;

std::cout<

}

User Avatar

Wiki User

11y ago

What else can I help you with?

Related Questions

A program c plus plus on automorphic numbers or not?

how to write a program that counts automorphic number from 1 to 999


How do you write a C plus plus program that will display the first 10 positive prime numbers?

By learning how to program on C+.


Write a program in c plus plus to implement macro processor?

Don't write, it is already written, google for 'cpp'.


How do you write program to convert meter to kilometer in c plus plus?

Divide it by 1000.


Do I need to write a program to find a substring in a given string in c plus plus?

No.


C plus plus program to print number patterns?

bghjg


How do you write an Algorithm for a C plus plus Program?

You don't write an algorithm for a C++ program, unless you are documenting the C++ program after-the-fact. The normal procedure is to write the algorithm first, in a language independent fashion, and then translate that stated algorithm into C++ code, or into whatever language you wish.


Write a program in c plus plus to compute first of non-terminal?

there is no solution of this problem...........that's it..........


How many classes can we write in a single c plus plus program?

Its limited only by available memory.


Would you Write c plus plus program using array for Fibonacci number?

You can write a C++ fib pro using arrays but the problem is the prog becomes very complicated since u need to pass the next adding value in an array.....


How do you write a C plus plus program that displays a pyramid of Xes on the screen using a for loop?

printf ("x")


Write a program in C programming language that computes the roots of the quadratic equation ax2 plus bx plus c?

Write your program and if you are having a problem post it here with a description of the problem you are having. What you are asking is for someone to do your homework for you.