?
Solved

linked lists, Large integers manipulation

Posted on 2003-03-05
15
Medium Priority
?
349 Views
Last Modified: 2013-12-14
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
Comment
Question by:commanderchatt
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 4
  • 3
15 Comments
 
LVL 2

Expert Comment

by:keenez
ID: 8073898
Is Long and/or Double only part of C++?  Try using these datatypes to store your value.

Cheers,

Keenez
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8076278
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
 

Author Comment

by:commanderchatt
ID: 8076550
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 2

Expert Comment

by:keenez
ID: 8083507
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
 
LVL 2

Expert Comment

by:keenez
ID: 8083566
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
 
LVL 8

Expert Comment

by:akshayxx
ID: 8084723
if you are looking for something different or more specific .. then let us know .. else close the question
0
 

Author Comment

by:commanderchatt
ID: 8085770
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
 
LVL 8

Expert Comment

by:akshayxx
ID: 8085837
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
 

Author Comment

by:commanderchatt
ID: 8089426
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
 
LVL 8

Expert Comment

by:akshayxx
ID: 8089908
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
 

Author Comment

by:commanderchatt
ID: 8092769
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
 
LVL 8

Accepted Solution

by:
akshayxx earned 300 total points
ID: 8093911
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
 
LVL 8

Expert Comment

by:akshayxx
ID: 8093916
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
 
LVL 8

Expert Comment

by:akshayxx
ID: 8093930
forgot the braces
if(carry)  {
 temp=(intederNode*)malloc(sizeof(integerNode));
 temp->data=carry;
 temp->next=sumP;
 sumP=temp;
}
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8093940
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

Introducing Priority Question

Increase expert visibility of your issues by participating in Priority Question, our latest feature for Premium and Team Account holders. Adjust the priority of your question to get emergent issues in front of subject-matter experts for help when you need it most.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In our object-oriented world the class is a minimal unit, a brick for constructing our applications. It is an abstraction and we know well how to use it. In well-designed software we are not usually interested in knowing how objects look in memory. …
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

741 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question