fibonacci

[olams]

hi,
thank you for replying. i started a new thread because nobody took a look at the old one. i finally figured out a way to add two arrays and using eArray.
i also wrote the fibonacci code. However, when i debug and print the fibonacci number, i get some numbers like this:

8
10
7
5 5 5 5
4 3 2 1
10 20 30 40
1 7 8 2 4
7 1 2 9 6
8
10 20 30 40 0 0 0 0
10 20
Input n:5
-6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6
-6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -
6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6 -6
-6 -6 -6 -6 -6 -6 -6 -6 -6 -5 -9 -1 -8 0 -8 -8 -4 -8 -8 8
After a is copied to v, v becomes 9 3 4 5 6

After a is added to v, v becomes 8 6 9 1 2

>>it prints the 5th fibonacci number at the end of the gabbage.
when i try to print the 10th fibonacci number which is 89, i get 9 at the end of the gabbage.
Help me please. The eArray class is still the same with some more functions added:

#include <iostream>
using namespace std;
void compLfact(int);
void compLfib(int);

//class Definition
class eArray{
public:
	//Constructors
	eArray();
	eArray(int);//constructor cos the name of the class is d same
	//as that of the constructor. they also don't need return types.
	//the two constructors are overloaded cos the have the same name.
	//accessor function to find the state of the object
	int getSize();
	//Set the elements to some value
	void set(int);//check notes
	void set(int, int);//check notes
	//Get the value of an element
	int get(int);
	//Print functions
	void dump();//print everything
	void dumpR();
	void vMpyC(int);//vector multiply by an integer constant
	void aMpyC(int);//arithmetic multiply by an integer
	void expandBy(int);
	void trimTo(int);
	void copyTo(eArray);
	void addTo(eArray);
	
private://only the class designer can access the class
	int size; //current size of the array
	int* data;//pointer to the array
	void init(int);
};

//class Implementation
eArray::eArray(){
	init(4); //default size = 4 elements
}
eArray::eArray(int s){
	init(s);//whatever value u want
}
void eArray::init(int n){
	size = n;
	data = new int[n];//dynamically declared array
	//size of the array can change; non-static
}
void eArray::set(int v){
	for(int i=0; i<size; i++)
		data[i]=v;
}
void eArray::set(int index, int val){
	if (index < 0 || index >= size){
		cout<<"Error******"<<endl;
		cout<<"Invalid index --- Operation aborted"<<endl;
	}
	else data[index] = val;	
}
int eArray::getSize(){
	return size;//tells the no. of active elements there are.
}
int eArray::get(int index){
	if (index < 0 || index >= size){
		cout<<"Error******"<<endl;
		cout<<"Invalid index --- Operation aborted"<<endl;
		return -1;//if the index is wrong
	}
	else return data[index];
}
void eArray::dump(){
	int i;
	for(i=0; i<size; i++){
		if ((data[i] !=0))
break;
	}
		while (i<size)
			cout<<data[i++]<<" ";
			cout<<endl;
	}


void eArray::dumpR(){
	for(int i=size-1; i>=0; i--)
		cout<<data[i]<<" ";
	cout<<endl;
}
void eArray::vMpyC(int c){
	for(int i = 0; i < size; i++)
		data[i] *=c;//multiply each component of the array by constant c
}
void eArray::aMpyC(int c){
int i,carry,temp;
	for(i=size-1,carry=0; i > -1; i--){
		temp=data[i]*c + carry;
		data[i]= temp%10;
		carry=temp/10;

	}
}


//This member function expands the size of the array by adding 
//n more elements to it.
void eArray::expandBy(int n){
int news=size+n;//news means new size
int *temp = new int[news];//create a temp array
int i;
//copy the old data into temp
	for(i=0; i<size; i++)
		temp[i]=data[i];
	//set the newly added elements to zero
	for(i=size; i<news; i++)
		temp[i]=0;
	// we don't need the old data anymore 
	//so we delete them
	delete []data;
	data=temp; //point data to temp
	size=news;//update the size
}
//This function trims the vector by removing all but first
//n components
void eArray::trimTo(int n){
int *temp, i;
	if(n > size){
		cout<<"Error in size spec****"<<endl;
		cout<<"Operation is aborted"<<endl;
	}
	else {
		temp = new int[n];
		//copy the first n numbers into temp
		for (i=0; i<n; i++)
			temp[i]=data[i];
		//Now the old data isn't needed
		delete []data;
		//make data points to the temp
		data=temp;
		size=n;//update size
	}
}

void eArray::copyTo(eArray t){
	int i;
for(i=0; i<size; i++)
	t.data[i] = data[i];
}

void eArray::addTo(eArray t){
	int i, temp, carry;
	for(i=size-1,carry=0; i > -1; i--){
		temp=data[i] + t.get(i) + carry;
		data[i]= temp%10;
		carry=temp/10;
	}
}

	

void main(){
	eArray x(8);
	x.set(10);
	cout<<x.getSize()<<endl;
	cout<<x.get(4)<<endl;//4th element is 10
	x.set(4,7);
	cout<<x.get(4)<<endl;
eArray y;
y.set(5);
y.dump();
int i;
	for(i=1; i<5; i++)
		y.set(i-1, i);
	y.dumpR();
	y.vMpyC(10);
	y.dump();
eArray z(5);
	z.set(0, 1);
	z.set(1, 7);
	z.set(2, 8);
	z.set(3, 2);
	z.set(4, 4);
	z.dump();
	z.aMpyC(4);
	z.dump();
	y.expandBy(4);//increase the size of the vector y by
	//4 more components. size is 4, after expansion,
	//size will be 8.
	cout<<y.getSize()<<endl;
	y.dump();
	y.trimTo(2);//to keep 2 numbers instead of 8 numbers
	y.dump();
	int n;
	cout<<"Input n:"; cin>>n;
	//compLfact(n);
	compLfib(n);
	eArray a(5);
	eArray v(5);
	a.set(0, 9);
	a.set(1, 3);
	a.set(2, 4);
	a.set(3, 5);
	a.set(4, 6);
	cout<<"After a is copied to v, v becomes"<<" ";
	a.copyTo(v);
	a.dump();
	cout<<endl;
	cout<<"After a is added to v, v becomes"<<" ";
	a.addTo(v);
	a.dump();
	cout<<endl;
	
}
void compLfact(int n){
	eArray d(20);//create an expandable array of 20 numbers.
	int i;
		d.set(0);//set all the numbers to zero.
		d.set(19,1);//factorial of zero is one.
		for(i=2; i<=n; i++)
			d.aMpyC(i);
		cout<<"The answer is"<<" ";
			d.dump();
		cout<<endl;
}
void compLfib(int n){
	int i;
	eArray a(100); 
	eArray b(100);
	eArray c(100);
	a.set(99, 1);
	b.set(99, 1);
	c.set(99, 1);
	for(i=2; i<=n; i++){
		c.addTo(a);
		a.set(0);
		b.copyTo(a);
		b.set(0);
		c.copyTo(b);
	}
	c.dump();
}

Thanks in advance for your help.

[VernonDozier]

They're probably all posting over in Dream In Code where you have it posted too.

[Duoas]

Well, I've just glanced over your code, so I'll run through the most obvious errors first, and give some useful suggestions, and see if that doesn't help.

1. main returns int.

2. You have not very well documented your code. In fact, it took me until I was reading through the aMpyC() and addTo() functions that I finally 'got it' that eArray is a bignum.

Also, your variable names need some work. I will not address that below, but poorly named variables are an indication of a nebulous understanding of what they do. This is what you are struggling with mostly at the moment-- making the structure match what you think it ought to be doing.

So, with that in mind, lets fix the very first part with some proper documentation.

// eArray
//
// The eArray class represents an unsigned
// integer of arbitrary precision. You can
// set it to a number, add a number to it,
// multiply it by a number, and print its value.
//
class eArray {
  ...
  };

3. You are forcibly using too much memory. Each element of data[] should represent only one digit of the number. (Yes it is possible to use all the bits in each element, but it is tricky and you are trying to do it the simple way anyway, so we'll stick with that.)

Also, you will likely save yourself some space if you use bytes instead of machine words to store your array.

Lets fix the definition and document it:

private:
    int size;
    // The number of digits in the number,
    // which is the same as the number of
    // elements in data[].
    //
    // The size is never less than one (so
    // data is never NULL).

    unsigned char* data;
    // The array of digits in the number.
    // Each element may have a value in
    // the range 0..9 only.

Notice how I explicitly added a condition on the length of the data[].

Oh yeah, and you'll have a much easier time if you store the number backwards. This is not particularly obvious until you've done this kind of thing two or more times...

// The digits are stored least-significant
    // digit first to most-significant digit last.

What this means is that if you store the number 1234, it will be listed in data as {4,3,2,1}.

Already, this imposes some concrete conditions on your code. As a result, it invalidates some of your code and requires some review of other parts.

4. The first thing to which I will direct your attention is setting and changing the size of the digits array (data[]). You have three procedures (init, expandBy, and trimTo) that change the size of the array. I think you could combine all of them into a single procedure that sets the size of the array, copying data as necessary. You might name it something like: void setSize( unsigned newSize ); Inside, you'd have to check to see if data[] were NULL, and if not, copy the elements you can into the new array.

5. Next, I would reconsider the visibility of certain things. For example, getting and setting a single digit does not belong to be publicly visible. Nor do functions that set the size of the array.

Along with this is the idea that, anywhere outside the class (such as in the fibonacci and factorial functions, and main) the eArray class should appear as much like a normal number as possible. That is to say, there is no reason for any non-eArray member function to be able to set the size of the array or manipulate individual digits directly.

What would be ideal is to be able to set the value that the array represents. Something like x.setValue( 123 ); (as a member function)
or x = 123; (as an operator overload).
Thereafter, x.data would have the value {3, 2, 1}.

You might want to rethink your constructors as:

eArray(): data( NULL ) { setSize( 1 ); }
  // The default constructor.
  // It creates a new number and initializes
  // its value to zero.

  eArray( int value ): data( NULL ) { setValue( value ); }
  // This constructor creates an eArray
  // (bignum) version of the int number.

Notice that, in both cases, the user of your class (which just happens to be you, but might not be...) doesn't need to care or think about how big the array actually is. He only needs to think of the numeric value the array represents.

6. Enforce rules, but be careful. The set() functions should guarantee that no element of data[] is larger than 9 or less than 0. Considerations:

• What if index is too large? Do you automatically setSize(index+1); or do you complain? If you complain, how do you do it (exception? return value? print error and continue?)
• Likewise, what if val is outside the range 0..9?

You can build in some easy guarantees by using the right data types. void set( unsigned index, unsigned val ) You might also find very useful a little function, very similar to set, that looks like this:

unsigned eArray::add( unsigned index, unsigned val ) {
  //
  // Add a value to a specific digit.
  // Return the carry value.
  //
  if (index >= size) setSize( index+1 );
  unsigned v = data[ index ] + val;
  data[ index ] = v % 10;
  return v / 10;
  }

7. The part to be careful about is the get() function. If my number is 1234 and I ask for digit 0 I rightly get 4. But if I ask for digit 12 what do I get? I should get zero. (This is where you are getting all those negative numbers from.)

7. The function vMpyC() does not fit into the ideology of the eArray class. You can't do that with normal number types, and eArray is not a vector...

The function aMpyC() has a potential bug. What if there is a carry past the end? (You cannot safely count on the most-significant digits being zero.) If there is a non-zero carry, you'll want to resize the array one digit larger and set the new digit to have the carry value.

8. Hmm... well, I've worked on this post long enough. I hope this helps some. You seem to have a pretty good handle on the math and organizing your algorithm, so I think you should be able to make things work after this.

Good luck.

[olams]

thank you very much, i really appreciate it.