///\file proiect.c
///\brief C library implementation for operations with large numbers.
///
/// Created by Cristescu Ovidiu
/// Implements addition, substraction, multiplication, division and the square root


#include<string.h>
#include<stdio.h>
#define MAX 10000
///\def #define MAX 10000
///\brief Define the maximum number possible as 10000.

typedef int bool;


void addition(char s1[256], char s2[256])
{
    ///\fn void addition(char s1[256], char s2[256])
    ///\brief In this function, we calculate the addition of two numbers
    ///\param s1 First number
    ///\param s2 Second number
    /// We calculate the addition by transforming the input numbers from char to integers

    int num1[255], num2[255], sum[255];
    ///num1 is an array used to store the first number
    ///num2 is an array used to store the second number
    ///sum is an array used to calculate the addition of the two numbers num1 and num 2

    int l1, l2;
    ///l1 is the lenght of the first number
    ///l2 is the lenghtof the second number


    for (l1 = 0; s1[l1] != '\0'; l1++)
    {
        ///Transformation from char to integer;
        num1[l1] = s1[l1] - '0';
    }


    for (l2 = 0; s2[l2] != '\0'; l2++)
    {
        ///Transformation from char to integer;
        num2[l2] = s2[l2] - '0';
    }

    ///Carry is a variable used when the sum of num1[i] and num2[j] is bigger than 9
    int carry = 0;
    int k = 0;
    int i = l1 - 1;
    int j = l2 - 1;

    for (; i >= 0 && j >= 0; i--, j--, k++)
    {
        ///Calculate the sum
        sum[k] = (num1[i] + num2[j] + carry) % 10;
        ///Calculate the carry (if we have one)
        carry = (num1[i] + num2[j] + carry) / 10;
    }



    if (l1 > l2)
    {
        ///If the first number is longer than the other, we add the carry that remains (if it exists) to the next digit
        while (i >= 0) {

            sum[k++] = (num1[i] + carry) % 10;
            carry = (num1[i--] + carry) / 10;
        }

    }
    else
        ///Otherwise, we do the same thing, but with the second number
        if (l1 < l2)
        {
            while (j >= 0)
            {
                sum[k++] = (num2[j] + carry) % 10;
                carry = (num2[j--] + carry) / 10;
            }
        }
        ///If we finished the numbers, but we still have the carry, we add him to the sum
        else
        {
            if (carry > 0)
                sum[k++] = carry;
        }


    ///We print the sum from the end the of array
    for (k--; k >= 0; k--)
        printf("%d", sum[k]);
}


void reverse(char *from, char *to )
{
    ///\fn void reverse(char *from, char *to )
    ///\brief This function is used to reverse  a number
    ///\param from Pointer to the number we want to reverse
    ///\param to Pointer to the number we want to store the reversed number

    int len = strlen(from);
    int l;

    for(l=0;l<len;l++)
    {
        ///here, the process of reversing is made
        to[l]=from[len-l-1];
    }

    to[len] = '\0';
}


int call_minus(char *large, char *small, char *result)
{
    ///\fn int call_minus(char *large, char *small, char *result)
    ///\brief In this function, we calculate the substraction of two numbers
    ///\param large Pointer to the first number, who is supposed to be larger
    ///\param small Pointer to the second number which is supposed to be lower
    ///\param result Pointer to a char where we calculate the result of the substraction


    char L[MAX], S[MAX];
    int l, s, now, hold, diff;

    /// the lenght of the first number
    l = strlen(large);

    ///the lenght of the second number
    s = strlen(small);

    ///sign is a boolean variable, we store in it the sign of our substraction
    bool sign = 0;


    if(l < s)
    {
        ///If the first number is smaller than the second, we interchange them, and our sign is 1, that means our result is negative
        ///Using the function strcpy we iterchange the numbers
        strcpy(result, large);
        strcpy(large, small);
        strcpy(small, result);

        ///Using the variable now, we also interchange the lenghts of the numbers
        now = l;
        l = s;
        s = now;
        sign = 1;
    }

    if(l == s)
    {
       ///If the lenghts of the numbers are equals
       if(strcmp(large, small) < 0)
       {
            ///if the first one is smaller:
            ///We interchange them,  and our sign is 1, that means our result is negative
            strcpy(result, large);
            strcpy(large, small);
            strcpy(small, result);

            ///Using the variable now, we also interchange the lenghts of the numbers
            now = l;
            l = s;
            s = now;
            sign = 1;
        }
    }
    ///We reverse the numbers to calculate the substraction.
    ///In L we store the bigger number.
    reverse(large,L);
    ///In S we store the smaller number.
    reverse(small,S);

    for(; s<l; s++)
    {
        ///We complete the smaller number with 0, because it doesn't affect our calculations
        S[s] = '0';
    }
    ///the end of the string
    S[s]='\0';

    for(now=0,hold=0;now<l;now++)
    {
        ///we calculate the difference between L[now] and S[now]
        ///hold is a variable used when L[now] (a digit of the first number) is smaller than S[now] (a digit from the second number
        diff = L[now] - (S[now]+hold);

        if(diff < 0)
        {
            ///If our difference is smaller than 0, hold becomes 1 and at our result we add diff (the differrece) at the result
            hold = 1;
            ///We add ten because we borrow it from  the next digit, this is why our hold becomes 1 */
            result[now] = 10 + diff + '0';
        }

        else
        {
            ///Otherwise , we simply add our difference to the result
            result[now] = diff + '0';
            ///Hold becomes 0 because we didn't have to borrow, because the digit L[now] was greater than the digit S[now]
            hold = 0;
        }
    }

    for(now=l-1; now>0; now--){
        if(result[now] != '0')
            break;
    }
    ///end of string
    result[now + 1] = '\0';
    ///We reverse the result, because when we store it, we start with the end of the result
    reverse(result, L);
    ///We copy the new result in the char result
    strcpy(result, L);
    /// we return the sign because we have to know if the output will be positive of negative
    return sign;
}

void subtraction(char fir[256], char sec[256])
{
    ///\fn void subtraction(char fir[256], char sec[256])
    ///\brief In this function we call the function call_minus and we print the result of the substraction
    ///\param *fir First number
    ///\param sec Second number
    int i;
    ///In res we store the result, calculated in the function call_minus
    char res[MAX];


    if(call_minus(fir, sec, res) == 1)
    {
        ///If the function call_minus return 1, it means our result is negative and we have to print "-" ar the beginning of the result
        printf("\n-");
    }

    int len = strlen(res);


    for(i=0; i<len; i++)
    {
        ///Printing the result of the substraction
        printf("%c",res[i]);
    }

    printf("\n");
}


char * multiply(char a[256],char b_1[256])
{
    ///\fn char * multiply(char a[256],char b_1[256])
    ///\brief This function is used to calculate the multiplication of two numbers
    ///\param a First number
    ///\param b Second number
    ///The operation is made transforming the numbers from char to integers

    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la, lb;
    int i, j, k=0, x=0, y;
    long int r=0;
    long sum = 0;
    char d[MAX];

    /// We copy our number in the string d because in this function there are made some changes, and the number is modified on the way
    strcpy(d,a);

    la = strlen(d) - 1;
    lb = strlen(b_1) - 1;

        for(i=0; i<=la; i++)
        {
            /// We transform the first number from char to integer, every character becomes a digit of the number
            d[i] = d[i] - '0';
        }

        for(i=0; i<=lb; i++)
        {
            /// We transform the second number from char to integer, every character becomes a digit of the number
            b_1[i] = b_1[i] - '0';
        }

    for(i=lb; i>=0; i--)
    {
         r = 0;
         for(j=la; j>=0; j--)
         {
             ///We multiply the numbers, digit by digit, and we store them in parameter temp
             temp[k++] = (b_1[i]*d[j] + r)%10;
             ///r is a parameter used to store the div by ten of the multiplication of the numbers, digit by digit.
             r = (b_1[i]*d[j]+r)/10;
         }

         ///If at the end of the digits, we still have the r, we add him in our temp
         temp[k++] = r;
         x++;

         for(y = 0; y<x; y++)
         {
             temp[k++] = 0;
         }
    }

    k = 0;
    r = 0;

    for(i=0; i<la+lb+2; i++)
    {

         ///After we store the multiplication of the digits, we sum them, to obtain the final result
         sum = 0;
         y = 0;

         for(j=1; j<=lb+1; j++)
         {
             if(i <= la+j)
             {
                 sum = sum + temp[y+i];
             }

             y += j + la + 1;
         }

         c[k++] = (sum + r) % 10;
         r = (sum + r)/10;
    }

    c[k] = r;
    j=0;

    for(i=k-2; i>=0; i--)
    {
        ///We transform from integer to char
         mul[j++]=c[i] + '0';
    }

    mul[j]='\0';
    return mul;
}

void multiplication(char a[256], char b_1[256])
{
    ///\fn void multiplication(char a[256], char b_1[256])
    ///\brief In this function we call the function multiply and we print the result using parameter c
    ///\param a First number
    ///\param b_1 Second number

    char *c;

    printf("Multiplication of two numbers : ");
    c = multiply(a,b_1);
    printf("%s\n",c);


}

char * division(char a[256],unsigned long b)
{
    ///\fn char * division(char a[256],unsigned long b)
    ///\brief The function is used to calculate the division of two numbers
    ///\param a First number
    ///\param b Second number
    static char c[MAX];
    int la;
    int i, k=0, flag = 0;
    unsigned long temp = 1, reminder;
    char number[256];

    ///We copy the number a in the parameter number, because during this function, the number is modified and it may cause errors at the other functions
    strcpy( number,a);

    la=strlen( number);

    for(i=0;i<=la;i++)
    {
        ///We transform from char to integer
         number[i] =  number[i] - '0';
    }

    temp =  number[0];
    reminder =  number[0];

    for(i=1; i<=la; i++)
    {
        ///Here, we calculate the division
         if(b <= temp)
         {
             ///If the divisor (b ) is smaller or equal than the first digit, we devide it and we store the rest in the parameter reminder
             ///Parameter c is used to store the result
             c[k++] = temp/b;
             temp = temp % b;
             reminder = temp;
             temp = temp * 10 +  number[i];
             flag = 1;

         }
         else
         {
             ///Otherwise, we store the temp in the reminder
             reminder = temp;
             temp = temp * 10 +  number[i];

             if(flag == 1 )
                 c[k++] = 0;
         }
    }

    for(i=0;i<k;i++)
    {
        ///We trasform from integer to char
         c[i]=c[i] + 48;
    }

    c[i]= '\0';

    printf("Reminder of division:  %lu  ", reminder);
    return c;
}

void division_function(char a[256])
{
    ///\fn void division_function(char a[256])
    ///\brief This function is used to call the function division and print the result, using parameter c
    ///\param a Our dividend
    char *c;
    unsigned long b;

    printf("\nInsert the divisor: ");
    scanf("%lu", &b);
    c = division(a,b);
    printf("\nResult of the division : ");
    printf("%s\n",c);

}


void square_root(char numar[256])
{
    ///\fn void square_root(char numar[256])
    ///\brief This function is used to calculate the square root of our number, grouping the digits of the number in twos
    ///\param a The number
    ///The result is printed digit by digit, every time we execute the operation of the pairs of two digits


    unsigned long  reminder, lungime,  i, k, modulo, nr, rez = 0, lung;
    int j;

    lungime = strlen(numar);

    for(i=0; i<lungime; i++)
    {
        ///We transform from char to integer
        numar[i] = numar[i] - '0';
    }

    ///We need to know if the lenght of our number is even or odd
    modulo = lungime % 2;

    if(modulo == 0)
    {
        ///If the lenght is even we calculate the square root, grouping the digits in twos
        lung = 0;
        reminder = 0;
        ///First, we calculate for the first two digits and we need to find the biggest digit that has his square smaller or equal with them
        nr = (reminder * 100) + (numar[0] * 10) + numar[1];
        ///Parameter j is used to find the digit, and  we start with the biggest one and we decrease it untill we find it
        j=9;
        while(!(((j*j) <= nr)))
        {

            j--;
        }
        ///After we found it, we use the reminder to store the rest between our number consisted of the two first digits and the square of the digit found
        reminder = nr - (j*j);
        ///We calculate the result in parameter rez
        rez = rez * 10 + j;
        ///To continue the calculations for the rest of the digits, we need to store the double of the result in the parameter k
        k = 2 * rez;

        printf("%d", j);

        for (i=2; i<lungime; i=i+2)
        {
            ///For the rest of the digits, we do the same as above
            nr = (reminder * 100) + (numar[i] * 10) + numar[i+1];
            j=9;
            ///This time, we have to find the biggest digit that added to the end of k (our result doubled) and we multiply the obtained number by that digit and the result must be smaller or equal than our number consists of the two digits
            while(!(((((k*10) + j) * j)) <= nr))
            {

                j--;
            }

            reminder = nr - (((k*10) + j) * j);
            rez =rez * 10 + j;
            k = 2 * rez;

            printf("%d", j);
        }
    }
    else
    {
        ///Otherwise, if the lenght is odd, we do the same as above, but we start with the first digit, and then continue with the others, making pairs of two
        lung = 0;
        reminder = 0;
        nr = (reminder * 100) +  numar[0];
        j=9;
        while(!(((j*j) <= nr)))
        {
            j--;
        }
        reminder = nr - (j*j);

        rez =rez * 10 + j;
        k = 2 * rez;
        printf("%d", j);

        for (i=1; i<lungime; i=i+2)
        {
            nr = (reminder * 100) + (numar[i] * 10) + numar[i+1];
            j=9;
            while(!(((((k*10) + j) * j)) <= nr))
            {

                j--;
            }
            reminder = nr - (((k*10) + j) * j);
            rez = rez * 10 + j;
            k = 2 * rez;
            printf("%d", j);

        }
    }

}