Каратсуба умножение больших чисел не удается в JavaScript

Question

Я пробовал две версии алгоритма умножения Карацубы, и они оба не дают разных результатов, когда я тестирую их с большими значениями X и Y.

Параметры, которые я использую

const x = 3141592653589793238462643383279502884197169399375105820974944592
const y = 2718281828459045235360287471352662497757247093699959574966967627
const solution = 8539734222673567065463550869546574495034888535765114961879601127067743044893204848617875072216249073013374895871952806582723184

Алгоритм1, который я получил с этой страницы: https://gist.github.com/haocong/c2d9b2169d28eb15a94d

Expected value to equal:
  8.539734222673567e+126
Received:
  7.292575034127423e+22

Алгоритм2, который я получил с этой страницы: https://stackoverflow.com/a/28376023/604950

Expected value to equal:
  8.539734222673567e+126
Received:
  6.0002556749374185e+22

Для воспроизведения вы можете получить этот PR: https://github.com/Falieson/Algorithms-Illuminated-Part1_TheBasics/pull/1

Answer 1

Это потому, что вы используете слишком большие числа, а JavaScript не знает, как их обрабатывать.

Метод Number.isSafeInteger () определяет, будет липредоставленное значение - это число, которое является безопасным целым числом.

2 ^ 53 - 1 является безопасным целым числом: оно может быть точно представлено, и никакие другие целые числа не округляются до него в любом режиме округления IEEE-754.Напротив, 2 ^ 53 не является безопасным целым числом.

console.log (warn (Math.pow (2, 53)));// ожидаемый результат: «Точность может быть потеряна!»

MDN

например, во втором алгоритме вы выполняете

var res  =   (z2 *  Math.pow(10, 2 * m )  ) + ( (z1-z2-z0) * Math.pow(10,  m )) + z0;

, что небезопаснооперации в вашем случае, и JavaScript не может его правильно вычислить, что дает вам неверный результат.

Если вы поместите этот код под вышеупомянутой строкой, вы увидите, что.

console.log(Number.isSafeInteger(10 ** (2 * m)));

Thisоценивается как ложное.