Fibronacci Numbers

[dsmo223]

I am writing a program to calculate Fibonacci numbers, it has to work by adding the previous binary numbers up to n to get Fibonacci(n), my program is working, but only for Fib(0) -> Fib(45) and this is using Fib(0)=1, fib(1)=1, fib(n)=fib(n-1)+fib(n-2). I am storing the binary numbers in vector<int>, and computeing from there, can anyone think of something that is causing it to create uncorrect numbers past 45?

[Return 0]

Well, what is the 45 sequence supposed to be equal to?

[Albatross]

I think you could be exceeding the bounds of a normal 32-bit integer.

F₄₈ = 4,807,526,97
std::numeric_limits<int>::max() = 4,294,967,296

However, everything up to 48 should work just fine.

-Albatross

[m4ster r0shi]

dsmo223 wrote:

can anyone think of something that is causing it to create uncorrect numbers past 45?

As Albatross noticed, the problem is overflow.
The int data type isn't big enough to hold such values.

This could help -> http://cplusplus.com/forum/lounge/32041/

[dsmo223]

This is a more compleate discription of the problem that I am having, I didn't have much time when I first posted;

I have to do the computation in binary, so I first take in the number from the user of the index of the fibonacii number that they want to compute, I then take that and convert it to binary, create 3 vectors, fib1, fib2, and fib, initialize fib 1 and 2 to 1, then loop from 0 to the users number { add fib 1 and 2, which are binary numbers to create the next number in the sequence, then store Fib 1 in Fib 2 and the number just calculated in Fib1, } Fib1 when that loop is done will be the answer to the problem in binary, now I have to convert that into decimal, I do this by the following code



This Code is my binary class that has all of the methods needed to do on binary numbers, and adding vectors of ints.

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#include "binary.h"

vector<int> binary::dectobin(int dec){ //decimal to binary converter
	vector<int> bin;
	while(dec!=0){
		bin.push_back(dec%2);
		dec=dec/2;
	}
	return bin;
}

vector<int> binary::bintodec(vector<int> bin){ //converts from binary to decimal
	vector<int> decimal;
	decimal.push_back(0);
	vector<int> decimal2;
	int temp;
	vector<int> addnumber;
	addnumber.clear();
	for(int i=(bin.size()-1); i>=0; --i){
		temp=bin[i]*pow(2,i);
		addnumber=(convertIntToVector(temp));
		decimal2=addints(decimal, addnumber);
		decimal.clear();
		decimal=decimal2;
		decimal2.clear();
		addnumber.clear();
	}
	return decimal;
}



/****************THIS IS WHY I THINK IT SHOULDN'T BE GOING OVER***************/

vector<int> binary::addints(vector<int> A,vector<int> B){ //adds to vector<int>s by componet to keep from going over
	vector<int> sumation;				//holds the binary answer
	vector<int>::iterator it;
	sumation.clear();
	int maxsize;						
		if(A.size()>B.size()){
			maxsize=A.size();
			for(int i=B.size(); i<A.size(); ++i){
				B.push_back(0);
			}
		}
		else
			maxsize=B.size();
		for(int i=A.size(); i<B.size(); ++i){
			A.push_back(0);
		}
	int carry=0;						//holds the carry bit
	for(int i=0; i<=maxsize-1; ++i){
		int sum = A[i]+B[i]+carry;
		sumation.push_back(sum%10);
		carry=(sum/10);		
	}
	sumation.push_back(carry);
	return sumation;
  }

vector<int> binary::add(vector<int> A,vector<int> B){        //adds 2 vector<int> binary numbers
	vector<int> sumation;				//holds the binary answer
	vector<int>::iterator it;
	sumation.clear();
	int maxsize;						
		if(A.size()>B.size()){
			maxsize=A.size();
			for(int i=B.size(); i<A.size(); ++i){
				B.push_back(0);
			}
		}
		else
			maxsize=B.size();
		for(int i=A.size(); i<B.size(); ++i){
			A.push_back(0);
		}
	int carry=0;						//holds the carry bit
	for(int i=0; i<=maxsize-1; ++i){
		int sum = A[i]+B[i]+carry;
		sumation.push_back(sum%2);
		carry=(sum/2);	
	}
	sumation.push_back(carry);
	return sumation;
  }

vector<int> binary::convertIntToVector(int A){
	vector<int> integer;
	integer.clear();
	while(A>=1){
		integer.push_back(A%10);
		A=A/10;
	}
	return integer;
	}

[dsmo223]

when I run the program with any number under 45, I get the correct number, but if I run 46, I get 823731425
when the correct number is 2971215073, also please remember that this has Fib(0) = 1 not 0.

Thank you for any help

[ne555]

My guess

vector<int> binary::bintodec(vector<int> bin){ //converts from binary to decimal
//...
	for(int i=(bin.size()-1); i>=0; --i){
		temp=bin[i]*pow(2,i); //overflow  

Avoid the intermediaries.

[dsmo223]

ne555,

I don't understand what you mean, can you please explain? I am fairly new to c++.

Thank you,
dsmo223

[ne555]

std::numeric_limits<int>::max()==2147483647 in my system. That is about 2³¹-1.
Now, suppose that bin has a really big number, so its size is greater than 31 (like 33)

//for(int i=(bin.size()-1); i>=0; --i){
//	temp=bin[i]*pow(2,i); 
//in the first iteration
temp = 1*pow(2,33) ; //about 8589934592 

That doesn't fit in. It causes overflow and now temp has an useless value.

So you need another way of converting.

[Browni3141]

How about the uint64_t data type? It can store numbers up to 2⁶⁴-1

[ne555]

Then you will be having troubles with the 97th Fibonacci (just a guess).
You need to change the conversion from base 2 to base 10. Check that bignum link for something better than

void bin_to_dec(bignum bin, vector<int> &n){
	if(bin){
		bin_to_dec(bin/10, n);
		n.push_back( (bin%10).to_long() );
	}
}