Алгоритм Карацубы в Javascript

Question

Я реализовал алгоритм Карацубы в Javascript.

const multiply = (a, b) => { 
    let sizeA = numOfDigits(a); 
    let sizeB = numOfDigits(b); 
    if(sizeA < sizeB) { 
     a = '0'.repeat(sizeB-sizeA).concat(a); 
    } 
    else if(sizeB < sizeA) { 
     b = '0'.repeat(sizeA - sizeB).concat(b); 
    } 
    if (numOfDigits(a) === 1 && numOfDigits(b) === 1) { 
     return a * b; 
    } else { 
     let n = numOfDigits(a); 
     n = (n % 2 === 0) ? n : n + 1; 
     let n_2 = parseInt(Math.ceil(n /2)); 
     let splitA = reduceInHalf(a); 
     let splitB = reduceInHalf(b); 
     let p = splitA[0]; 
     let q = splitA[1]; 
     let r = splitB[0]; 
     let s = splitB[1]; 
     let u = multiply(p, r); 
     let v = multiply((q - p).toString(), (s - r).toString()); 
     let w = multiply(q, s); 
     let product = u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w; 
     return product; 
    } 
} 

Это происходит, когда я пропускаю очень большие цифры, скажем, 2 цифры из 64 цифр. Я попал в проблему с максимальным количеством вызовов. Я также столкнулся с другой реализацией, которая вернула неправильный результат.

Все отлично работает с 2 номерами по 32 числа каждый. Он попадает в нерегулярную рекурсию, как только я ввожу 2 64-значных числа. Можно ли это сделать?

Answer 1

Похоже, вы полагаетесь на числовые функции JavaScript для различных частей (например, q - p и все u * Math.pow(10,n) + (u + w - v) * Math.pow(10, n_2) + w); но номера JavaScript являются значениями с плавающей запятой с двойной точностью. Они не могут точно представлять целые числа из более чем 16 цифр. (См. "biggest integer that can be stored in a double".)

Если вы хотите сделать математику с очень большими целыми числами, вам нужно либо найти библиотеку с большим целым, либо управлять ею самостоятельно (используя строки или массивы или еще много чего).