[C++] Program for adding very large numbers

Discussion in 'Code Snippets and Tutorials' started by Khang685, Mar 20, 2008.

  1. Khang685

    Khang685 Newbie

    Joined:
    Mar 20, 2008
    Messages:
    28
    Likes Received:
    0
    As you know, an integer cannot store very large numbers. Here, I made use of arrays and implemented BigNum algorithm to add very large numbers. It can go as large as possible, with dynamic memory allocation.

    Code (Text):
    1. <div class="text" id="{CB}" style="font-family: monospace;"><ol><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">#include <stdio.h></li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">#include <stdlib.h></li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">#include <string.h></li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">int main(){</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; char tmp1[100], tmp2[100];</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; int B[100], C[100];</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; int array[100];</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; int i,j;</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; int n1, n2;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; int num=0;</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //set all arrays to -1</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; memset(array, -1, sizeof(array));</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; memset(B, -1, sizeof(B));</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; memset(C, -1, sizeof(C));</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //scan in the 2 no.s as strings</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; gets(tmp1);</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; gets(tmp2);</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //convert from strings to numbers</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(i = strlen(tmp1)-1, j=0; i >= 0; i--,j++)</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; B[j] = (int) tmp1[i] - '0';</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(i = strlen(tmp2)-1, j=0; i >= 0; i--,j++)</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; C[j] = (int) tmp2[i] - '0';</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //print out the two number, each on a separate line</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(i = strlen(tmp1)-1; i >= 0; i--)</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf("%d", B[i]);</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; printf("\n");</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(i = strlen(tmp2)-1; i >= 0; i--)</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf("%d", C[i]);</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; printf("\n");</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //set 1st element of array to 0.</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; array[0] = 0;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //algo for adding numbers</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; //loop through all the digits of the numbers and add.</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(j = 0; B[j] != -1 || num != 0 || C[j] != -1; j++){</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(array[j] == -1) array[j] = 0;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //if there are no digits of a number in jth place, avoid error by not adding -1</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(C[j]==-1) C[j] = 0;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(B[j]==-1) B[j] = 0;</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j] = B[j] + C[j];</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j] +=num;</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; num = 0;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(array[j]>=10){</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; num = (array[j] - array[j]%10)/10; //find out the no. of second digit</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; array[j] = array[j]-10;</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; //printf("%d", array[j]);</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; }</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(j = 0; array[j] != -1; j++){}</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; for(i = j-1; i>=0; i--)</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; printf("%d", array[i]);</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; printf("\n");</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; system("PAUSE");</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp; &nbsp; return 0;</li><li style="padding: 0 5px; background-color: #fff; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">}</li><li style="padding: 0 5px; background-color: #f9f9f9; line-height: 16px; border-bottom: 1px solid #efefef; border-left: 1px solid #999;">&nbsp;</li></ol></div>
     
  2. Zer0

    Zer0 Level IV

    Joined:
    Mar 2, 2008
    Messages:
    3,037
    Likes Received:
    180
    Location:
    Home sweet home
    There are already a huge amount of "BigInteger" libraries around the internet.
    I will list a few for others' reference:
    [*] http://gmplib.org/
    [*] http://mattmccutchen.net/bigint/
    [*] http://www.apfloat.org/apfloat/

    These libraries contain support for other operations such as subtraction, multiplication, etc.

    Of course, I'm not trying to downplay your code, I'm just saying that it is a bit redundant. Well done nevertheless