multiplication of 2 very bin Number. More than 2^53

#1
VakhoQ

Posted 01 March 2011 - 06:46 AM

Programmer

Members
126 posts

In JavaScript, Maximum Value of Integer is 2^53. How to multiplicate 2 big numbers, thich is more than 2^53.
For example, I want what is result of 32732136127321832131312*321321999887631263123131= ???

let's write Algorithm. We know, how to multiplicate numbers by our pensil in our exercise book.
For example: how to calculate 892 *670?

#####892
#####670
................
####0000
###6244
##5352
................
##597640

now we have a="892" and b="670"; a and b is a String. we should write each number in Array and then convert to Int.

A[2]=8, A[1]=9, A[0]=2;
B[2]=6, B[1]=7, B[0]=0;

Example:

*########### Fill Array A ########*/

do{   

i++;

A[i]=a.charAt(a.length-i-1);

}while((a.length-i-1)!=0);


/*########### Fill Array B ############*/


do{   

t++;

B[t]=b.charAt(b.length-t-1);

}while((b.length-t-1)!=0);

Then COnvert To Int;


/*##### Convert String to INT ####*/

for (var i in A) A[i]=parseInt(A[i]);   

for (var i in B) B[i]=parseInt(B[i]);

ok, thats good! now we have to multiplicate each A[i] numbers All the B[j] number.
And the result want to be In a C Array();

for example

##############A[2] A[1] A[0] // there are I
##############B[2] B[1] B[0] // there are J
............................................................................
#############C[0][3] C[0][2] C[0][1] C[0][0]
#######C[1][3] C[1][2] C[1][1] C[1][0]
C[2][3] C[2][2] C[2][1] C[2][0]
..........................................................................

C[0][0]= B[0]*A[0]
C[0][1]= B[0]*A[1]
C[0][2]= B[0]*A[2]

C[1][0]= B[1]*A[0]
C[1][1]= B[1]*A[1]
C[1][2]= B[1]*A[2]

C[2][0]= B[2]*A[0]
C[2][1]= B[2]*A[1]
C[2][2]= B[2]*A[2]

ok thats good. Now how tu sum this Arrays? that's something dificult, is not it? lat's see what we have.
We can write this C Array In Matrix.

00 means C[0][0]
21 means C[2][10]

|00 01 02 03|
|10 11 12 10|
|20 21 22 20|
|30 31 32 33|

ok. Now what we have?
firstly, we write 00
then, we have to sum 01 and 10 - C[0][1]+C[1][0].
then, we have to sum 02, 11 and 20 - C[0][2]+C[1][1]+C[2][0]
and so on....

00 01 02 03 10 20 33
10 11 12 22 32
20 21 32
30

I) part. what is happening? we need observation.

00 01 02 03
10 11 12
20 21
30

i is 0. i increase. i++
j is 1. j decrease. j--
while i!=j
and so on....



/* #####################################################

 ======================================================

 Name        : Multiplication 2 numbers , that is  more than 2^53

 Author       : VakhoQ From Georgia.

 Copyright   : VakhoQ.

 For:           : Codecall.net

======================================================

#################################################### */ 



MJ=a.length-1;

for(j=0; j<=MJ; j++)   

{  

dj=j; 

    for (i=0; i<=j+dj; i++)

    {      

     document.write("[",  i, j  ,"]");              

    j--; 

    }  document.write("<br>");


j=dj;

}

II) part. what is happening? observation also...

10 20 33
22 32
32

i increase.
j decrease.


j=MJ;  

for(i=1; i<=j; i++)

{ 

 di=i;

 dj=j;

    do{

    document.write("[",  i, j  ,"]");     

    i++;

    j--;

    }while((i-1)!=MJ);

    document.write("<br>");

 i=di;

 j=dj;

}

ok ok ok. but wait!
for example 123*45; a.length != b.length ==> i have matrix like this:

|00 01 02|
|10 11 12|

but I can fill 20, 21, 22 with zeros. I need this this im My algorithm.
And finally, I fill the result on Array D[].


Edited

Edited by VakhoQ, 13 March 2011 - 02:24 AM.

GNU/Linux Is the Best.

#2
Alexander

Posted 01 March 2011 - 11:11 PM

It's Science!

Moderators
4,118 posts

Location:Vancouver, Eh! Cleverness: 200

A great neat set of code, and all numbers work flawlessly compared to my arbitrary precision calculator. You can certainly use this in an online calculator, I don't think I've seen a single one that is arbitrary precision yet.

Be sure to read the updated FAQ! || Health is achieved through the same 10,000 steps.
If a suggested code/method fails, informing us is less important than telling us why or what errors occurred.

#3
VakhoQ

Posted 02 March 2011 - 03:11 AM

Programmer

Members
126 posts

In addition (Again Explanation, For Easily understand):

The main Part is how to Sum This numbers:

[00] // the first number
[01][10] // C[0][1]+ C[1][0] is the Second ans so on...
[02][11][20]
[03][12][21][30]
[04][13][22][31][40]
[14][23][32][41]
[24][33][42]
[34][43]
[44] // The final number

And this numbers are from Matrix:

00 01 02 03 04
10 11 12 13 14
20 21 22 23 24
30 31 32 33 34

The first Result . D[0]
00 # # # #
# # # # #
# # # # #
# # # # #

the second Result.D[1] = C[0][1]+C[1][0]
# 01 # # #
10 # # # #
# # # # #
# # # # #

next:
# # 02 # #
# 11 # # #
20 # # # #
# # # # #

for this we write:

Part I


for(j=0; j<=4; j++)

{  

    k=j; 

 

      for (i=0; i<=j+k; i++)

      {     

      document.write("[",  i, j  ,"]");               

      j--; 

      }

   document.write("<br>");

   j=k;

}

/* Result well be
[00]
[01][10]
[02][11][20]
[03][12][21][30]
[04][13][22][31][40]
*/

Part II


var dj; var i; var j=4;

  for(i=1; i<=j; i++) { 

 di=i; 

 dj=j;     

         do{     

         document.write("[",  i, j  ,"]");      

          i++;    

          j--;      

          }while((i-1)!=4);   

         document.write("<br>");

 i=di;

 j=dj;

}

/* Result well be
[14][23][32][41]
[24][33][42]
[34][43]
[44]
*/

And the Matrix is from here:

for example: 12345*12345 =

######12345
######12345
..........................
#####61725 + <<< 5 is C[0][0] , 2 is C[0][1] and So on...
####49380 + <<< 5 is C[1][0] , 2 is C[1][1] and So on...
###37035 + <<< And so on...
##24690 +
......................
=152399025

Thants all :) see other parts or full code, in a full source. :)

GNU/Linux Is the Best.

#4
VakhoQ

Posted 02 March 2011 - 03:20 AM

Programmer

Members
126 posts

Alexander
thanks ;)

GNU/Linux Is the Best.

#5
VakhoQ

Posted 02 March 2011 - 04:42 AM

Programmer

Members
126 posts


/* #####################################################

 ======================================================

Name######: Multiplication 2 numbers , that is  more than 2^53. 

Version###: V2

Author####: VakhoQ (Vakhtang Koroghlishvili) From Georgia, Tbilisi.

University: TSU

Copyright#: VakhoQ.

For:######: Codecall.net

======================================================

#################################################### */ 




<script>


function NN(a,b){


// var a="19798709798797321321321321321331321213131312321321";   

// var b="33987098897097321312321321323213232131232131232132";


var A = new Array();

var B = new Array();

var C = new Array();  

var D = new Array();


var i=-1;

var t=-1;


/*########### Fill Array A ########*/

do{   

i++;

A[i]=a.charAt(a.length-i-1);

}while((a.length-i-1)!=0);


/*########### Fill Array B ############*/

do{   

t++;

B[t]=b.charAt(b.length-t-1);

}while((b.length-t-1)!=0);


/*##### Convert String to INT ####*/

for (var i in A) A[i]=parseInt(A[i]);   

for (var i in B) B[i]=parseInt(B[i]);   


        

for(i=0; i<=b.length-1; i++)   C[i] = new Array();                            


var N=0; var t;

var MJ;

var TestIfSet=0;


for(i=0; i<=b.length-1; i++)    

{  

    for(j=0; j<=a.length-1; j++)

    {       

         if(j==a.length-1)

         {         

         C[i][j]=(B[i]*A[j])+N; 


                 if(C[i][j] >9) 

                 {                    

                 t=0;                     

                 var C2=new String(C[i][j]); 

                    

                 do{                

                   C[i][j+t]=Number(C2.charAt(C2.length-t-1));      

                   if(TestIfSet==0){ MJ=j+t;}

                   if(TestIfSet!=0 && j+t > MJ){MJ=t+j;}  

                   t++;

                   }

                 while((C2.length-t)!=0);   

                 TestIfSet=1;


                 }         

         }    


         else

         {       

         C[i][j]=B[i]*A[j]+N;                   

         N = (C[i][j]-C[i][j]%10)/10;

	 C[i][j]=C[i][j]%10;

         }   

    } 

    N=0;

}  

      document.write("<Br>");



 

document.write("<br> Our Matrix <br>");

for (i=0; i<=MJ; i++)

{

    for(j=0; j<=MJ; j++)

    {

    document.write(" ",  i, j, " "  );   

    }document.write("<br>");

}   

 







document.write("  <br> Values Of Matrix<br>"); 


for (i=0; i<=MJ; i++)

{

    for(j=0; j<=MJ; j++)

    {

        if(typeof C[i]== 'undefined' || C[i][j]==null )

        { 

     

           if(typeof C[i] ==  'undefined')

           {

           C[i]= new Array();

           }

           C[i][j]=0;

        }



    document.write(" ",  C[i][j] , " "  );  

    }  document.write("<br>");

}   

  document.write("<br>");






document.write("<br><br><br><br>Summing Matrix Parts<br>");  


// Part I


var di;  

var dj;

var H=0;

var N=0;


for(j=0; j<=MJ; j++)   

{  

dj=j; 

D[H]=0;


    for (i=0; i<=j+dj; i++)

    {    

    D[H]+=C[i][j];  

    document.write("[",  i, j  ,"]");                  

    j--; 

    } document.write("<br>");

    D[H]+=N; 


    if(D[H]<10)

    { 

    N=0; 

    }   

    

    else if(D[H]>9)

    {

    N=(D[H]-D[H]%10)/10;

    D[H]=D[H]%10;

    }


      

     

j=dj;

H++;

}



// Part2

j=MJ;  


D[H]=0;

for(i=1; i<=j; i++)

{ 


 di=i;

 dj=j;


    do{

    document.write("[",  i, j  ,"]");     

    D[H]+=C[i][j];    

    i++;

    j--;

    }while((i-1)!=MJ);

    document.write("<br>");

    D[H]+=N;   // sumed + N


    if(j==MJ){

    // End. finally D[H]+=N;

    }


    else if(D[H]<10)

    { 

    N=0; 

    }   

    

    else

    {   

    N=(D[H]-D[H]%10)/10;

    D[H]=D[H]%10;

    }



 i=di;

 j=dj;

H++;

D[H]=0;

}



 

document.write("<br> <br>");


//  ## Sharp ##

     var Sharp=MJ;

     Co=0;   

     do{       

     Co++;   

     document.write("#");      

     } while(Co!=Sharp); ; 

     Sharp--;

//  ## Sharp ##




document.write(a, " * <br>");


//  ## Sharp ##

     var Sharp=MJ;

     Co=0;   

     do{       

     Co++;   

     document.write("#");      

     } while(Co!=Sharp); ; 

     Sharp--;

     

//  ## Sharp ##



document.write(b, " * <br>");


//  ## Line ##

     Co=-1;

     do{         

     document.write(".");

     Co++;

     } while(Co!=(MJ)*5);

     document.write("<br>");

//  ## Line ##



k=0; 

var Sharp=MJ;


do{ 



//  ## Sharp ##

     Co=0;   

     do{       

     Co++;   

     document.write("#");      

     } while(Co!=Sharp); ; 

     Sharp--;

//  ## Sharp ##



   for(var i = C[k].length - 1; i>=0 ; i--)

   {

   document.write(C[k][i]); 

   }

   document.write("+ <br>"); 

    

k++;

}while(k!=MJ)


//  ## Line ##

     Co=-1;

     do{         

     document.write(".");

     Co++;

     } while(Co!=(MJ)*5);

     document.write("<br>");

//  ## Line ##

 


var StRresult = new String();

for(i=0; i<=D.length-1; i++){

StRresult=D[i]+StRresult;   

}



while(StRresult.length > 0 && StRresult.substr(0,1) == "0"){

StRresult = StRresult.substr(1);

}



return StRresult;


}



var a = prompt("Enter Value of a ", "");

var b = prompt("Enter Value ofb ", "");

var finalRez=NN(a,b)


document.write("=", finalRez, "<br><br><br>", a, "*" ,b, "=",  finalRez);



    

 

</script>

Result will be like this:
Our Matrix
00 01 02 03 04 05 06 07 08 09 010 011 012 013 014 015 016
10 11 12 13 14 15 16 17 18 19 110 111 112 113 114 115 116
20 21 22 23 24 25 26 27 28 29 210 211 212 213 214 215 216
30 31 32 33 34 35 36 37 38 39 310 311 312 313 314 315 316
40 41 42 43 44 45 46 47 48 49 410 411 412 413 414 415 416
50 51 52 53 54 55 56 57 58 59 510 511 512 513 514 515 516
60 61 62 63 64 65 66 67 68 69 610 611 612 613 614 615 616
70 71 72 73 74 75 76 77 78 79 710 711 712 713 714 715 716
80 81 82 83 84 85 86 87 88 89 810 811 812 813 814 815 816
90 91 92 93 94 95 96 97 98 99 910 911 912 913 914 915 916
100 101 102 103 104 105 106 107 108 109 1010 1011 1012 1013 1014 1015 1016
110 111 112 113 114 115 116 117 118 119 1110 1111 1112 1113 1114 1115 1116
120 121 122 123 124 125 126 127 128 129 1210 1211 1212 1213 1214 1215 1216
130 131 132 133 134 135 136 137 138 139 1310 1311 1312 1313 1314 1315 1316
140 141 142 143 144 145 146 147 148 149 1410 1411 1412 1413 1414 1415 1416
150 151 152 153 154 155 156 157 158 159 1510 1511 1512 1513 1514 1515 1516
160 161 162 163 164 165 166 167 168 169 1610 1611 1612 1613 1614 1615 1616

Values Of Matrix
2 1 3 3 1 2 3 1 2 4 5 1 2 3 1 2 3
4 2 6 6 2 4 6 2 4 8 0 3 4 6 2 4 6
6 3 9 9 3 6 9 3 6 2 6 4 6 9 3 6 9
4 2 6 6 2 4 6 2 4 8 0 3 4 6 2 4 6
2 1 3 3 1 2 3 1 2 4 5 1 2 3 1 2 3
6 3 9 9 3 6 9 3 6 2 6 4 6 9 3 6 9
2 1 3 3 1 2 3 1 2 4 5 1 2 3 1 2 3
4 2 6 6 2 4 6 2 4 8 0 3 4 6 2 4 6
6 3 9 9 3 6 9 3 6 2 6 4 6 9 3 6 9
2 1 3 3 1 2 3 1 2 4 5 1 2 3 1 2 3
4 2 6 6 2 4 6 2 4 8 0 3 4 6 2 4 6
6 3 9 9 3 6 9 3 6 2 6 4 6 9 3 6 9
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Summing Matrix Parts
[00]
[01][10]
[02][11][20]
[03][12][21][30]
[04][13][22][31][40]
[05][14][23][32][41][50]
[06][15][24][33][42][51][60]
[07][16][25][34][43][52][61][70]
[08][17][26][35][44][53][62][71][80]
[09][18][27][36][45][54][63][72][81][90]
[010][19][28][37][46][55][64][73][82][91][100]
[011][110][29][38][47][56][65][74][83][92][101][110]
[012][111][210][39][48][57][66][75][84][93][102][111][120]
[013][112][211][310][49][58][67][76][85][94][103][112][121][130]
[014][113][212][311][410][59][68][77][86][95][104][113][122][131][140]
[015][114][213][312][411][510][69][78][87][96][105][114][123][132][141][150]
[016][115][214][313][412][511][610][79][88][97][106][115][124][133][142][151][160]
[116][215][314][413][512][611][710][89][98][107][116][125][134][143][152][161]
[216][315][414][513][612][711][810][99][108][117][126][135][144][153][162]
[316][415][514][613][712][811][910][109][118][127][136][145][154][163]
[416][515][614][713][812][911][1010][119][128][137][146][155][164]
[516][615][714][813][912][1011][1110][129][138][147][156][165]
[616][715][814][913][1012][1111][1210][139][148][157][166]
[716][815][914][1013][1112][1211][1310][149][158][167]
[816][915][1014][1113][1212][1311][1410][159][168]
[916][1015][1114][1213][1312][1411][1510][169]
[1016][1115][1214][1313][1412][1511][1610]
[1116][1215][1314][1413][1512][1611]
[1216][1315][1414][1513][1612]
[1316][1415][1514][1613]
[1416][1515][1614]
[1516][1615]
[1616]

################32132154213213312 *
################321321312321 *
.................................................................................
################32132154213213312+
###############64264308426426624+
##############96396462639639936+
#############64264308426426624+
############32132154213213312+
###########96396462639639936+
##########32132154213213312+
#########64264308426426624+
########96396462639639936+
#######32132154213213312+
######64264308426426624+
#####96396462639639936+
####00000000000000000+
###00000000000000000+
##00000000000000000+
#00000000000000000+
.................................................................................
=10324745959490450650146817152

32132154213213312*321321312321=10324745959490450650146817152

Edited by VakhoQ, 13 March 2011 - 02:25 AM.

GNU/Linux Is the Best.

#6
VakhoQ

Posted 04 March 2011 - 02:31 AM

Programmer

Members
126 posts

Oh... There are 1 mistake in the Script. The script only works well when a.length = b.length OR a.length > b.length.
So we Should Add a little Code to way out of the situation. I've already correct my code. Think about this detail , thats very easy to solve the problem. :) And I've made a mistake now in the code. You Should Find it and add something. We are in the tutorial, So you should do ;)

Edited by VakhoQ, 13 March 2011 - 02:28 AM.

GNU/Linux Is the Best.