Difference between revisions of "Sum of large numbers in C"

(Created page with "Complexity <math>\theta(n)</math> No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math> <syntaxhighlight lang="c" name="largesum"> #include <stdio.h> #include<s...")
 
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Complexity <math>\theta(n)</math>
+
Write a program which can do sum of large numbers having up to 1000 digits
  
−
No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
  
 
<syntaxhighlight lang="c" name="largesum">
 
<syntaxhighlight lang="c" name="largesum">
 
#include <stdio.h>
 
#include <stdio.h>
−
#include<string.h>
+
#include <string.h>
−
#include<ctype.h>
+
#include <ctype.h>
−
 
+
 
void print(char *a, int l);
 
void print(char *a, int l);
 
int read(char *a);
 
int read(char *a);
−
 
+
int sum(char *a, char* b, char * c, int al, int bl);
 
int main(void) {
 
int main(void) {
−
char a[1000], b[1000], c[1000], carry;
+
char a[1000], b[1000], c[1000]; //a and b hold the input numbers and c hold the output number. Each array entry is a digit
−
int al, bl;
+
int al, bl; //for storing the number of digits of the two input numbers
 
printf("Enter the first number ");
 
printf("Enter the first number ");
 
al = read(a);
 
al = read(a);
−
fflush(stdin);
 
 
printf("Enter the second number ");
 
printf("Enter the second number ");
 
bl = read(b);
 
bl = read(b);
−
int l = al > bl? al:bl;
+
int l = sum(a, b, c, al, bl);
−
int i = l;
 
−
carry = 0;
 
−
while(al > 0 && bl > 0)
 
−
{
 
−
char val = a[--al]  + b[--bl] + carry;
 
−
c[i--] = val %10;
 
−
carry =  val/10;
 
−
}
 
−
while(al > 0)
 
−
{
 
−
char val = a[--al]  + carry;
 
−
                c[i--] = val %10;
 
−
                carry =  val/10;
 
−
}
 
−
while(bl > 0)
 
−
{
 
−
char val =  b[--bl] + carry;
 
−
                c[i--] = val %10;
 
−
                carry =  val/10;
 
−
}
 
−
c[0] = carry;
 
 
printf("sum = ");
 
printf("sum = ");
−
print(c, l+1);
+
print(c, l);
 
return 0;
 
return 0;
 
}
 
}
 +
 +
int sum(char *a, char* b, char * c, int al, int bl)
 +
{
 +
int l = al > bl? al:bl;//l stores the no.of digit of output which may become l+1 due to carry from MSB
 +
        int i = l;
 +
        char carry = 0;
 +
        while(al > 0 && bl > 0)
 +
        {
 +
                char val = a[--al]  + b[--bl] + carry;
 +
                c[i--] = val % 10;
 +
                carry =  val / 10;
 +
        }
 +
        while(al > 0)//If a has more digits than b
 +
        {
 +
                char val = a[--al]  + carry;
 +
                c[i--] = val % 10;
 +
                carry =  val / 10;
 +
        }
 +
        while(bl > 0)//If b has more digits than a
 +
        {
 +
                char val =  b[--bl] + carry;
 +
                c[i--] = val % 10;
 +
                carry =  val / 10;
 +
        }
 +
        c[0] = carry;//Assigning the final carry
 +
return l+1;//Return the no. of digits of output
 +
}
  
 
int read(char *a)
 
int read(char *a)
Line 50: Line 55:
 
char c;
 
char c;
 
int i = 0;
 
int i = 0;
−
while(1)
+
do
 
{
 
{
 
c = getchar();
 
c = getchar();
−
if(!isdigit(c))
 
−
break;
 
−
a[i++] = c-48;
 
 
}
 
}
−
return i;
+
while(isspace(c)); //Reading and discarding any whitespace char typed
 +
while(isdigit(c))
 +
{
 +
a[i++] = c - 48; //getchar returns the ASCII. So, for 1 it returns 49. Subtracting 48, we get the actual int value entered via keyboard
 +
c = getchar();
 +
}
 +
return i;//Return the no. of digits read
 
}
 
}
 +
 
void print(char *a, int l)
 
void print(char *a, int l)
 
{
 
{
 
int i;
 
int i;
 
if(a[0] != 0)
 
if(a[0] != 0)
−
printf("%d",a[0]);
+
printf("%d", a[0]);//If final carry is 0, ignore it
 
for(i = 1; i < l; i++)
 
for(i = 1; i < l; i++)
 
{
 
{
Line 70: Line 79:
 
printf("\n");
 
printf("\n");
 
}
 
}
−
 
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
===Explanation===
 
  
  

Latest revision as of 15:54, 17 June 2014

Write a program which can do sum of large numbers having up to 1000 digits

Solution by Arjun Suresh

<syntaxhighlight lang="c" name="largesum">

  1. include <stdio.h>
  2. include <string.h>
  3. include <ctype.h>

void print(char *a, int l); int read(char *a); int sum(char *a, char* b, char * c, int al, int bl); int main(void) { char a[1000], b[1000], c[1000]; //a and b hold the input numbers and c hold the output number. Each array entry is a digit int al, bl; //for storing the number of digits of the two input numbers printf("Enter the first number "); al = read(a); printf("Enter the second number "); bl = read(b); int l = sum(a, b, c, al, bl); printf("sum = "); print(c, l); return 0; }

int sum(char *a, char* b, char * c, int al, int bl) { int l = al > bl? al:bl;//l stores the no.of digit of output which may become l+1 due to carry from MSB 

       int i = l;
       char carry = 0;
       while(al > 0 && bl > 0)
       {
               char val = a[--al]  + b[--bl] + carry;
               c[i--] = val % 10;
               carry =   val / 10;
       }
       while(al > 0)//If a has more digits than b
       {
               char val = a[--al]  + carry;
               c[i--] = val % 10;
               carry =   val / 10;
       }
       while(bl > 0)//If b has more digits than a
       {
               char val =  b[--bl] + carry;
               c[i--] = val % 10;
               carry =   val / 10;
       }
       c[0] = carry;//Assigning the final carry

return l+1;//Return the no. of digits of output }

int read(char *a) { char c; int i = 0; do { c = getchar(); } while(isspace(c)); //Reading and discarding any whitespace char typed while(isdigit(c)) { a[i++] = c - 48; //getchar returns the ASCII. So, for 1 it returns 49. Subtracting 48, we get the actual int value entered via keyboard c = getchar(); } return i;//Return the no. of digits read }

void print(char *a, int l) { int i; if(a[0] != 0) printf("%d", a[0]);//If final carry is 0, ignore it for(i = 1; i < l; i++) { printf("%d", a[i]); } printf("\n"); } </syntaxhighlight>





blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Sum_of_large_numbers_in_C&oldid=3502"

Complexity <math>\theta(n)</math>

No. of swaps in the worst case = <math> \lfloor n/2 \rfloor</math>

<syntaxhighlight lang="c" name="largesum">

  1. include <stdio.h>
  2. include<string.h>
  3. include<ctype.h>

void print(char *a, int l); int read(char *a);

int main(void) { char a[1000], b[1000], c[1000], carry; int al, bl; printf("Enter the first number "); al = read(a); fflush(stdin); printf("Enter the second number "); bl = read(b); int l = al > bl? al:bl; int i = l; carry = 0; while(al > 0 && bl > 0) { char val = a[--al] + b[--bl] + carry; c[i--] = val %10; carry = val/10; } while(al > 0) { char val = a[--al] + carry; 

               c[i--] = val %10;
               carry =   val/10;

} while(bl > 0) { char val = b[--bl] + carry; 

               c[i--] = val %10;
               carry =   val/10;

} c[0] = carry; printf("sum = "); print(c, l+1); return 0; }

int read(char *a) { char c; int i = 0; while(1) { c = getchar(); if(!isdigit(c)) break; a[i++] = c-48; } return i; } void print(char *a, int l) { int i; if(a[0] != 0) printf("%d",a[0]); for(i = 1; i < l; i++) { printf("%d", a[i]); } printf("\n"); }

</syntaxhighlight>

Explanation[edit]



blog comments powered by Disqus