Модуль возведения в степень по квадрату в JavaScript не работает правильно? - PullRequest
Новая
       8

Модуль возведения в степень по квадрату в JavaScript не работает правильно?

0 голосов
/ 29 сентября 2018

В течение последних нескольких часов я пытался реализовать экспонирование путем возведения в квадрат в Javascript.В основном я пытался применить Теорему Ферма Литтла для решения модульного мультипликативного обратного.Кажется, что это должно быть прямо вперед, но я получаю неправильные результаты: 

const MAX = 10**9 + 7
const inv2 = expBySquare(2, MAX-2)
// inv2 should be 500000004 but is 437533240

function expBySquare(x, n) {
  if (n < 0) throw 'error'
  if (n === 0) return 1
  if (n === 1) return x

  if (n % 2 === 0) return expBySquare((x * x) % MAX, n / 2) % MAX
  return (x * expBySquare((x * x) % MAX, (n - 1) / 2)) % MAX
}

Я только что попытался реализовать алгоритм в C https://onlinegdb.com/H1tsx4TY7, и он работал без проблем.Я знал, что мне следует ожидать проблем с переполнением в JS, но я думаю, что он может обрабатывать числа, так как по модулю используется во всех слабых местах.

Ответы [ 2 ]

0 голосов
/ 29 сентября 2018

Я знал, что следует ожидать проблем с переполнением в JS, но я думаю, что он может обрабатывать числа, поскольку модуль используется во всех слабых местах.

JavaScript нена самом деле имеет отличный тип "integer" с "overflow";скорее он просто имеет тип «число», значения которого являются числами с плавающей запятой двойной точности и подвержены ошибке округления.Таким образом, даже если значение x * x представляется в виде 64-разрядного целого числа, оно не может быть точно представлено в виде числа JavaScript.Числа JavaScript могут точно представлять любое целое число в диапазоне [- (2 53 -1), 2 53 -1] - см. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER - но ваши вычисления включают значениявне этого диапазона.

Чтобы убедиться, что вы выходите за пределы этого диапазона, вы можете вставить это: 

if (x * x > Number.MAX_SAFE_INTEGER)
    throw 'error: ' + x + ' * ' + x + ' is ' + (x * x);

Вы увидите error: 294967268 * 294967268 is 8700568919138382<strong>0</strong>, хотя 294,967,268 × 294,967,268 на самом деле8,7005,689,191,383,82 4 .

Чтобы это исправить, вам нужно либо меньшее значение MAX (для обеспечения MAX * MAX <= Number.MAX_SAFE_INTEGER), либо использовать (частичное) библиотека больших целых чисел для выполнения целочисленной арифметики с большими значениями, которые вы используете.

0 голосов
/ 29 сентября 2018

Числа JavaScript всегда используют 64-битный формат с плавающей запятой.Следовательно, вы можете работать только с мантиссой в 52 бита, что дает вам эффективные 53 бита.Промежуточные значения в вашем сценарии превышают те, которые приведут к ошибкам округления.Первый раз, когда это происходит, это квадрат 279,632,277.Это должно быть 78,194,210,340,204,729 (57 бит), но округляется до 78,194,210,340,204,730.

...