Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 352
  • Last Modified:

linked lists, Large integers manipulation

i am writing a program that needs to do basic arithmatic on large integers that dont fit in a "int" value so i am storing them as linked lists ,backwards, so that when i use recursion to print the number it prints it out in the right order. anyways how would i go about adding and subtracting such large numbers? my struct is like so:
 struct integer{
      int data;
      struct integer *next;};
i am planning on making them functions that accept inputs of 2 head pointers for 2 sets of linkedlist numbers and returns a new head with the answer?

thanks
0
commanderchatt
Asked:
commanderchatt
  • 8
  • 4
  • 3
1 Solution
 
keenezCommented:
Is Long and/or Double only part of C++?  Try using these datatypes to store your value.

Cheers,

Keenez
0
 
akshayxxCommented:
commanderchatt:
what is the 'base' of ur number .. is it decimal OR binary OR hexadecimal..


keenz:
>>Is Long and/or Double only part of C++?  

its in C also :P
well these days in most systems .. unsigned int and unsigned long both are 4 bytes.. so he wont gain much.. from replacing int with long..double will help to some extent
and as i see from the asker's comment . i think he wants to implement arbitrary large integer mathematics..
0
 
commanderchattAuthor Commented:
it is a decimal number of for example 99 characters i want to be able to do addition and subtraction with 2 numbers of that size i already looked into all arithmetic type i knew of: int,unsigned int, long, unsigned long, long long, unsigned long long, float, double, and long double.           all of them are still to small it needs to be in a linked list
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
keenezCommented:
Well then, I assume an add algorithm would have to go something like:

Create a 3rd Linked List
Set carryover value = 0
loop through linked lists {
  Add the 2 data numbers in the linked list (or if we've reached the end of a linked list, add 0 or logic to skip, etc ....)
  AND add the carryover to above
  Store the units digit in the linked list
  calculate the new carryover value (divide by 10)
}

To do subtraction,

Create a 3rd linked list
set carryover value = 0
loop through linked lists {
  if carryover = 1 {
     subtract 1 from data1
   }
  if data1 < data2 {
     carryover = 1
     data1 = data1 + 10
     store on linked list (data1 - data2)
  else
     carryover = 0
     store on linked list (data1 - data2)
  }
}

Of course, you're going to have to handle the case when the number of nodes in each linked list aren't the same for the subtraction and to think about signs.

Cheers,

keenez
0
 
keenezCommented:
Oh .... I just checked your structure ....

You're going to need a tail pointer and a previous pointer (well, you' don't need but it's faster).  

Cheers,

Keenez
0
 
akshayxxCommented:
if you are looking for something different or more specific .. then let us know .. else close the question
0
 
commanderchattAuthor Commented:
im actually having trouble with the code itself i understand the idea but i am not extremely familiar with the -> character and all that so i cant really program the actual code.
             printf("Please enter the first integer");
             first=ReadInt();
             printf("Please enter the second integer");  
             second=ReadInt();
             result=AddInt(first,second);
             PrintInt(&result);


the addint function is what i am having trouble building how would i go about this code wise.
0
 
akshayxxCommented:
u mean to say that u dont know how to read .. that means you dont know how to use scanf?

and as for '->' is concerned .. it isnt a character . its two characters and hence a symbol..

it is used to refer to the members of the structure..when u have a pointer to it..

here i'll explain how can u insert some node in the linked list .. u better refer your text books ..

typedef struct _node{
int data;
struct _node *next;
}node;

node *head;

head=NULL; //initially list is empty

so if u wanna read in an element and insert in the list pointed by the 'head'

int value;
node *temp;

------code to insert the node in the list-----
----- this will insert the new node at the head of the list---------

scanf("%d",&value);
temp=(node*)malloc(sizeof(node));
temp->data=value;  // to access the 'data' element of 'memory' pointed by 'temp'
temp->next=head;
head=temp;




to traverse and operate on the members of list
node *ptr=head;
for(;ptr!=NULL;ptr=ptr->next){
//operate on ptr->data
}


NOTE.. above method will insert the new node at the start of the  list pointed with 'head'
so if u enter numbers in the sequnce
 1
 2
 3
 4
 5
list will look like
5 4 3 2 1
0
 
commanderchattAuthor Commented:
akshayxx i can do all that already i have code that reads a number and prints it no prob but its the code that adds and subtracts i need.    i use getchar in my read function though cause i want the user to enter in the entire number not    5 then 3 then 1   for 531
0
 
akshayxxCommented:
ok tell me how does ur linked list store a number 12345 ..
how does ur linked list look like ..  does ur head point to 5 ( least significant digit ) OR 1 ( most significant digit)..
tell this and we can help u out
0
 
commanderchattAuthor Commented:
while(isdigit(input=getchar())){listptr=(struct integerNode* ) malloc(sizeof(struct integerNode));
         
         listptr->data = input;
         listptr->next = head;
         head=listptr;
}

this is how i input into the list and my function return head
0
 
akshayxxCommented:
i hope u are aware that, while you are reading .. u are filling up the ascii value of the characters '0'...'9'

so while adding and/or subtracting u have to take this into cosideration..
OR while reading the number change ur line

listptr->data=input;
to
listptr->data=input -'0';

but then while u'll be printing our ur integers u have to take care if u r using %d OR %c ..

and as for adding and substractomg algorithm .. tell us where are u stuck..
looking at ur reading function  it is clear that ur integer pointer points to the least significant digit .. which is helpful for the both cases of mathemetical operations..

also tell us.. in ur substraction do u take want to take care if u r substracting larger integer from smaller one .. i.e. is ur program supposed to take care of negative integers or not ..  for the negative integer case u need additional member to ur struct that will keep the sign of the integer.. negative/positive..

for the addtion the case is pretty straight forward ( in case of both positive integers)

make another integerNode *sumP;
and start browsing ur  operand integerNode pointers.. say ip and jp

//assuming ur listptr-data keeps the value of the digit and not its ascii value..
that is  ip->data = 5  and not '5'
// also at the end of following addition procedure u'll end up with the resulted number  in reversed form ( wrt ur original numbers)
//
int carry=0,add;
sumP=NULL;
integerNode *temp;

while(ip!=NULL && jp !=NULL){
temp=(intederNode*)malloc(sizeof(integerNode));
add=ip->data+jp->data+carry;
temp->data=add%10;
carry=add/10;
ip=ip->next;
jp=jp->next;
temp->next=sumP;
sumP=temp;
}
// at this point at least one of ip or jp is consumed to full length

 if(ip !=NULL){// jp==NULL
// jp is consumed  ip still left
while(ip != NULL ){  
temp=(intederNode*)malloc(sizeof(integerNode));
add=ip->data+carry;
temp->data=add%10;
carry=add/10;
ip=ip->next;
temp->next=sumP;
sumP=temp;
}

}
else if(jp !=NULL){// ip==NULL
// ip is consumed  jp still left
while(jp != NULL ){  
temp=(intederNode*)malloc(sizeof(integerNode));
add=jp->data+carry;
temp->data=add%10;
carry=add/10;
jp=jp->next;
temp->next=sumP;
sumP=temp;
}

}

  // this means both ip and jp are finished up
//now  we need to take care of carry
  //( it will be either 1 or 0)

  if(carry)  
  temp=(intederNode*)malloc(sizeof(integerNode));
  temp->data=carry;
  temp->next=sumP;
  sumP=temp;




now the pointer sumP is reversed sum .. so reverse the list now..
0
 
akshayxxCommented:
try to implement above and show ur code ..
we here stick to this policy of not giving full source code ..   as it seems that this is some project assignment
0
 
akshayxxCommented:
forgot the braces
if(carry)  {
 temp=(intederNode*)malloc(sizeof(integerNode));
 temp->data=carry;
 temp->next=sumP;
 sumP=temp;
}
0
 
akshayxxCommented:
WELL .. i used the above pasted code as it is .. ( except for typo like intederNode   --> integerNode )

and it works perfectly .. so at least ur positive integer addition code is ready .. dont forget to reverse the integerNode list pointer for the sum obtained
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 8
  • 4
  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now