|
Multiplying Long Numbers
This page deals with multiplying two long numbers. However, very often when we need to
multiply we can multiply by a "small" number and do not have to deal with more
than one long number.
In this script, the numbers are put in arrays. The two arrays containing the big
numbers are multiplied to get the even longer answer. The script deals with multiplying
two positive numbers.
On this page:
An example of the running script is below. Enter two numbers (or use the random
buttons) and click on the button to get the answer.
For instance, I got this:
Answer checks OK
9,924,129.790891545006121103771196924 x
217,772,519,668.5427208139598990367426=
2,161,202,750,080,099,743.8983715933301845735209049155071526355742560997624
Num Digits: 74
js answer=
2161202750080099800
Time: 0.03 seconds
The script first reports that the answer checks out (using casting out nines) and then
presents the multiplication. Then it boasts about the number of digits in the answer, in
the above, 74. Then it computes the product using standard javascript (originally as a
second check) and finally it says how long it took to work out the answer (0.03 seconds).
The actual time may be a bit longer than this because the browser takes a while to draw
the window.
The script begins by defining the number base:
var Base =
10000; // The number base
Using a bigger rather than a smaller base makes the script faster. Instead of working
out each individual digital sum, it can multiply in groups of 4, in the present case,
because the biggest number in each cell of the array will be 9999.
First the script checks the numbers entered to ensure that at most one decimal point
exists, and that no non-numbers have been inputted. It does this using the following
function:
function checkNumMult(aNum) {
var isOK=0;
var aNum=aNum+"";
//if the number has one or none decimal points, lastIndexOf and indexOf
//will give the same answer
if (aNum.lastIndexOf(".")!=aNum.indexOf("."))
isOK=1;
else
//here a regular expression is used to check for numbers and decimals
if (aNum.match(/[^0-9.]/g))
isOK=2;
return isOK;
} //end of checkNumMult(aNum)
If there is an error in the numbers, the script says why and tells the user which
number has the problem.
The above function is used in the code like this:
if
(checkNumMult(x)>0)
{
switch
(checkNumMult(x)) {
case 1:
alert( "Too many decimal points
in number 1.")
break
case 2:
alert( "Some characters aren't
numbers in number 1");
break
} //end of switch
} //end of check number 1
if
(checkNumMult(y)>0)
{
switch
(checkNumMult(y)) {
case 1:
alert( "Too many decimal points
in number 2.")
break
case 2:
alert( "Some characters aren't
numbers in number 2");
break
} //end of switch
} //end of check number 1
} //end number problem
else //number checks out
{
Because the function returns 0, if everything is OK, 1 for a decimal problem and 2 for
a non-number problem the code can tell the user the kind of problem it found, and also
where the problem occurred (number 1 or number 2).
If the numbers check out, the code runs after the else above.
The following are the variables set at the beginning, with comments:
t1= new Date(); //used to
calculate start time
aX= new
Array(); //holds number x
aY= new
Array(); //holds number y
aW= new
Array(); //holds the product, x*y
n1=removeCommas(n1); //clean up n1
and n2
n2=removeCommas(n2);
x=n1; //set x and y values
y=n2;
Further variables are set as follows (getDec was used in the subtraction
page):
numlen=x.length+y.length;
decXo=getDec(x);
//set original decimal position in
x and in y
decYo=getDec(y);
decX=decXo; //also set the current
holder of the decimal place
decY=decYo;
//remove decimal from x, using plain
javascript.
x=x.replace( ".","");
//remove decimal from y
y=y.replace( ".","");
//initialise decPlace, which is the number of decimals in
//the number with the most decimals
//First just assume x is the number with most decimal places
//If decX isn't longer than decY, then the following will be true
var decPlace=decX;
What we want to do is to make the
numbers into integers, multiply them and then put the decimal points back into the
numbers. The next bit of the code puts in any trailing zeros which might be needed to
correct the numbers.
//Then check which is the correct number
if (decX>decY)
{
decPlace=decX;
//Then check which is the correct number
if (decX>decY)
{
decPlace=decX;
//add zeros to y
//the number of zeros is just the difference between the number of
//decimal places in each number.
//decYo is the number of decimals in the original y number.
for (var i=0;i<(decPlace-decYo);i++)
{
//add a zero at the end
y+= "0";
//increment decY, so we keep a record of the decimal position
//in the new number. For instance
// if decYo=2, as in 1.12, then the number is really 112/10^2
//When we add zeros, the position becomes one more
//for each zero we add .. 1.120, decimal is now 3 from the end, or
//the number is really 1120/10^3
//increment decY
decY+=1;
}
}
//add zeros to x, if y has more decimals
//repeat of the above
else
if (decY>decX)
{
decPlace=decY;
//add zeros to x
for (var i=0;i<(decPlace-decXo);i++)
{
x+= "0";
decX+=1;
}
}
//otherwise, decPlace is as above
Because we add zeros, the decimal position will change, so we need to increment one or
the other of decX and decY, so we know where to put the decimals in the numbers after
multiplying.
The numbers enter the main function as strings from the form on the page. We need to
put them into the arrays. First we do this:
xlen=x.length;
ylen=y.length;
cellSize=getLength(Base);
maxSize=Math.ceil(getLength(x)/cellSize)+Math.ceil(getLength(y)/cellSize);
We record the lengths of the strings and compute the cellSize. The cellSize is computed
with:
function getLength(num) {
return
Math.ceil(Math.log(num)/Math.LN10);
} //end of getLength(num)
The cellSize is the number of digits in each cell. We can say straight away when we
know the Base is 10, that each cell holds one digit, and when the Base is 100, it holds 2.
But the computer cannot do this easily, so it needs to do a calculation. The length of a
number is the log to base 10 of that number. And this is what the function getLength
calculates. As the logs in javascript are natural logs, we need to divide the two logs to
get the base 10 logarithm.
The following code builds two arrays containing the two numbers as we want them:
//the length of the array (sum of all
digits)
//a product cannot have more than
this number of digits, but might have one less
//so the sum of the digits in the
multiplier and multiplicand is greater than
//or equal to the sum of those in
the product.
sumDig=x.length+y.length;
slice=Math.ceil(sumDig/cellSize);
//make an array:
for (i=0;i<=slice;i++)
aX[i]= null; //this avoids lots of zeros in the
answer
for (i=0;i<=slice;i++)
aY[i]= null;
for (i=0;i<=2*slice;i++)
aW[i]= null;
//slice is the number of itesm in the array. Each item or cell has
cellSize digits
//put the number into the array
for (i=0;i<slice;i++)
{
//we need to fill the array with the right-most numbers at the right of
the array
aX[slice-i-1]=(x.substring(x.length-cellSize*(i+1),x.length-
cellSize*(i)));
aY[slice-i-1]=(y.substring(y.length-cellSize*(i+1),y.length-
cellSize*(i)));
}
The arrays, aX and aY, now contain the numbers we want to multiply. And all that
remains is...
The multiplication uses junior school long multiplication adapted for the computer, and
for javascript in particular.
The code is:
//carry is zero at the start
carry=0;
//slice is the length of the array
for
(i=slice-1; i>=0; i--) {
//multiply numbers
for
(j=slice-1;j>=0;j--)
{
//prod is the product of the two
digits
prod= aX[i]*aY[j];
//add any carry from previous
prod += carry;
//deal with any new carry
if
(prod>=Base) {
carry =Math.floor( prod/Base);
prod -= (carry*Base);
}
else
carry = 0;
aW[i+j]+= prod;
if
(aW[i+j]>=Base)
{
rem=Math.floor(aW[i+j]/Base)
aW[i+j]-=rem*Base;
carry+=rem;
}
if
(aW[i+j]>Base)
{
aW[i+j-1]+=Math.floor(aW[i+j]/Base);
aW[i+j]=aW[i+j]%Base;
}
}//end of for j
} //end of for i
We have now multiplied the two long numbers and the answer lurks in the array aW.
We now write the answer into the string, z. Here we try to avoid writing out empty
cells (which should be null) and to ensure that each cell contains the right number of
digits, padding it with leading zeros, as necessary:
z= "";
for
(k=0;k<aW.length;k++)
if (aW[k]!=null) //we kept the nulls!
{
if (
(
(aW[k]+ "").length==cellSize)||
(k>aW.length-2)
)
z+=((aW[k]));
else
{
while ((aW[k]+"").length<cellSize)
{
aW[k]= '0'+aW[k];
}
z+=((aW[k]));
}
}
The numbers are at present integers, because we have removed the decimals. Now, we need
to put the decimal points back into the numbers:
//put the decimals back in the numbers
decZ=decX+decY;
x=insertDec(x,decX);
y=insertDec(y,decY);
x=addseps(x);
y=addseps(y);
We have already mentioned addseps on
the subtraction page. It adds the thousands separators (commas). The following function,
insertDec, inserts the decimal point:
function insertDec(num,decPlace) {
var num=num;
var decPlace=decPlace;
ans= "";
mess+= "num="+num+";
decPlace="+decPlace+"<br>";
if (decPlace>0)
{
ans=num.substring(0,num.length-decPlace)+ "."+
num.substring(num.length-decPlace,num.length);
return ans;
}
else
return num;
} //end of insertDec(x,decPlace)
This code removes the leading zeros:
//remove leading zeros from answer:
while (z.charAt(0)=="0")
{
z=z.substring(1,z.length);
}
if (z.charAt(0)==".")
z= "0"+z;
But if the number begins with a decimal, then a leading zero is added.
We have previously created t1, the start time, and we now create t2 and subtract the
two times as below:
t2= new Date();
t1=(t2.getTime()-t1.getTime())/1000
Completing
The Code
z=insertDec(z,decZ);
//alert("z after insert="+z);
z=addseps(z);
//check num length
if
(checkAns(x,y,ans))
s+= "Answer checks
OK<br>";
else
s+= "Answer
error<br>";
//remove trailing zeros from decimals
z=remTrailingZeros(z);
x=remTrailingZeros(x);
y=remTrailingZeros(y);
s+=x+ " x <br>"+y+"=<br>";
s+=z+ "<br>";
var numDig=z.length;
if (z.indexOf(".")>-1)
numDig-=1;
s+= "Num Digits: "+numDig+"<br>";
s+=( "js answer=<br>"+(Number(n1)*Number(n2))+"<br>");
s+= "Time: "+t1+" seconds";
document.getElementById( "s1").innerHTML=s;
}//else number checks
}
function remTrailingZeros(x) {
var decPos=x.indexOf(".")
if (decPos>-1)
{
first=x.substring(0,decPos);
second=x.substring(decPos,x.length);
while
(second.charAt(second.length-1)=="0")
second=second.substring(0,second.length-1);
if (second.length>1)
return first+second;
else
return first;
}
return x;
} //end of remTrailingZeros(x)
|
|
![[Back to
previous page]](BackArrow.gif){kind=small}
![[Next Page
in Series]](ForwardArrow.gif){kind=small}