умножение длинных чисел

 
0
 
JavaScript
ava
xervin | 17.10.2011, 22:40
Все доброго времени суток!
В ходе изучения javascript решил попробовать написать умножение длинных чисел методом Карацубы. Но вот незадача - скрипт оказывается рабочим только при длине числа до 6 знаков
((


<body onLoad='main()'>
<script language='javascript'>

var BASE = 10 //система счисления
var MIN_LENGTH_FOR_KARATSUBA = 4 //числа короче умножаются квадратичным алгоритмом
var MAX_DIGITS=1024;


function normalize(l) {
/*Нормализация числа - приведение каждого разряда в соответствие с системой счисления.
*
*/
i=0;
while(i < l.length) {
if (l[i] >= BASE) { //если число больше максимального, то организовавается перенос
carryover = (l[i] / BASE)|0;
if (l[i+1]*0!=0) {l[i+1]=0;l[i + 1] += carryover;} else {l[i + 1] += carryover;}
l[i] -= (carryover * BASE)|0;
} else if (l[i] < 0) { //если меньше - заем
carryover = ((l[i] + 1) / BASE - 1)|0;
if (l[i+1]*1!=1) {l[i+1]=0;l[i + 1] += carryover;} else {l[i + 1] += carryover;}
l[i] -= (carryover * BASE)|0;
}
i++;
}
}
function getNum(a,c) {
var i;
var s;
a_b = 0;
var buf=0;
while (c>=1) {
if(a_b >= MAX_DIGITS) {
break;
}
a[a_b] =(c % 10)|0;
c/=10;
c=c|0;
++(a_b);
}
// for(i = 0; i * 2 < a_b - 1; i++) {
// buf = a[i], a[i] = a[a_b - i - 1], a[a_b - i - 1] = buf;}
return a;
}

function karatsuba(a, b,ret) {
var d=(a.length<b.length)? a.length : b.length;
var asum=new Array();
var bsum=new Array();
var x1=new Array();
var x2=new Array();
var x3=new Array();
//alert(a+'\n'+b+'\n'+d);
if (d < MIN_LENGTH_FOR_KARATSUBA) { //если число короче то применять наивное умножение
for(i=0;i<a.length+b.length;i++) ret[i]=0;
for(i = 0; i < a.length; i++) {
for(j = 0; j < b.length; j++) ret[i + j] += a[i] * b[j];
}
//alert(ret + ' = ' + d + ' \n' + a + ' * ' + b);
} else { //умножение методом Карацубы
var al=new Array(); //младшая часть числа a
al=div(a,false);

var ar=new Array(); //старшая часть числа a
ar=div(a,true);

var bl=new Array(); //младшая часть числа b
bl=div(b,false);

var br=new Array(); //старшая часть числа b
br=div(b,true);
d=(al.length>ar.length)? al.length : ar.length;
for(i = 0; i < d; i++) {
asum[i] = al[i] + ar[i];
}
d=(bl.length>br.length)? bl.length : br.length;
for(i = 0; i < d; i++) {
bsum[i] = bl[i] + br[i];
}

//alert(asum+" = " + bsum);
d=(a.length>b.length)? a.length : b.length;
karatsuba(al, bl, x1, d/2|0);
karatsuba(ar, br, x2, d/2|0);
karatsuba(asum, bsum, x3, d/2|0); // произведение сумм частей
//alert(asum+"\n"+bsum+"\n"+ar+"\n"+al+"\n"+br+"\n"+bl+"\n"+d);
//alert(x1+'\n'+x2+'\n'+x3+ "\n"+ret);
for(i = 0; i < x3.length; i++) x3[i] = x3[i] - x1[i] - x2[i];
normalize(x1);
normalize(x2);
normalize(x3);

for(i = 0; i < x1.length; i++) ret[i]+=x1[i];
for(i = 0; i < x3.length; i++) ret[i+d/2|0]+=x3[i];
for(i = 0; i < x2.length; i++) ret[i+d]+=x2[i];
}
//normalize(ret);
}

function div(numb,flag) {
var length=flag? (numb.length / 2)|0 : ((numb.length+1) / 2)|0;//true - старшая
values=new Array();
j=0;
if (flag) {
for(i=length;i<numb.length;i++) {
values[j]=numb[i];
j++;
}
}
else {
for(i=0;i<length;i++) {
values[j]=numb[i];
j++;
}
}
return values;
}

function printNum(a) {
var s="";
var f=0;
for(i=a.length-1;i>=0;i--){
if (f==3) {f=0;s+=" ";}
f++;
s+=a[i];
}
alert(s);
}

function main() {
var c1 = 1*prompt("Число:","123456");
var c2 = 1*prompt("Число:","123456");
var a=new Array(); // first multiplicand
var b=new Array(); // second multiplicand
var r=new Array(); // result

a=getNum(a,c1);
b=getNum(b,c2);

var d=(a.length>b.length)? a.length : b.length;
for(i=0;i<d*2;i++) r[i]=0;
//for(i=0;i<d;i*=2);
karatsuba(a,b,r,d);
normalize(r);alert(r);
//printNum(r);
}
</script>
</body>


может подскажете?
Kommentare (1)
ava
magelan | 19.10.2011, 11:36 #
JS это не Питон который позволяет в числах хранить числа любой разрядности.
Для чисел любой длины JS представляет строки и достаточно удобные методы работы с ними

Я использовал умножение методом Шёнхаге — Штрассена - http://forum.vingrad.ru/forum/topic-338711.html
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
  magelan   xervin
advanced
Absenden