Working With Number – Infinity Multiplication – Beyond Integer – Perl

When we are 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 equations on the numbers. This is due to the architecture of how computers store an integer value.

Operating systems’ architecture can use up to 64 bits to store one integer value at the time of this writing. If a programming language utilizes a full 64 bits block to store a number, which can either be a signed or an unsigned long integer. If it is 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 value that only utilizes a 32 bits block of binary can only store a number with a value ranging from -2,147,483,648 to 2,147,483,647.

When we are storing numbers as an integer type and if we utilized a mathematical equation on the numbers to produce a result value, and in the event where the result value somehow became larger than the largest value that an integer type can hold. Then the result value of the equation would most likely to not be the correct answer. Depending on the environment that we are working in, the computer might simply produce a value of zero as the result values for equations that happen to produce a result value that is larger than the largest value that an integer type can hold. In another scenario, the computer can also reset the bits block every time the value passed the maximum value that an integer type can hold. Thus, a supposed to be positive result value may become a negative result value or vice versa. This type of event where computers produce erroneous results due to values that are larger than what an integer type can hold is usually called an integer overflow problem.

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

This is the first chapter of Infinity Multiplication, Beyond Integer. This article is the Perl version of this chapter. In this chapter, I will discuss in regard to how to process a multiplication equation that involves large numbers that are stored in string format by processing the equation at the rate of one digit at a time.

Please take note that the programming example of this article is an actual program that is called infiX. The version of infiX that is attached to this article is version one. Version one and two of infiX is not meant for a production environment. Version one and two of infiX were modeled to demonstrate the procedures of how to apply a multiplication equation on large numbers. Although these versions of infiX are not the production environment version, they ran through 300,000+ test cases without producing any errors. Nonetheless, they are not efficient if to run in a production environment. If you need the production version of infiX, 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 face for multiplying two large numbers together is storing the numbers, and the second challenge is storing the result value for the equation. For a multiplication equation, the numbers of the equation, themselves, do not need to be very close to the maximum value of what an integer can hold to produce a result value that is beyond the capability of what an integer can hold. One method for solving this issue is to store the digits of the numbers as string type format. Storing digits as string format is one method that can solve the problem of storing a number that is larger than what an integer type can hold.

When numbers are stored as string format, computers can’t generally directly apply a mathematical equation on the numbers without a conversion. This is because when we stored any numbers as string format, they are stored as ASCII code and are not the actual decimal value, or a binary value that represents that decimal value. Also, if the numbers are larger than what an integer type can hold then we can’t simply convert the entire string of digits back to an integer type to apply a mathematical equation on the strings. Nonetheless, we can operate on the strings at the rate of one digit at a time.

Another challenge we can face for a multiplication equation is in regard to the positive and the negative value. In a multiplication equation, a negative value multiply by a negative value will always produce a positive result value. It is same when a positive value is multiplied by a positive value. The only scenario where the result value can be a negative value is when two numbers that are involved in the equation are not the same in the negative or the positive base.

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

Multiplication itself can also be described as an equation that will give back the first value in the sum of itself by an amount of times that is defined by the second value as a result value. Since computers’ architecture support multiplication calculation on integer values as a natively supported feature, if we were to apply an addition equation instead of utilizing the natively supported multiplication feature then we can face efficiency issues. Therefore, in my opinion, for programming, multiplying the digits of the first number to the digits of the second number would always be more efficient than to apply an addition formula on the first number by an amount of times bases on the value of the second number. Let first inspect the formula for multiplying two numbers to each other at the rate of one digit at a time.

Formula:
Step 1: Evaluate for whether if either A or B is zero in value. If either A or B is a value of zero then return a value of zero as an answer.
Step 2: Evaluate for whether if either A or B is a value of one. If A is a value of one then return B as the answer. If B is a value of one then return A as the answer.
Step 3: Evaluate for whether if A and B is negative or positive in value.
Step 4: Multiply each digit in A to the first digit in B. Starting from right to left for both A and B.
Step 5: For each instance of multiplication.
        If there is any carry-over value from the previous equation then add the carry-over value to the result value.
        If the result value is larger than nine. 
        Keep the rightmost digit of the result value.
        Anything that is to the left of the rightmost digit is the carry-over value.

Step 6: Store the result in a temporary answer string starting from right to left.
Step 7: Once all the digits in A multiplied to the first digit of B.
        If there is any carry-over value then add the carry-over value to the beginning of the temporary answer string.
Step 8:	Assign the value of the temporary answer string to the main answer string.

Step 9: Multiply each digit from A to the second digit in B.
Step 10: Each instance of multiplication is exactly similar to step four above.
Step 11: Store the result value 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 is any carry-over value then add the carry-over value to the beginning of the temporary answer string.
Step 13: Starting at the second position from the right of the main answer string.
         The starting position will change to the third position when the equation is at the third digit in B.
         The starting position will change to the fourth position when the equation come to the fourth position in B. This pattern will continue to the final digit in B.
         
         Starting from right to left, add each digit from the temporary answer string to the main answer string at the rate of one at a time.
         Keep track of and apply the carry-over value for each addition procedure.
         At the ending of the addition equation, if there is any carry-over value then append the carry-over value to the beginning of the answer string.
*Note: More reference in regard to adding two numbers together at the rate of one digit at a time can be found by reading the Infinity Adding chapter of Working With Number.   

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 and B are not the same in the nagative or the positive base then append a negative sign to the front of the main answer string. 

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

Step 5: 7 * 8 = 56           | carry-over = 5     | temporary answer string =     6                                                          
Step 6: 8 * 8 = 64 + 5 = 69  | carry-over = 6     | temporary answer string =    96  
Step 7: 5 * 8 = 40 + 6 = 46  | carry-over = 4     | temporary answer string =   696
Step 8:     carry-over = 4 to temporary 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           | carry-over = 2     | temporary answer string =     8
Step 11: 8 * 4 = 32 + 2 = 34  | carry-over = 3     | temporary answer string =    48
Step 12: 5 * 4 = 20 + 3 = 23  | carry-over = 2     | temporary answer string =   348
Step 13:     carry-over = 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 is 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 both strings for whether if they are negative or positive in value. Besides evaluating the negative or the positive value base, we also have to correct simple input mistakes. One of the possibilities of an input mistake is the user added an extra plus or minus sign. Another possibility is the input having leading zeroes after the negative or the positive sign. Leading zeroes that are before the decimal in decimal numbers do not offer any additional value to the actual value.

With the above perspective, in Perl, we can use the code block below to evaluate the negative or the positive base of both A and B. Then we would remove any negative and positive sign from the left side of the string. After removing all the plus and minus sign, if there are any leading zeroes, we would remove all the leading zeroes.

Take note that isaNeg and isbNeg can be a boolean type of true or false. Nonetheless, I just want to demonstrate another method for storing the result of a conditional statement as numbers instead of a true or false value.

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 the above steps, we can apply the shortcuts for a multiplication equation. The first shortcut is if any number multiplied by zero or zero multiplied by any number then the equation will produce a value of zero as an answer. Since we removed any leading zero from both string A and B. If zero was the only digit in any string then the string that contained only the value of zero would also be empty. Thus, if either string A or B is empty or in others word is with a length that is less than one, then we would return a value of zero as a result value.

The other shortcut for dealing with a multiplication equation is multiplying a number to a value of one. When a number is multiplied by one or vice-versa then that number is the answer to the equation. For this procedure, we can evaluate to check whether if A or B only contains a lone one as a digit. If string A only contained a lone digit that is a one then we return string B as the answer. If string B only contains a one then we return string A as the answer. The result value that we are returning is based on one condition, if A string and B string are different in the positive and the negative base then we append a negative sign to our result 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 and the shortcuts, we can then apply the multiplication procedures on our input values. With the multiplication formula in context, for each multiplication, we know that we are multiplying all the digits of A string to one digit in B string, and the equation will process until we had multiplied all the digits of A to all the digits of B. After each time that we had multiplied all the digits in A string to a digit in B string, we have to add the result value of the equation to our output string before we can move onto the next digit in B string. As the same time as we are moving from right to left of the digits in B string, we are also moving from right to left of the position of where we would add the first rightmost digit of the multiplication’s result value to the output string.

In a programming context, we would require two loops to execute and one loop is nested within the other. The outer loop will read each digit in B string from right to left and will stop executing after the loop reaches the zero position in B string. For each time the outer loop is executed, the inner loop will execute all its cycle. For each inner loop execution, the loop will process one digit at a time from string A, and also, from right to left. The inner loop will stop executing when the last digit in A string is read. For our loops, we would have two indexers, one is for our outer loop and the other one is for the inner loop. The indexer for the outer loop starts with a value that is one value less than B string’s length and will decrease by one value each time the outer loop is executed. The indexer for the inner loop starts with a value that is one value less than the length of A string and will decrease by one value each time the inner loop is executed. The outer loop’s indexer’s value is the position of the digit that we are processing in B string, and the inner loop’s indexer’s value is the position of the digit that we are currently working on in A string.

When the outer loop is executed, we would first convert the digit of that position in B string to an integer type. By converting and assigning the digit to a variable, we do not have to convert the digit for every equation between the digit of B to all the digit of A. When the inner loop is executed, we also convert a digit from the current position of string A to an integer type. Then we 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 one the inner loop finishes executing and before we move onto the next execution of the outer loop. Thus, the complete answer for our inner loop execution will be stored in a temporary answer string.

Besides the procedures, we also have to keep track of the carry-over value. For a multiplication equation that is processing at the rate of one digit at a time then the leftmost digit of the result value is the carry-over value. The rightmost digit of the result value is to be kept as the result value for the equation. We only have to assign a value to the carry-over value if the result value is larger than nine. For anything else that is below nine, a value of zero is assigned to the carry-over value. The carry-over value is to be added to the result value of the multiplication equation of the next digit.

For each inner loop execution, we stored the result value from our multiplication equation to our temporary answer string starting from right to left. Once the inner loop executed all its cycles, we append the final carry-over value in string format to the leftmost of our temporary answer string. This code block below demonstrates the mentioned procedures.

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 + $carryOverM;
          $carryOverM = ($temp > 9)? int(substr($temp,0,-1)) : 0;
    	  $outtemp = substr($temp, -1) . $outtemp;
          $aidx--;
     }          
$outtemp = ($carryOverM > 0)? $carryOverM . $outtemp : $outtemp;

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

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

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

When adding our temporary answer string’s value to our output string’s value, for each equation, we have to keep track of the position of where we are going to first read the digit from the output string. 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 starting position for when we are processing the digit from the output string is defined with the name outposition.

We will use the length of our temporary answer string as an index for our loop. Each time the loop is executed, we will read a digit 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 value, then we minus to a count of how many times the current loop had been executed. In Perl, the starting position of a string is the zero position. Thus, we also have to subtract a value of one from the total length of the output string for the above procedure to be able to get the correct position.

For each equation, we also keep track of the carry-over value, then we would apply the carry-over value to the equation of the next digit. If the result value from the equation is larger than nine then the carry-over value will be set to a value of one and the rightmost digit from the result value is then added to the temporary addition string. After the loop is executed, we then append any carry-over value to the leftmost of our temporary addition 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 + $carryOverA;
     $carryOverA = ($tempadd > 9)? 1 : 0;
     $tempaddstr = substr($tempadd, -1) . $tempaddstr;
     $outidx = $outidx + 1;
}
$tempaddstr = ($carryOverA > 0) ? $carryOverA . $tempaddstr : $tempaddstr;

After producing a result string by adding the multiplication’s temporary answer string to our output string, we then assign the result string as the output string’s value. To assign the result string to the output string, we keep the digits on the right of the starting position in the output string and append the addition’s result to the left of the digits that we kept in the output string. The starting position in the output string is the length of the output string subtract to the value of the outposition variable. To get the first digit that is on the right of the starting position, we add a value of one to the starting position’s value.

After the above procedures, we then reset the temporary answer string’s variable to an empty value and increase the count for our outposition variable to prepare for the next execution of the outer loop. Of which will read the next digit in B string. This code block below is written in Perl to demonstrate the procedures.

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

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

Advertisement

# 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, and does not support the decimal.
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 $carryOverM = 0;
            my $outtemp = "";
            my $aidx = $alen - 1;

            while ($aidx > -1){
                $temp = int(substr($a,$aidx,1)) * $z + $carryOverM;
                $carryOverM = ($temp > 9)? int(substr($temp,0,-1)) : 0;
                $outtemp = substr($temp, -1) . $outtemp;         
                $aidx--;
            }          
            $outtemp = ($carryOverM > 0)? $carryOverM . $outtemp : $outtemp;
        
            if (length($output) < 1){
                $output = $outtemp;
                $outtemp = "";
                $outposition = $outposition + 1;
            } else {
                my $tempadd = 0;
                my $carryOverA = 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 + $carryOverA;
                    $carryOverA = ($tempadd > 9)? 1 : 0;
                    $tempaddstr = substr($tempadd, -1) . $tempaddstr;
                    $outidx = $outidx + 1;
                }

                $tempaddstr = ($carryOverA > 0) ? $carryOverA . $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);

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 Multiplication – Beyond Integer – Perl".
Original Post Link: http://kevinhng86.iblog.website/2017/02/11/working-with-number-infinity-multiplication-beyond-integer-perl/.

Advertisement


Random Article You May Like

Leave a Reply

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

*
*