Home » Perl » Perl – Infinity Multiplication – Beyond Integer

When working with numbers inside the computer and the numbers happened to be longer than ten digits in length and if we are treating the numbers as an integer type, we might face challenges for storing and utilize mathematical equation on the numbers. This is due to the architecture of how computers store an integer value.

Operating systems’ architecture can use up to 64 bit to store one integer 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 or unsigned long integer. If it is a signed long integer, we can store a number value from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. A signed integer type which utilizes 32 bits block of binary can store a number ranging from -2,147,483,648 to 2,147,483,647.

When we stored numbers as an integer type and utilized a mathematical equation on the numbers to produce a result and if the result becomes larger than what an integer can hold, the result may not be the correct answer. Depend on the environment we are working in, the computer might simply produce a zero value for the result or the computer can reset the bits block every time the count is higher than what an integer can hold. Thus a positive result may become a negative result or vice versa.

When dealing with multiplication, our numbers can be as short as ten digits in length to produce a result value that is bigger than the value of what a 64 bits block integer can hold. If we were going to work with numbers that are very large in our programming procedure, how are we going to stores and operates mathematical equation on the values?

This is the first chapter of Infinity Multiplication, Beyond Integer and was written for Perl. In this chapter, I will discuss in regard to how to operate with large numbers directly on a string by multiply one digit at a time.

Notice: The programming example of infinity adding, subtracting, multiplication and division are not meant for a production environment until version three. Version one and two are models to demonstrate the procedure of how large digits can be operated on. The example ran through 300,000+ test cases without producing any errors. However, they are not efficient for a production environment. If you need the production version for the infinity library, please stay tune until chapter three.

Next Chapter: Decimal, Precise Float Calculation

How To Multiply Values That Are Larger Than What An Integer Can Hold

In programming, the first challenge we meet for multiplying two large numbers together is storing the numbers and the result value. For multiplication, the numbers themselves do not need to be very close to the maximum value of what an integer can hold to produce a result that is beyond the capability of what an integer can hold. One method for solving this issue is to store the numbers and their digits in a string type format. Storing digits in string format is one method that can solve the problem of storing a number that is larger than what an integer type data can hold.

When numbers are stored in string format, the computer can’t generally directly apply a mathematical equation on the numbers without a conversion. This is because when any numbers are stored in string format, they are stored as ASCII code and not the actually binary or decimal value that represents the actual number value. Also, we can’t simply convert the entire string of number back to an integer type to apply a mathematical equation on the string. However, we can operate on the string with one number at a time.

Another challenge we can face for multiplication is regard to positive and negative values. In multiplication, a negative value multiply by a negative value will produce a positive result value. A positive value multiply by a positive value will produce a positive result value. The only scenario where the result value can be negative is when two multiplication numbers are different in the negative and positive base.

Besides scenarios, there are also shortcuts that are available for us which doesn’t require us to apply an actual mathematical equation. For example, when anything multiplies by zero or zero multiply by any values, we can produce a zero result value without any mathematical calculation. The second is when any number is multiplied by one or one multiply by any number, we can simply just return the number as the result value.

Multiplication itself can also be described as giving back the first value in sum as a result by the amount of times bases on the second value. Since computer’s architecture allow the usage of multiplication equation on integer as a natively supported function, if we apply addition equation for multiplication we can face efficiency issues. Therefore in my opinion for programming, multiplying the digits in the first value to the digits in the second value is more efficient than applying an addition formula on the first value base on what is defined by the second value. Nevertheless, let first look at the programming formula for multiplication numbers between two values, one digit at a time.

Formula:
Step 1: Check to see if either A or B is zero. If either A or B is zero return zero as an answer.
Step 2: Check to see if either A or B is one. If A is one return B as the answer. If B is one return A as the answer.
Step 3: Check if A and B is negative or positive.
Step 4: Multiply each digit in A string to the first digit in B string. Starting from right to left for both A and B string.
Step 5: For each instance of multiplication.
        If there are any leftover from the previous equation add to the result.
        If the result is larger than nine. 
        Keep the rightmost digit for the result.
        Keep the anything before the rightmost digit for leftover.

Step 6: Store the result in a temporary answer string from starting right to left.
Step 7: Once all the digits in A multiplied to the first digit of B,
        if there are any leftover add to the beginning of the temporary answer string.
Step 8:	Assign the value from the temporary answer string to the answer string.

Step 9: Multiply each digit from A string to the second digit in B string.
Step 10: Each instance of multiplication is same as step four.
Step 11: Store the result in a temporary answer string starting from right to left.
Step 12: Once all the digits in A multiplied to the second digit of B,
         if there are any leftover add to the beginning of the temporary answer string.
Step 13: Starting at the second position from the right of the answer string.
         This position change to third if the digit in B is third,
         change to fourth if the digit in B is fourth and so on.
         
         Add each digit from the temporary answer string to the answer string one at a time.
         Keep track and add remainder for each digit.
         If there is any remainder at the final of the addition equation append to the beginning of the answer string.
*Note: To read about adding one digit at a time please refer to Infinity Adding.        

Step 14. Repeat step 8 to 12 until all the digits in A are multiplied by all the digits in B.
Step 15. If A is negative and B is positive or B is positive and A is negative, append a negative sign to the front of the answer string. 

Example: 587 * 489
Step 1: 7 * 9 = 63           | leftover = 6 | temporary answer string =    3 
Step 2: 8 * 9 = 72 + 6 = 78  | leftover = 7 | temporary answer string =   83
Step 3: 5 * 9 = 45 + 7 = 52  = leftover = 5 | temporary answer string =  283
Step 4:     leftover = 5 to answer string   | temporary answer string = 5283
Step 5: assign temporary to answer string   | answer string : 5283



Step 5: 7 * 8 = 56           | leftover = 5     | temporary answer string =     6                                                          
Step 6: 8 * 8 = 64 + 5 = 69  | leftover = 6     | temporary answer string =    96  
Step 7: 5 * 8 = 40 + 6 = 46  | leftover = 4     | temporary answer string =   696
Step 8:     leftover = 4 to answer string       | temporary answer string =  4696

Step 9: add answer string to temporary string   | answer string    =     5283 +
                                                  temporary string =    4969  
                                                     answer string =    52243                                         
                                                                   
Step 10: 7 * 4 = 28           | leftover = 2     | temporary answer string =     8
Step 11: 8 * 4 = 32 + 2 = 34  | leftover = 3     | temporary answer string =    48
Step 12: 5 * 4 = 20 + 3 = 23  | leftover = 2     | temporary answer string =   348
Step 13:     leftover = 2 to answer string       | temporary answer string =  2348

Step 14: add answer string to temporary string   | answer string    =     52243 +
                                                  temporary string =    2348 
                                                     answer string =    287043                                         

Answer: 587 * 489 = 287043

The formula above are the programming procedures of this article’s method for multiplying two strings of digits together. In this article let assume that we are multiplying two strings of digits together, the first string name is A and the second string name is B. In the formula above, the first step is to evaluate for whether if A or B string is negative. Besides evaluating if A or B string can be a negative value, we also have to correct simple input mistakes in the scenario where the user add an extra plus or minus sign, or having leading zero after the negative or positive sign. Leading zero in decimal number does not offer any additional value to the actual value.

With the above perspective, in Perl, we can use the code block below to evaluate whether A or B is negative, than we remove any negative and positive sign from the left side of the string until we reach a value that is not a plus or minus sign. After removing the plus and minus sign, any leading zero will be removed until the left most of the string is not a leading zero.

my $isaNeg = substr($a,0,1) eq "-"? 1 : 0;
my $isbNeg = substr($b,0,1) eq "-"? 1 : 0;       
$a =~  s/^[+-]+//g ;
$b =~ s/^[+-]+//g;    
$a =~ s/^0+//g;
$b =~  s/^0+//g;  

After evaluating string A and B from the above step we can apply our shortcuts for multiplication. The first shortcut is if any number multiply by zero or zero multiply by any number will produce a zero for an answer. Since we removed any leading zero from both string A and B. If zero was the only digit, the string would also be empty. Thus if either string A or B is empty or in other word is length less than one, we would return a zero result.

The other shortcut for dealing with multiplying is multiplying a number to one or one to a number. One multiply by any number or any number multiply by one will produces the number as the answer. In a programming context, we can evaluate if whether A or B only contain a one as a digit. If A string only contained one digit that is a one we will return B string as the answer. If B string contains only a one, we will return A string as the answer. The result that we are returning is base on one condition, if A string and B string is different in the the positive and negative base, we append a negative sign to our return value. The Perl code block below demonstrate the above procedures.

if (length($a) < 1 || length($b) < 1){
     return "0";
}
if ($a eq "1"){
     return ($isaNeg ne $isbNeg? "-" . $b : $b );
}
if ($b == "1"){
     return ($isaNeg ne $isbNeg? "-" . $a : $a );
}

After evaluating the inputs, we can then apply the multiplication procedure on our input values. With the multiplication formula in context, we know that we are multiplying the entire string of digits from A string to every single digit in B string. After we are multiplying all the digits in A string to a digit in B string, we have to add the result to our output string before we can move on to the next digit in B string. As we move from right to left of the digits in B string, we are also moving from right to left of where to add the multiplication result to our output string.

In a programming context, we would require two loops to execute and one is nested within the other. The outer loop will read each digit in B string from right to left and will stop executing whence the loop reach the zero position in B string. For each time the outer loop is executed, the inner loop will read one digit at a time from A string from right to left, and the loop will stop executing whence the last digit in A string is read.

Whence the outer loop executed, we first convert the digit of that position in B string to an integer type. With this method, we do not have to convert the digit for every equation. When the inner loop executed, we convert a digit from the current position in A string and multiply the digit from A string to B string. The answer string that we get back from executing the entire inner loop would be added to our output string once the inner loop finishes executing and before we move onto the outer loop next execution. Thus the complete answer for our inner loop execution will be stored in a temporary answer string.

We also have to keep track of the leftover due to we are only multiplying and storing one digit at a time. Therefore we can only add a single digit value to our temporary answer string. The digit that we are adding to the temporary answer string from each inner loop execution is always the rightmost digit from the result. The leftover is always the digits before the rightmost digit from the result. We only have to assign values to leftover if the result is larger than nine. For anything else that is below nine, the leftover will be assigned with a zero. The leftover is always be added to the multiplication equation.

For each inner loop execution, we stored the result from our multiplication equation to our temporary answer string starting from right to left. Once the inner loop cycle ended, we append the final leftover value in string format to the left most of our temporary answer string. This code block shows the mentioned procedure for Perl.

for (my $i = $blen - 1; $i > -1; $i--){
     my $z = int(substr($b,$i,1));
   
     while ($aidx > -1){
          $temp = int(substr($a,$aidx,1)) * $z + $leftover;
          $leftover = ($temp > 9)? int(substr($temp,0,-1)) : 0;
    	  $outtemp = substr($temp, -1) . $outtemp;
          $aidx--;
     }          
$outtemp = ($leftover > 0)? $leftover . $outtemp : $outtemp;

After executing the inner loop and if it is the first time the outer loop executed or otherwise our output string doesn’t have any values, we simply assign the temporary answer string to the output string and reset the temporary answer string to an empty value.

if (length($output) < 1){
     $output = $outtemp;
     $outtemp = "";
     $outposition = $outposition + 1;
}

If our output string does contain a value after the inner loop executed, then we have to add the temporary answer string’s result to our output string before the next execution of the outer loop. For adding the result from the temporary answer string to the output string, we will utilize a loop to read and add value in a one digit at a time manner from the temporary answer string to the output string.

When adding our temporary answer string’s result to our output string, we have to keep track of the position of where we are going to first read the digits from in our output string for each equation. To measure this, we keep track of a count of how many times the outer loop had been executed. This will tell us how far we should start from the right of the output string by subtracting the length of the output string to the count. For this article, the count to get the position of where we first read the digit from in our output string is defined with the name outposition.

We will use the length of our temporary answer string as an index for our loop. We will read one digit at a time from the temporary answer string and a digit from the output string and add them together. To get the position of where to read from in our output string we take the length of the output string minus the outposition variable, then we minus to a count of how many times the current loop executed. In Perl, the starting position of a string is the zero position. Thus we have to also minus a one from the total length of the output string to get its first position on the most right.

For each equation, we also keep track of the remainder and apply the remainder to the next equation. If our result is above nine for an equation, the remainder will be set to one and the rightmost digit from the result is then added to a temporary add string. After the loop is executed, we then append any remainder value to the leftmost of our temporary add string. The Perl’s code block below is an example that demonstrates the mentioned procedures.

for (my $idx = length($outtemp) - 1; $idx > -1; $idx--){
     $cposition = ($outlen - $outidx - $outposition);
     $x = int(substr($outtemp,$idx,1));
     $y = ($cposition > -1 )? int(substr($output,$cposition,1)) : 0;
     $tempadd = $x + $y + $remainder;
     $remainder = ($tempadd > 9)? 1 : 0;
     $tempaddstr = substr($tempadd, -1) . $tempaddstr;
     $outidx = $outidx + 1;
}
$tempaddstr = ($remainder > 0) ? $remainder . $tempaddstr : $tempaddstr;

After producing a result string from adding our temporary answer string from the multiplication procedure to our output string, we then assign the result string to our output string. To append the result to the output string, we keep the digits after the starting position in the output string and append the adding result to the left of the digits we kept from the output string.

We then reset the temporary answer string’s variable to empty and increase the count for our outposition variable to prepare for the next execution of the outer loop that will read the next digit in B string. This code block below is written in Perl to demonstrate the procedure.

$output = $tempaddstr . substr($output,  length($output) - $outposition  );
$outtemp = "";
$outposition = $outposition + 1;

The function below is the full operational function code to this article.

# Written by Kevin Ng
# The full tutorial on this subject can be found @ http://kevinhng86.iblog.website 
# This source code file is a part of Kevin Ng Z library.
# To use this source code in your project please give the copyright credit.
# This function only multiply and does not check to see if it is only number in the string, you must build a checker around it.
# Notice: Version one and two of any infinity code from the libZ library are prototype.
#         They are not meant for production environment due to efficentcy.
#         Although are prototype these script were tested and ran through 300,000+ test cases without producing any errors.
#         This is version one of infinity multiplication for Perl.
use strict;

package libZ;

    sub infiX{     
        my ($a, $b) = @_;
        my $isaNeg = substr($a,0,1) eq "-"? 1 : 0;
        my $isbNeg = substr($b,0,1) eq "-"? 1 : 0;       
        $a =~  s/^[+-]+//g ;
        $b =~ s/^[+-]+//g;    
        $a =~ s/^0+//g;
        $b =~  s/^0+//g; 
   
        if (length($a) < 1 || length($b) < 1) {
            return "0";    
        }
        if ($a eq "1"){
            return ($isaNeg ne $isbNeg? "-" . $b : $b);    
        }    
        if ($b == "1"){
            return ($isaNeg ne $isbNeg? "-" . $a : $a);      
        }
    
        my $temp = 0;
        my $outposition = 0;
        my $alen = length($a);
        my $blen = length($b);
        my $output = "";
        for (my $i = $blen - 1; $i > -1; $i--){
            my $z = int(substr($b,$i,1));
            my $leftover = 0;
            my $outtemp = "";
            my $aidx = $alen - 1;

            while ($aidx > -1){
                $temp = int(substr($a,$aidx,1)) * $z + $leftover;
                $leftover = ($temp > 9)? int(substr($temp,0,-1)) : 0;
                $outtemp = substr($temp, -1) . $outtemp;         
                $aidx--;
            }          
            $outtemp = ($leftover > 0)? $leftover . $outtemp : $outtemp;
        
            if (length($output) < 1){
                $output = $outtemp;
                $outtemp = "";
                $outposition = $outposition + 1;
            } else {
                my $tempadd = 0;
                my $remainder = 0;
                my $outlen = length($output) - 1;
                my $outidx = 0;
                my $cposition = 0;
                my $tempaddstr = "";
                my $x = 0;
                my $y = 0;

                for (my $idx = length($outtemp) - 1; $idx > -1; $idx--){
                    $cposition = ($outlen - $outidx - $outposition);
                    $x = int(substr($outtemp,$idx,1));
                    $y = ($cposition > -1 )? int(substr($output,$cposition,1)) : 0;
                    $tempadd = $x + $y + $remainder;
                    $remainder = ($tempadd > 9)? 1 : 0;
                    $tempaddstr = substr($tempadd, -1) . $tempaddstr;
                    $outidx = $outidx + 1;
                }

                $tempaddstr = ($remainder > 0) ? $remainder . $tempaddstr : $tempaddstr;
                $output = $tempaddstr . substr($output,  length($output) - $outposition  );

                $outtemp = "";
                $outposition = $outposition + 1;
            }   
        }
        if ($isaNeg ne $isbNeg){
            $output = "-" . $output;
        }
        return $output;
}


package main;
my $x = "99999999999999999999";
my $y = "-99999999999999999999";

print libZ::infiX($x, $y)

Visit my blog at http://kevinhng86.iblog.website to find all my articles.

Written by: kevinhng86
Published at: programming.world.edu
Permalink: http://programming.world.edu/2017/02/16/perl-infinity-multiplication-beyond-integer/
Skip to toolbar