Показать сообщение отдельно
  #5 (permalink)  
Старый 09.11.2019, 16:48
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,012

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

// вычисляет (n ** p) % m
function powMod(n, p, m) {
  if (n < 1) { return 0; }
  if (m < 0) { m = 0; }
  p = Math.round(p);
  n = n % m;
  var r = 1;
  while (p >= 1) {
    if (p % 2) {
      r = (r * n) % m;
    }
    n = (n * n) % m;
    p = Math.floor(p / 2);
  }
  return r;
}

alert(powMod(34546, 68883, 2437));


в хроме на относительно больших числах это работает быстрее "прямого" вычисления с BigInt

Последний раз редактировалось Alexandroppolus, 09.11.2019 в 16:59.
Ответить с цитированием