Working With Number – Infinity Adding – Beyond Integer – Python

When working with numbers inside any programming language, the biggest challenge a programmer can face is that we are limited to how much digits we can use for a mathematical equation. This mostly due to the architecture of how numbers are stored in the computer. Numbers inside the computer are stored in bits, the range of how much bits are used for storing a number can range by different type of programming language.

Since operating system architecture can use up to 64 bits to store one value at the time of this writing. If a programming language utilizes a 64 bits block to store a number, which can be a signed long integer, we can store a number with a value from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. A signed integer type, which can utilize a 32 bits block of binary can store a number ranging from -2,147,483,648 to 2,147,483,647.

With the maximum of 19 digits for a signed long integer, most of us would work with numbers that are below that limit. However, what happens if we are required to work with numbers that are larger than 19 digits? Is there a possible solution for this? This is the Python version of Beyond Integer the first chapter of Infinity Adding in Working With Number. If you take a look at the completed source code at the end of this article, I used a test case of more than 500 digits plus another 500 digits. With the complete source code at the end of this tutorial, it is possible to add a lot more digits beyond the 500 digits I used for the test case.

How To Add Numbers That Are Larger Than What An Integer Can Hold

How can we possibly adding two numbers that the values are larger than what a 64 bits block can store? Without even looking at any procedures at all, the first challenge we have is how are we going to store the numbers? One solution is, we can store the digits in string format. With this method we can expand the storage capability to as much as a string can handle.

That can solve our first problem. Nevertheless, we will face a second challenge and that is, the numbers are now in string format, and computers can’t perform mathematical equations on any number that is stored in a string format. The reason why is when a computer store a decimal number in a string format, it does not store the actual decimal number as an actual decimal or binary value. Computers when storing numbers or characters symbols in string format actually store them in a represent ASCII code. For example, the number seven in ASCII code is actually stored with the equivalent value of 55 in decimal. Thus, we can’t simply add two strings that are full of digits to get the total value.

Nevertheless, we still have a solution, and that is we can convert each digit or more from both string to an integer type. Then we can add them together one digit at a time. For the demonstration of this tutorial, we are adding one digit at a time. First of all let talk about adding two positive numbers together, or adding two negative numbers together. We know that when a positive number add to another positive number, it will increase the value in a positive manner. When adding two negative numbers together, it will increase the value in the negative direction.

There are other procedures we have to give consideration to. One of them is we have to keep track of the equation’s carry-over value, which is when two single digits add together and the equation produces a value that is beyond a single digit. With the carry-over value, we will have to add that carry-over value to the next set of digits in our equation. Other things we have to give consideration to is we are working with numbers from the right side of the strings to the left side of the strings. We have to also prepare for the event of which when one string run out of digit before the other. Nevertheless, let look at the formula for adding one single digit at a time.

Formula: 
                          (A,B) = positive Or (A,B) = negative

Step 1: Treat all digits in both strings as if they are all positive.
Step 2: From right to left of both string.
Step 3: Add a digit from string A to string B.
Step 4: If the result is higher than nine. Keep the single rightmost digit in the result value as the result value of that position.  
Note: Another method for this is to take a value of 10 and subtract from the result value to get the rightmost digit.
      For example, 9 + 9 = 18. If we were to take 18 - 10 then we would get the rightmost digit. If there is a carry-over value, the carry-over value would be a constant value of one.

Step 5: Any digits before the rightmost digit of the result value are carry-over value. This will always be a value of one in the event where we are only adding two sets of digits together per calculation.
Step 6: Record the single digit result value to an output string starting from right to left. Keep track of the carry-over value.
Step 7: Move to the next digit in the string. If there is any carry-over value then add the carry-over value to the result value.
Step 8: If one string runs out of digits before the other. Continue the loop for the string that is still in length, and use a value of zero to substitute the value of the void string.
Step 9: Repeat the steps until both strings run out of digits. When the strings ended, appends the final carry-over value to the left side of the answer string.
Step 10: If A and B are both negative, append a minus sign to the leftmost of the answer string. 

Example 1: Add -3552 to -18       
Step 1: Treat both numbers as positive values.
Step 2:   2 + 8 = 10       |  carry-over = 1  | answer string =      0           
Step 3:   5 + 1 + 1 = 7    |  carry-over = 0  | answer string =     70
Step 4:   5 + 0            |  carry-over = 0  | answer string =    570
Step 5:   3 + 0            |  carry-over = 0  | answer string =   3570
Answer:       Append a negative sign to the front of the string, and we will get -3570 as the answer for the equation.

Example 2:  Add 251 to 749
Step 1:   1 + 9 = 10      | carry-over = 1      | answer string =       0
Step 2:   5 + 4 + 1 = 10  | carry-over = 1      | answer string =      00
Step 3:   2 + 7 + 1 = 10  | carry-over = 1      | answer string =     000
Step 4: Add the carry-over value of one to the left of the answer string | answer string =    1000
Answer: Since both A and B are positive in value, we do not need to add any signs to the result value, the answer for 251 + 749 is 1000.

This formula is basically the converted mathematical formula for addition of which all of us learned in school. Let convert the above formula into programming procedure call for Python.

With the formula above in perspective, the first procedure we have to make is to evaluate whether if A or B is negative or positive in value. Since we are treating both strings as positive numbers while executing the equation, and we are adding the strings of digits together and they are not an actual integer type, we have to remove any plus or minus sign from the strings. We would also want to remove leading zeroes after the negative or the positive sign. This is because leading zeroes before the decimal do not alter the value of a number. Let’s imagine that we stored all the digits for both numbers in a variable name A, and in a variable name B. This is the code block for our first procedure.

Note that we can also use a boolean value for isaNeg or isbNeg. However, I just want to demonstrate another method for storing a digit value as a true or false value.

isaNeg = 1 if a[0] == "-" else 0
isbNeg = 1 if b[0] == "-" else  0

a = a.lstrip("+-")
b = b.lstrip("+-")
a = a.lstrip("0")
b = b.lstrip("0")

When we are dealings with a loop where one string has the possibility to be shorter than the other string and we do not know which string is the longer or the shorter in length. What can we rely on? In most cases, we can measure their lengths, and with the length, we can initialize a conditional statement of which can evaluate and utilizes the longer string’s length as the index counts for our continues loop run. However, that means we would have to mirror our code. Another method is we can keep track of the position of where we are reading from for both strings in our continues loop. If we reach the ending position for one string then we would not read from that string but the loop would still continue for the string that is still in length. The loop will only stop if we reach the ending position for both strings.

First, we have to declare variables that hold the positions that we are going to read from for both strings. Since we will start at the end of the strings, the first position would be the total length of the string minus one. Besides that, we would have to declare a variable that can store our total result value. Another variable would be needed for storing the carry-over value for each addition procedure. Third, we would need to store the result value from the addition procedure of a single digit adding to a single digit on a temporary placeholder. We would also need two variables that we are going to use as a temporary placeholder for the digits that we are going to obtain from A and B string. This code block below shows the variables that we are going to use.

aidx = len(a) - 1
bidx = len(b) - 1
x = 0
y = 0
carryOver = 0
temp = 0
output = ""

As in the above description, our while loop will run until our read position for both our strings are below zero. Every time the loop run, the script will try to grab a digit from both strings in the event where both their position is not below zero. If one of the read position for a string is below zero, the script will not read from that position and would only read from the string that is still in length.

Each time we read from a position in a string, we would convert the digit in that position to an integer value. Then we would add them together. After adding them together and if the value of the result is larger than nine, we would assign one to the carry-over value. For an addition equation, if we are only adding two sets of digits together at a time, the carry-over value can never be more than a value of one. If the result value is below a value of ten then we would assign the carry-over value with a value of zero.

After the previous procedures, we then convert the result value to string format and assign the first rightmost digit to our answer string. To get the first rightmost digit from the result value, we can subtract the result value to a value of ten in the event where the result value is larger than nine. This method is a practical solution for an addition operation, and only applicable to addition operations that involve adding only two sets of digits at a time.

When both our strings reach the zero position, we would evaluate whether if we have any carry-over value from the previous equation. If we do have a carry-over value then we would convert the carry-over value to string format and assign the carry-over value to the front of our output string. At the end of every loop, we minus a value of one from the read position for both our A and B string’s indexers.

After the loop executed and we have gotten the total result value, we would first need to trim off any leading zeroes. After that, we would then return the output bases on a condition. If both A and B string were negative in value, we append a negative sign in front of the output string.

if (isaNeg == isbNeg):
    while (aidx > -1 or bidx > -1):
        x = int(a[aidx]) if aidx > -1 else 0
        y = int(b[bidx]) if bidx > -1 else 0
        temp = x + y + carryOver
        carryOver = 1 if temp > 9 else 0
        temp = temp - 10 if temp > 9 else temp
        output = str(temp) + output
        output = str(carryOver) + output if (aidx < 1 and bidx < 1) else output
        aidx = aidx - 1
        bidx = bidx - 1
    output = output.lstrip("0")
    output = "0" if len(output) < 1 else output
    return "-" + output if (isaNeg == 1 and isbNeg == 1) else output

The above is for adding a positive number to a positive number, or a negative number to a negative number. In the event where one number is a negative number and the other is positive in value or one number is negative in value and the other is a positive number, how are we going to handle this procedure? In context, if we are adding a positive number to a negative number then we are simply reducing the value of that positive number toward the negative direction. The same previous principle is applied in the event where we are adding a negative number to a positive number. The equation would reduce the value of that negative number toward the positive direction. With that context in mind let first look at the formula.

                          A = positive And B = negative Or A = negative and B = positive.
Pre-step 1: Check if A is larger than B or is B larger than A, or is both strings are equal in value.
Pre-step 2: Check string length first. The string with larger length would also be the one with the larger value.
Pre-step 3: If both strings are the same in length the compare each digit from both strings starting from left to right.
Pre-step 4: The string that is found with the higher value first is the largest one.
Pre-step 5: If the digits are equal at every position of both strings, then they are equal in value.
End Step: If both A and B are equal in value then we would return a value of zero as the result value.

A > B:  From right to left of both string.
Step-1:  Minus a single digit from A to B.
Step-2:  If the result is a positive value or a value of zero then keep the digit. 
Step-3:  If the result is a negative value. Take a value of ten and add to the result value. Also, assign one to the carry-over value.
Step-4:  Record the result digit in an output string starting from right to left.
Step-5:  Move to the next number. If there is any carry-over value then minus the result value to the carry-over value.
Step-6:  If string B run out of digits before string A. Minus A to a value of zero, and then to any carry-over value if there is.
Step-7:  Repeat until there are no more digits in both strings. Trim off any leading zeroes from the answer string.
Step-8:  If A = negative and B = positive then append a negative sign to the front of the answer string.

A < B:  From right to left of the string.
Step 1:  Minus a single digit from A to B.
Step 2:  If the result value is a negative value or a value of zero, keep the positive version of the value.
Step 3:  If the result value is larger than zero, then subtract a value of ten to the result value, and assign one to the carry-over value.
Step 4:  Record the result digit in an output string starting from right to left.
Step 5:  Move to the next number. If there is any carry-over value then add the result value to the carry-over value.
Step 6:  If string A runs out of digits before string B, use a value of zero and subtract to the value of the digit in B, then add to any carry-over value if there still is.
Step 7:  Repeat until both strings run out of digits. Trim off any leading zeroes in the answer string.
Step 8:  If A = positive and B = negative, append a negative sign to the front of the answer string.


Example 1:     Add 537 to -58 
   Step 1:     7 - 8 = -1     |  10 - 1 = 9  | carry-over = 1  |   answer string =     9
   Step 2:     3 - 5 - 1 = -3 |  10 - 3 = 7  | carry-over = 1  |   answer string =    79
   Step 3:     5 - 1 = 4      |       4      | carry-over = 0  |   answer string =   479
   Step 4:     In this case we do not have to append the a negative sign to the front of the answer string.
   Answer:     537 add to -58 equal to 479. 

Example 2:    Add 37 to -301
   Step 1:    7 - 1 = 6        | 10 - 6 = 4 | carry-over = 1 |  answer string =     4
   Step 2:    3 - 0 + 1 = 4    | 10 - 4 = 6 | carry-over = 1 |  answer string =    64
   Step 3:    0 - 3 + 1 = -2   | -2  =  2   | carry-over = 0 |  answer string =   264
   Step 4:    Since 37 was a positive value and 301 was a negative value and the negative value is larger than the positive value.
              We would append a negative sign to the leftmost of our output string.
   Step 5:    -264 is the result value of 37 add to -301.      

With the above formula in perspective, in our programming procedure, we would first evaluate for whether which string hold the larger number, or are they both equal in value. If we found that they are equal in value then we would return the answer of “0” and end the program.

As you can see in the code block below, we are checking on the length first. If A and B are equal in length, then we would compare if the same position digit from both strings is larger than one another. The evaluation of each digit from both strings would start from the right and process toward the left of the strings. If one digit is larger than the other, we would assign the name of the string that has the larger value as our larger variable’s value.

If we found the larger digit, we increase index for our loop count to its maximum value which would be the strings’ length, the loop would then completed. If we reached the ending of both string without finding a larger value, then we assign a “0” value to the larger variable and return its value.

larger = "a" if (len(a) > len(b)) else ( "b" if (len(b) > len(a)) else "1")
if (larger is "1"):
    larger = ""
    for i in range(0, len(a)):
        larger = "a" if (int(a[i]) > int(b[i])) else larger
        larger = "b" if (int(b[i]) > int(a[i])) else larger
        larger = "0" if (i == len(a) - 1 and len(larger) < 1) else larger
        if (len(larger) > 0):
            break
if (larger is "0"):
    return larger

With this code block below, if string A is larger, the program would execute the loop until its reach the zero position in string A. For every loop run, we would check to see if there is still a position to read from in string B. If both A and B are still in position, we convert a digit from both string A and string B to an integer value. We then subtract the value of the digit that we got from string A to the digit that we got from string B, then to any carry-over value. If we already passed the zero position in B string. We do not read from B string, instead, we would substitute a value of zero in lieu of string B’s digit.

When it comes to the carry-over value for any given loop, we would check our result value. If the result value is less than zero then we assign a value of one to the carry-over value. If the result value is zero or larger then we assign a value of zero to the carry-over value.

For the result value, if our result value is a negative value, we would take a value of ten and add to the result value. After that, we append the result value in string format to our output string, starting from right to left. We also have to minus one from our index counts after each loop cycle. Once the while loop is completed, we return the output string bases on one condition. If A is negative in value, we assign a negative sign to the front of the output string.

   
elif (larger is "a"):
    while (aidx > -1):
        x = int(a[aidx])
        y = int(b[bidx]) if bidx > -1 else 0
        temp = x - y - carryOver
        carryOver = 1 if temp < 0 else 0
        temp = 10 + temp if temp < 0 else temp
        output = str(temp) + output
        aidx = aidx - 1
        bidx = bidx - 1
    output = output.lstrip("0")
    return "-" + output if (isaNeg == 1) else output

In the event where string B is larger than string A in value then we would use string B’s length as the position index count for the while loop. For every loop run, we check to see if there is still a position left to read from string A. If both A and B are still in position, we convert a digit from both string A and string B to an integer value. We then minus the digit that we got from A to the digit that we got from B. Then we add the result of the previous equation to any carry-over value. If we had already passed the zero position in A string, we do not read from A string but would substitute a value of zero in lieu of A string’s digit.

To assign a carry-over value for any given loop, we have to evaluate our result value. If the result value is larger than zero then we would assign a value of one as the carry-over value. If the result value is not larger than zero then we would assign a value of zero to the carry-over value.

For the result value, if our result value is a positive value, we would take a value of ten and subtract to the result value. If the result value is a negative value, we would convert the result value into a positive value. After that, we append the result value in string format to our output string, starting from right to left. We also have to subtract one from our index counts after each loop. Once the while loop is completed, we return the output value bases on one condition. If A is positive in value, we append a negative sign to the front of the output string.

elif (larger is "b"):
    while (bidx > -1):
        x = int(a[aidx]) if aidx > -1 else 0
        y = int(b[bidx])
        temp = x - y + carryOver
        carryOver = 1 if temp > 0 else 0
        temp = 10 - temp if temp > 0 else (temp - temp - temp)
        output = str(temp) + output
        aidx = aidx - 1
        bidx = bidx - 1
    output = output.lstrip("0")
    return "-" + output if (isaNeg == 0) else output  

This below is the full function of this tutorial.

Advertisement

# "Copyright Notice", please do not remove.
# Written by Kevin Ng
# The full tutorial on this subject can be found @ http://kevinhng86.iblog.website or http://programming.world.edu.
# Release date to http://programming.world.edu will lag one week after release on http://kevinhng86.iblog.website
# This source code file is a part of Kevin Ng's Z library.
# This source code is licenses under CCDL-1.0  A copy of CDDL1.0 can be found at https://opensource.org/licenses/CDDL-1.0
# End "Copyright Notice"

# Notice: This is version 1 of infiA from Kevin Ng's LibZ library.
#         This is not a production version and is a prototype.
#         This version has been tested, but would be too slow in a production environment.
#         This version of infiA support mathematical addition without the decimal.


class libZ:
    def infiA(self, a, b):
        isaNeg = 1 if a[0] is "-" else 0
        isbNeg = 1 if b[0] is "-" else 0
        a = a.lstrip("+-")
        b = b.lstrip("+-")
        a = a.lstrip("0")
        b = b.lstrip("0")

        aidx = len(a) - 1
        bidx = len(b) - 1
        x = 0
        y = 0
        carryOver = 0
        temp = 0
        output = ""

        if (isaNeg == isbNeg):
            while (aidx > -1 or bidx > -1):
                x = int(a[aidx]) if aidx > -1 else 0
                y = int(b[bidx]) if bidx > -1 else 0
                temp = x + y + carryOver
                carryOver = 1 if temp > 9 else 0
                temp = temp - 10 if temp > 9 else temp
                output = str(temp) + output
                output = str(carryOver) + output if (aidx < 1 and bidx < 1) else output
                aidx = aidx - 1
                bidx = bidx - 1
            output = output.lstrip("0")
            output = "0" if len(output) < 1 else output
            return "-" + output if (isaNeg == 1 and isbNeg == 1) else output

        elif (isaNeg != isbNeg):
            larger = "a" if (len(a) > len(b)) else ( "b" if (len(b) > len(a)) else "1")
            if (larger is "1"):
                larger = ""
                for i in range(0, len(a)):
                    larger = "a" if (int(a[i]) > int(b[i])) else larger
                    larger = "b" if (int(b[i]) > int(a[i])) else larger
                    larger = "0" if (i == len(a) - 1 and len(larger) < 1) else larger
                    if (len(larger) > 0):
                        break
            if (larger is "0"):
                return larger
            elif (larger is "a"):
                while (aidx > -1):
                    x = int(a[aidx])
                    y = int(b[bidx]) if bidx > -1 else 0
                    temp = x - y - carryOver
                    carryOver = 1 if temp < 0 else 0
                    temp = 10 + temp if temp < 0 else temp
                    output = str(temp) + output
                    aidx = aidx - 1
                    bidx = bidx - 1
                output = output.lstrip("0")
                return "-" + output if (isaNeg == 1) else output

            elif (larger is "b"):
                while (bidx > -1):
                    x = int(a[aidx]) if aidx > -1 else 0
                    y = int(b[bidx])
                    temp = x - y + carryOver
                    carryOver = 1 if temp > 0 else 0
                    temp = 10 - temp if temp > 0 else (temp - temp - temp)
                    output = str(temp) + output
                    aidx = aidx - 1
                    bidx = bidx - 1
                output = output.lstrip("0")
                return "-" + output if (isaNeg == 0) else output

# Test case
c = "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
d = "999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999"
print(libZ().infiA(c,d))

Digiprove sealCopyright secured by Digiprove © 2017

This post was written by Kevin and was first post @ http://kevinhng86.iblog.website.
Original Post Name: "Working With Number – Infinity Adding – Beyond Integer – Python".
Original Post Link: http://kevinhng86.iblog.website/2017/02/01/working-with-number-infinity-adding-beyond-integer-python/.

Advertisement


Random Article You May Like

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*