Big Number Class

having problem with +

Page 1 of 1

4 Replies - 8744 Views - Last Post: 08 June 2007 - 01:10 AM Rate Topic: -----

#1 realNoName  Icon User is offline

  • D.I.C Regular

Reputation: 7
  • View blog
  • Posts: 343
  • Joined: 04-December 06

Big Number Class

Posted 07 May 2007 - 10:56 AM

i have to make a class that will hold large numbers (all are going to be 0 or larger) and i got it all to work but the + operator


it has to use this linked list (i have the digits stored in reversed order so the number 123 is stored in the list 321... any ways i have been playing with this for some time now and dont really know where to go (i know the way i have it setup now it will only work if they are the same length but i will fix that later)
struct node
{
   int digit;
   node * next;
};


bigNumber bigNumber::operator +  (const bigNumber & right) const
{
	int temp,i,size;
	bool add = false;
	node * rWalker = right.root,
		 * walker = root;
	char * answer;

	if(this->length > right.length)
	{
		answer = new char[this->length];
		size = this->length +2;
	}
	else
	{
		answer = new char[right.length];
		size = right.length +2;
	}
	
	for(i=0; i<=size-1; i++)
	{
		if(walker != NULL && rWalker != NULL)
		{
			temp = walker->digit + rWalker->digit;
			if(add && walker->next != NULL)
			{
				temp++;
				add = false;
			}
			answer[i] = (temp/10?temp%10:temp) + 48;
			add = (temp/10?true:false);

			walker = walker->next;
			rWalker = rWalker->next;
		}
	}
	if(add)
	{
		answer[size+1] == '1';
		answer[size+2] == '\0';
	}
	else
		answer[size] = '\0';
	
	return bigNumber(answer);
}


Is This A Good Question/Topic? 0
  • +

Replies To: Big Number Class

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Big Number Class

Posted 07 May 2007 - 12:37 PM

well just a note first. I had just put this in my tutorial on conditionals (not posted yet). There is no need to use the conditional to convert something to a boolean. As this is a little redundant.
add = (temp/10?true:false); the condition temp/10 is already a boolean expression. To make sure it gives you a true boolean (1 for true 0 for false) you can make this: add = (temp/10) && true; but unless you really need that extra insureance add = (temp/10); will be 0 if it is false and non-zero if it is true, and that is all C++ cares about.

Question: Why store the digits in reverse order? It would seem to me that having the LSD at the base of the list would make much more sence. It would simplify the logic because the power of the digit could be determined as its length away from the base node. It would also be more natural to the classic algorithms. -- I was wondering if you had a spacific reason.

OH I see, you have them stored as they would appear in a string! so in the string "123" the char[0]=1, char[1] =2, char[2]=3 and so this is how you created you linked list.

This presents a problem becuse addition needs to be done from LSD to MSD (the opposit way you have it stored). It is difficult to read a single (or forward) linked list backwards.

so how do we do addition backwards...

456 + 10578 = first off we need to place all digits byond the common length
answer = 10
then add the common digits:
10[9][12][14]
then scan and carrie (in a loop until there is no more carries): First pass
10[10][2][14]
10[10][3][4]
second pass
11[0]34
last pass
11034. Answer since no more carries were required.

This seems a VERY inefficent way to do things. Storing the numbers in the linked list in the correct order would make the addition a single pass operation.

Another solution would be to actually do the addition in a stack (which is basicly the same thing as reversing the linked list and then adding except that you should not need to reverse the ansewer once your done). But this will use lots of memory.

I think you painted yourself into a corner by storing the numbers backwards. Converting two and from a string with the digits reversed would have been easier than trying to do arithmatic backwards.

to read "123\0" just scroll till you find '\0' and then start making your nodes backwards... when your index reaches 0 you have the MSD (would be the last node created).

I haven't the slightest clue how you mannaged multiplication backwards... division I can understand.
Was This Post Helpful? 0
  • +
  • -

#3 realNoName  Icon User is offline

  • D.I.C Regular

Reputation: 7
  • View blog
  • Posts: 343
  • Joined: 04-December 06

Re: Big Number Class

Posted 07 May 2007 - 02:31 PM

Quote

add = (temp/10?true:false); the condition temp/10 is already a boolean expression. To make sure it gives you a true boolean (1 for true 0 for false)
Yea i know i did it just so there where no warnings :)

Quote

Question: Why store the digits in reverse order?
I can put it in any other order i want... i had it the other way first but changed it

the thinking behind this was... well i dont know how to put it but anyways if you think its better to do it the other way am good with that
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Big Number Class

Posted 07 May 2007 - 02:46 PM

The addition algorithem if they are stored in a forward manner is rather strait forward.

int carry = 0;
while (walker || rWalker)
{
	if (walker && rWalker)
	{
		digit = carry + walker->digit + rWalker->digit;
		carry = digit % 10;
		digit /= 10;
		//add digit to answer's linked list
		walker = walker->next;
		rWalker = rWalker->next;
	} else
	{
		walker = walker ? walker: rWalker; // whichever one is not NULL
		while (walker)
		{
			digit = carry+walker.digit;
			//add digit to answer
			carry = 0; //only needed this for the first digit...
			walker = walker->next;
		}
	break;
	}
}

Or something like that... (shooting from the hip here, no idea if the above code works).




The more I think about it... The more I see major problems with this linked list structure.

First of all it is a terrible waste of space.
Was This Post Helpful? 0
  • +
  • -

#5 imamkomc  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 5
  • View blog
  • Posts: 64
  • Joined: 09-May 07

Re: Big Number Class

Posted 08 June 2007 - 01:10 AM

Nice to meet you.
My name is Imamkomc,

I will try to help you, but i dont give an anwer.
Now, me to having make program to compute big number and
I will give the program, i am using array no link list :

big number to operator +
*********************

bigint_add bigint_add::operator + (bigint_add num2)
{
int i,j,k,loop;
bigint_add result2;
result2.length_byte=length_byte;
if (length_byte>=num2.length_byte)
	{
   loop=length_byte;
   diff=abs(length_byte-num2.length_byte);
   for(j=length_byte;j>=1;j--)
   	{
	  num2.num[j+diff]=num2.num[j];
	  if(j<=diff)
		  {
		 num2.num[j]=0;
		 }
	  else if(j>diff)
		  {
		 num2.num[j]=num2.num[j-diff];
		  }
	  }
   result_add[loop]=0;
   for(k=loop;k>=1;k--)
   	{
	  result_add[k]+=num[k]+num2.num[k];
	  if(result_add[k]>=10 && k!=1)
		  {
		 result_add[k]=result_add[k]-10;
		 result_add[k-1]=1;
		 }
	  else
		  {
		 result_add[k]=result_add[k];
		 result_add[k-1]=0;
		 }
	  }
   }
else if(length_byte<num2.length_byte)
	{
   loop=num2.length_byte;
   for(i=1;i<=num2.length_byte;i++)
   	{
	  salin[i]=num[i];
	  }
   for(i=1;i<=num2.length_byte;i++)
   	{
	  num[i]=num2.num[i];
	  }
   diff=abs(num2.length_byte-length_byte);
   for(j=num2.length_byte;j>=1;j--)
   	{
	  if(j<=diff)
		  {
		 num2.num[j]=0;
		 }
	  else if(j>diff)
		  {
		 num2.num[j]=salin[j-diff];
		  }
	  }
   result_add[loop]=0;
   for(k=loop;k>=1;k--)
   	{
	  result_add[k]+=num2.num[k]+num[k];
	  if(result_add[k]>=10 && k!=1)
		  {
		 result_add[k]=result_add[k]-10;
		 result_add[k-1]=1;
		 }
	  else
		  {
		 result_add[k]=result_add[k];
		 result_add[k-1]=0;
		 }
	  }
   }
	for(k=1;k<=loop;k++)
   	{
	  num[k]=result_add[k];
	  }
   result2.length_byte=loop; // update value length_byte

   for(k=1;k<=loop;k++)
   	{
	  result2.num[k]=num[k];
	  }
return result2;
}

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1