Возведение в степень по модулю. Что не так?
Здравствуйте, гениальный математик, просматривающий тему.
Помогите починить мою бедную, сломанную голову и дайте совет что может быть не так и как должно быть ТАК. Имеем набор функций, собранных из разных уголков интернета(изложенных мной) и предназначенных для возведения большого числа в большую степень по модулю:
/*1 - способ "справа налево. Представляем степень в виде двоичного числа и в зависимости от нуля или единицы творим всякую фигню."*/
const PowToModFromWiki = (base, pow, mod) =>{
let step = pow.toString(2).split('').map(Number);
let result = 1;
for(let i=step.length-1;i>0;i--){
result =(result * base**step[i])%mod;
base = (base**2)%mod;
}
return (result*base)%mod;
}
/*2 - способ упрощение степени. Возводим базу в квадрат, делим степень пополам*/
const anotherPowToMod = (base, pow, mod) => {
let temp = 1;
while (pow>2){
if (!(pow%2)) {
base = base**2%mod;
pow/=2;
}
else {
pow--;
temp =(temp * base)%mod;
}
}
return (temp * (base**pow % mod))%mod;
}
/*3 - рекурсивное быстрое возведение в степень. Ненавижу рекурсию*/
const recursePowToMod = (base, pow, mod) => {
const bynPow = (base, pow) =>{
if (pow == 1) return base;
if (pow%2 == 0) {
let temp = bynPow(base, pow/2);
return temp**2%mod;
} else return bynPow(base, pow-1)*base%mod;
}
return bynPow (base, pow);
}
/*4 - школьный метод, самый простой. Без комментариев.*/
const tooDumbPowToMod = (base, pow, mod) => {
let result = 1;
for(let i=0; i<pow; i++) {
result = result * base % mod;
}
return result;
}
И все бы хорошо - при малых значениях базы, степени и модуля они возвращают одинаковое (правильное) значение. Но, с ростом вводимых значений они начинают чудить: 1 и 2 возвращают одно значение 3 иногда как 1 и 2, а иногда свое; 4 - держится дольше всех, на 9-10 значных числах, ломаясь. Вот, к примеру входные значения:366142356 1447804911 219020071 (вероятно)Правильный ответ - 38504623 |
Добрый_Серый_Волк,
искать библиотеку которая поддерживает большие числа типа Big Number. |
|
Senseye, осёл и яблоко не умеют.
А вообще бесит что нельзя смешивать BigInt и Number - это против всей парадигмы языка идёт, в котором можно было любые операции к чему угодно применять не боясь словить Exception. Возвращали бы BigInt в итоге, или, если так принципиально - NaN. |
Приводиш в нужные типы и все
Number(BigInt(100) ** BigInt(2)) А по поводу Exception, нужно писать тесты |
Тесты это прекрасно, но изменение основной логики при введении нового типа и только для этого типа - это преступлении против языка.
Я мог умножить что угодно на что угодно, хоть Number хоть Object хоть чёрта в ступе, и продолжить работу со своим NaN. Но тут вылезает BigInt, который умножается только на BigInt да ещё и кидает exception. Это позволительно для сторонней либы, но никак не для нового примитивного типа. |
Спасибо, дорогие товарищи, за ответы. Читал про BigInt и пробовал с этим типом, но что-то не пошло. Видать не умею их готовить.
Проблему потери точности(ну и задачу) решил написанием и добавлением двух простых алгоритмов: умножения(по Трахтенбергу) и вычитания (заменил им деление по модулю) чисел в их строковом представлении. |
Цитата:
function powToMod(base, power, module) {
if(power === 1n) return base;
if(power % 2n === 0n) return powToMod(base, power / 2n, module) ** 2n % module;
return powToMod(base, power - 1n, module) * base % module;
}
alert(powToMod(366142356n, 1447804911n, 219020071n));
BigInt не является частью спецификации ECMASCRIPT 2019, черновик смотрите на https://tc39.es/proposal-bigint/ Данный ответ написан с использованием данного черновика, возможно кардинальное изменение в логике. Не стоит сейчас это использовать в браузере, но думаю вы можете использовать в node.js, поскольку управляемое вами окружение! https://caniuse.com/#feat=bigint Цитата:
Семантика всех операторов в идеале должна основываться на некоторых математических принципах, чтобы соответствовать ожиданиям разработчиков. Операторы деления и нахождения остатка основаны на соглашениях из других языков программирования для целых чисел. Тип Number может представить только математические значения c точностью в 15—17 десятичных цифр и масштабы в диапазоне примерно от 10⁻³⁰⁸ до 10³⁰⁸. Т. е. он представляет конечное число чисел. Это конечное множество чисел. Тип BigInt представляет целочисленные математические значения. Т. е. этот тип представляет бесконечное число чисел. Это множество целых чисел. Т. е. получается, что тип BigInt в основном представляет бесконечное кол-во чисел, которые не могут быть выражены через тип Number. Цитата:
Цитата:
Цитата:
try {
alert("Symbol: " + Symbol.iterator);
} catch(error) {
alert("Это не ECMAScript1, приведите к нужному типу");
}
Однако поймали!В ECMAScript1 не было блока try-catch, так что вы бы не смогли поймать исключение при умножении {} * {}, поэтому вам выдают до сих пор (из-за обратной совместимости) NaN в таких случаях. Кстати при сложении строк и массивов определённой длины тоже может произойти исключение. Продемонстрирую на примере массива
try {
const a = new Array(2 ** 32 - 1);
const b = [1, 2, 3];
const c = a.concat(b);
alert(c.length);
} catch(error) {
alert("Не складывается");
}
UPD Так как тогда 5 поделить на 2? Используйте либо тип Number, либо тип BigInt. alert(5n / 2n); alert(5 / 2); UPD #funfact Двоичное, восьмеричное и шестнадцатеричное представление целых чисел... alert(0xffffffffffffffffffffffffffffffffffffffffffn); alert(0b111111111111111111111111111111111111111111n); alert(0o777777777777777777777777777777777777777777n); UPD Возможно многие вопросы отпадут, если вы подумаете, что тип называется именно BigInt, а не BigDecimal. UPD BigInt не является частью спецификации, черновик предложения https://tc39.es/proposal-bigint/ |
| Часовой пояс GMT +3, время: 23:08. |