Grade School High Precision Floating Point Number Adder Implementation in C++

Warning: This program has not been thoroughly tested. So it may produce incorrect results.

How the Code Works:

Note this problem calculates the integer and fractional portion separately in array as opposed to techniques learned in numerical analysis. To test if outputs are correct check against other high precision calculator such as this calculator.

Similar to this problem or same techniques used in uva problem 424 integer inquiry solution, uva problem 10035 primary arithmetic solution, uva problem 713 adding reversed numbers solution. The technique from this problem can also be applied to the mentioned problems.


Solution Steps:
Example Input:
25.401
534.2914
710.84
9.7808
980.7223

Note here are two separate arrays with one for decimal part and other for fraction. The dot is not stored anywhere, it is just shown to make it easy to understand. First the numbers are aligned with padding functions to create this,

025 . 4010
534 . 2914
710 . 8400
009 . 7808
980 . 7223

Although not used in this problem below, this pic that shows how I calculated sum column-row (column major) wise which is not cache friendly.

uva 424 integer inquiry order of operation
uva 424 integer inquiry order of operation

As shown in the pic above the technique is almost same but this time row and columns are interchanged and kept in a separate array which looks like this,

New Decimal Array:
05709 
23108 
54090 
New Fraction Array:
42877
09482
11002
04083

Next the operation is carried out as shown below,

row wise addition of high precision floating point numbers
row wise addition of high precision floating point numbers

Sample Test Input:

3.6692156156
65652.6459156456415616561
33.54615616
1.1
9854949494968498.49684984444444444444444443213615312613216512331918565

Output:

Output: 9854949495034189.45813726568600610054444443213615312613216512331918565

Code:

/********************************************************************************************
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Naive High Precision Floating Point Number Adder
 *
 * Warning:   This Code is mostly useless and hard to read. It is not represented in
 *            usual sign, exponent sign, exponent magnitude, mantissa magnitude format.
 *            The Program should produce correct output till given FRACTION_LIMIT after
 *            decimal point for unsigned numbers (Negative numbers not supported).
 *
 *            Also it may not necessary produce correct result as it is not throughly
 *            tested. Use it with caution.
 *
 *            Please follow input format. I have not handled any exception for incorrect
 *            input formats.
 *
 *******************************************************************************************/



#include<stdio.h>
#include<string.h>



// Increase the TEST_NUMBERS to calculate more float numbers.
#define TEST_NUMBERS  5

#define DECIMAL_SIZE  100
#define FRACTION_SIZE 100




// Function Prototypes
void sumDecimal(char **, int, int);
void sumFractions(char **, int);


// Array for holding decimal and fractional portion
static char decimal[TEST_NUMBERS][DECIMAL_SIZE];
static char fraction[TEST_NUMBERS][FRACTION_SIZE];


// Pointers reversed decimal and fractional result array.
char *resDec, *resFrac;
int resDecLen, resFracLen;



// Align decimal portion of the numbers and zeros.
void fixPaddingDecimal(int carry){

    // Holds calculated length of all strings.
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest decimal.
    int maxlength = memo[0] = strlen(decimal[0]);


    // Get the max length for padding or aligning.
    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(decimal[i]);
        if( len > maxlength )
            maxlength = len;
    }



    // Shift elements by appropriate positions or, create padding.
    // Look at my other linked pages from the post to understand this part.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            int padding = maxlength - len;

            for(int j = len - 1; j >= 0; --j)
                decimal[i][padding + j] = decimal[i][j];

            for(int j = 0; j < padding; ++j)
                decimal[i][j] = '0';
        }
    }



    // Create a new 2D array that will hold values in the new changed order.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Copy decimal portion to the mew changed order array.
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = decimal[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */


    // After fixing alignment add the decimal portion.
    sumDecimal( cacheFrindlyFloatOrganization, maxlength, carry);

}



// Add all the decimal numbers.
void sumDecimal(char **cacheFrindlyFloatOrganization, int maxlength, int carry){

    // Holds the output decimal part in reversed order.
    char *resultDecimal = new char[maxlength + 1];

    int z = 0;


    // Again look at the pages linked from this post.
    // I have explained this in uva 424, 10035, 713 etc.
    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultDecimal[z++] = sum % 10 + '0';
        carry = sum / 10;
    }

    // Stored in reversed order
    if(carry)
        resultDecimal[z++] = carry + '0';
    resultDecimal[z] = '\0';


    // Store the address and length of resultDecimal
    resDec = resultDecimal;
    resDecLen = z;


}



// As explained above this ALMOST does the same thing as function decimal code.
void fixPaddingFraction(){

    // Holds calculated length of all strings
    static int memo[TEST_NUMBERS];


    // Find out the max length of largest fraction
    int maxlength = memo[0] = strlen(fraction[0]);

    for(int i = 1; i < TEST_NUMBERS; ++i){
        int len = memo[i] = strlen(fraction[i]);
        if( len > maxlength )
            maxlength = len;
    }


    // Add zeros to empty positions.
    for(int i = 0; i < TEST_NUMBERS; ++i){
        int len = memo[i];

        if( len != maxlength ){
            for(int j = len ; j < maxlength; ++j)
                fraction[i][j] = '0';
            fraction[i][maxlength] = '\0';
        }
    }


    // Explained above.
    char **cacheFrindlyFloatOrganization = new char*[maxlength + 1];
    for(int i = 0; i < maxlength; ++i)
        cacheFrindlyFloatOrganization[i] = new char[TEST_NUMBERS + 1];


    // Interchanging row and columns
    for(int j = 0; j < maxlength; ++j){
        for(int i = 0; i < TEST_NUMBERS; ++i){
            cacheFrindlyFloatOrganization[j][i] = fraction[i][j];
        }
    }


    // Debug
    /*
    for(int i = 0; i < maxlength; ++i){
        for(int j = 0; j < TEST_NUMBERS; ++j){
            printf("%c ", cacheFrindlyFloatOrganization[i][j]);
        }
        printf("\n");
    }
    */

    // Sum the fractional array part.
    sumFractions(cacheFrindlyFloatOrganization, maxlength);
}




// Does ALMOST the same thing for decimal function code.
void sumFractions(char **cacheFrindlyFloatOrganization, int maxlength){

    char *resultFraction = new char[maxlength + 1];

    int z = 0, carry = 0;

    for( int i = maxlength - 1; i >= 0; --i ){

        int sum = 0;

        for(int j = 0; j < TEST_NUMBERS; ++j)
            sum = sum +  cacheFrindlyFloatOrganization[i][j] - '0';

        sum = sum + carry;
        resultFraction[z++] = sum % 10 + '0';
        carry = sum / 10;
    }


    // Stored in reversed order
    resultFraction[z] = '\0';


    // Hold the address and length resultFraction array.
    resFrac = resultFraction;
    resFracLen = z;


    // Call the padding function for by sending the carry from fraction part.
    fixPaddingDecimal(carry);
}



// The output decimal and fraction array are in reversed order.
// They need to be reversed before outputting.
void reverseString(char *tmpString, int tmpStringLen){

    for(int i = 0, j = tmpStringLen - 1; i < j; ++i, --j ){
        int temp = tmpString[i];
        tmpString[i] = tmpString[j];
        tmpString[j] = temp;
    }
}



int main(){


    // Comment freopen lines below to input and output from console.
    // In order to use freopen create a file named input_file.txt
    // in same directory as your cpp file. The output of the program
    // will be in output_file.txt file.

    /*
    freopen("input_file.txt", "r", stdin);
    freopen("output_file.txt", "w", stdout);
    */



    for(int i = 0; i < TEST_NUMBERS; ++i){
        //printf("Enter float:\n");
        scanf("%[0-9].%[0-9]", &decimal[i], &fraction[i]);
        getchar();
    }


    // This is where it all starts.
    fixPaddingFraction();



    reverseString(resDec, resDecLen);
    reverseString(resFrac, resFracLen);


    // Debug
    printf("Output: %s.%s\n", resDec, resFrac );



    return 0;
}
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s