Long Multiplication

BIG NUMBER ARITHMETIC - MULTIPLICATION

The below code is to multiply very large numbers. I have given the test numbers as integers but it can handle numbers of any size. I have implemented this code in my sub page C Programs/ x power n

The idea is pretty straight forward, we need to multiply two very large numbers using long multiplication and for example if we multiply 98495270 by 90281 the result will look like this

9 8 4 9 5 2 7 0

9 0 2 8 1


9 8 4 9 5 2 7 0

7 8 7 9 6 2 1 6 0 0

1 9 6 9 9 0 5 4 0 0 0

0 0 0 0 0 0 0 0 0 0 0

8 8 6 4 5 7 4 3 0 0 0 0 0


8 8 9 2 2 5 1 4 7 0 8 7 0

The code below is implemented to multiply digit by digit so that it can handle n_digits more than that of c data types can handle. Also the below code has a version of long addition too.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int *number_to_digit(int *n, int *digit_count);
int split_lastDigit(int the_num,int *carryover);
int *long_multiplication(int *multiplicant,int multiplicant_dgcount,int *multiplier,int multiplier_dgcount,int *product_dgcount);
int *add_to_list(int *the_list,int the_value,int *list_count);
int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount);

int main()
{

    int a=90281,b=98495270,i; // INPUT HERE

    int multcant_dgcount;
    int *multcant=number_to_digit(&b,&multcant_dgcount);

    for(i=(multcant_dgcount-1);i>=0;i--)
    {
        printf("%d\t",*(multcant+i));
    }
    printf("\n");

    int multiplier_dgcount;
    int *multiplier = number_to_digit(&a,&multiplier_dgcount);

    for(i=(multiplier_dgcount-1);i>=0;i--)
    {
        printf("%d\t",*(multiplier+i));
    }
    printf("\n");

    int product_dgcount=0;
    int *product=long_multiplication(multcant,multcant_dgcount,multiplier,multiplier_dgcount,&product_dgcount);

    for(i=(product_dgcount-1);i>=0;i--)
    {
        printf("%d\t",*(product+i));
    }
    printf("\n");
    return 0;
}


int *long_addition(int *addition_dgtslist[],int addition_dgtscount[],int list_count, int *rslt_dgtcount)
{
    int i,j;
    // Find the maximum number of digits list
    // Idea is to fill zeroes for shorter numbers (numbers with less digits)
    int max_list_count = 0;
    for(i=0;i<list_count;i++)
    {
        if(max_list_count<addition_dgtscount[i])
        {
            max_list_count = addition_dgtscount[i];
        }
    }

    // Fill zeroes for shorter numbers
    for(i=0;i<list_count;i++)
    {
        for(j=addition_dgtscount[i];j<max_list_count;j++)
        {
            addition_dgtslist[i]=add_to_list(addition_dgtslist[i],0, &addition_dgtscount[i]);
        }

    }
    int *addition_result;
    (*rslt_dgtcount)=0;

    int carry_over = 0;
    int total_sum;

    for(j=0; j<max_list_count ;j++)
    {
        total_sum = carry_over;
        for(i=0;i<(list_count);i++)
        {
            total_sum = total_sum + (*(*(addition_dgtslist+i)+j)) ;
            //printf("%d",*(*(addition_dgtslist+i)+j));
        }
        addition_result=add_to_list(addition_result,split_lastDigit(total_sum,&carry_over),rslt_dgtcount);
    }
    // To add carry Over digits to the list
    int temp_carryover = carry_over;
    if(carry_over!=0)
    {
        addition_result=add_to_list(addition_result,split_lastDigit(temp_carryover,&carry_over),rslt_dgtcount);
        temp_carryover = carry_over;
    }
    return addition_result;
}

int *long_multiplication(int *multiplicant,int multiplicant_dgcount,int *multiplier,int multiplier_dgcount,int *product_dgcount)
{
    int i,j; //Loop variables
    int *product_summ[multiplier_dgcount]; //Variable to hold the digits of each multiplication results level
    int product_summ_dgcount[multiplier_dgcount];
    printf("\n");
    for(i=0;i<multiplier_dgcount;i++) //Loop thro' all the digits of multiplier 9 4 for 49
    {
        product_summ_dgcount[i] = 0; // set the product digit count as zero
        // Add zeroes at the end
        for(j=0;j<i;j++)// Have to add zeroes at the end of the product sum
        {
            product_summ[i]=add_to_list(product_summ[i],0,&product_summ_dgcount[i]);// added zeroes at the end
        }
        int carry_over = 0; //set the carryover as zero
        int temp_product; // variable to store temporary product
        for(j=0;j<multiplicant_dgcount;j++) //Loop thro' all the digits of multiplicant 4 2 0 1 for 1024
        {
            temp_product = carry_over + ((*(multiplier+i))*(*(multiplicant+j)));
            product_summ[i]=add_to_list(product_summ[i],split_lastDigit(temp_product,&carry_over),&product_summ_dgcount[i]);// added the digit
        }
        //Add the carry over digits to the product_summ
        int carry_over_sum;
        int *carry_over_digits =  number_to_digit(&carry_over,&carry_over_sum); //Split the carry_over digits
        for(j=0;j<carry_over_sum;j++)
        {
             product_summ[i]=add_to_list(product_summ[i],(*(carry_over_digits+j)),&product_summ_dgcount[i]);// added the carry over digits
        }
    }

    // Long addition
    for(i=0;i<multiplier_dgcount;i++)
    {
        // Check the results here
        for(j=(product_summ_dgcount[i]-1);j>=0;j--)
        {
            printf("%d\t",*(product_summ[i]+j));
        }
        printf("\n");
    }
    printf("\n");
    (*product_dgcount)=0;// Set product digit count as zero
    int *result_product = long_addition(product_summ, product_summ_dgcount,multiplier_dgcount,product_dgcount);
    return result_product;
}

int *add_to_list(int *the_list,int the_value,int *list_count)
{
    if((*list_count)==0)// There is no item in the list
    {
        the_list = (int *)malloc(1*sizeof(int)); // We initialize 1 space to the list
    }
    else
    {
        int *temp = (int *)realloc(the_list,(*(list_count)+1)*sizeof(int)); // Allocate one extra space
        if(temp != NULL)
        {
            the_list = temp;
        }
        else
        {
            printf("Error Allocating Memory");
        }
    }

    *(the_list+(*(list_count))) = the_value; // Adding the value here
    *(list_count) =(*(list_count))+1; // Increment the list count after addition
    return the_list; // return the list address
}


int split_lastDigit(int the_num,int *carryover)
{
    *(carryover) = (int)(the_num/10);
    return (the_num - (*(carryover)*10));
}


int *number_to_digit(int *n, int *digit_count)
{
    int numP,numC = *(n);
    int *digits = (int *)malloc(1*sizeof(int)); //Initially we allocate 1 space to digit list
    *(digit_count) = 0;// set digit_count = 0

    while(numC!=0)
    {
        numP = numC; //Set the numP value as numC then remove the last digit of numC
        //numC = numC/10
        numC=floor(numC/10);
        *(digits+(*(digit_count))) =(int)(numP - (numC*10)); //
        (*(digit_count))=(*(digit_count))+1;//Update the digit count

        int *temp=(int *)realloc(digits,(*(digit_count)+1)*sizeof(int)); // give the pointer some (+1 int) memory each time
        if (temp != NULL )
        {
            digits=temp; //Memory added here
        }
        else
        {
            printf("Error Allocating Memory");
        }
    }
    return digits;// return the digits address and the digit_count is already updated
}