Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 30.09.2019, 20:49
Новичок на форуме
Отправить личное сообщение для Добрый_Серый_Волк Посмотреть профиль Найти все сообщения от Добрый_Серый_Волк
 
Регистрация: 20.08.2017
Сообщений: 3

Возведение в степень по модулю. Что не так?
Здравствуйте, гениальный математик, просматривающий тему.
Помогите починить мою бедную, сломанную голову и дайте совет что может быть не так и как должно быть ТАК.
Имеем набор функций, собранных из разных уголков интернета(изложенных мной) и предназначенных для возведения большого числа в большую степень по модулю:
/*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
Ответить с цитированием
  #2 (permalink)  
Старый 30.09.2019, 21:32
Аватар для рони
Профессор
Отправить личное сообщение для рони Посмотреть профиль Найти все сообщения от рони
 
Регистрация: 27.05.2010
Сообщений: 33,064

Добрый_Серый_Волк,
искать библиотеку которая поддерживает большие числа типа Big Number.
Ответить с цитированием
  #3 (permalink)  
Старый 09.10.2019, 00:23
Аватар для Senseye
Новичок на форуме
Отправить личное сообщение для Senseye Посмотреть профиль Найти все сообщения от Senseye
 
Регистрация: 12.11.2016
Сообщений: 4

Возможно добавят тут learn.javascript.ru BigInt
А пока, есть тип BigInt, поддерживает перемножение

Последний раз редактировалось Senseye, 09.10.2019 в 00:27.
Ответить с цитированием
  #4 (permalink)  
Старый 09.10.2019, 00:37
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Senseye, осёл и яблоко не умеют.
А вообще бесит что нельзя смешивать BigInt и Number - это против всей парадигмы языка идёт, в котором можно было любые операции к чему угодно применять не боясь словить Exception. Возвращали бы BigInt в итоге, или, если так принципиально - NaN.
__________________
29375, 35
Ответить с цитированием
  #5 (permalink)  
Старый 09.10.2019, 00:48
Аватар для Senseye
Новичок на форуме
Отправить личное сообщение для Senseye Посмотреть профиль Найти все сообщения от Senseye
 
Регистрация: 12.11.2016
Сообщений: 4

Приводиш в нужные типы и все
Number(BigInt(100) ** BigInt(2))

А по поводу Exception, нужно писать тесты
Ответить с цитированием
  #6 (permalink)  
Старый 09.10.2019, 01:29
Аватар для Aetae
Тлен
Отправить личное сообщение для Aetae Посмотреть профиль Найти все сообщения от Aetae
 
Регистрация: 02.01.2010
Сообщений: 6,480

Тесты это прекрасно, но изменение основной логики при введении нового типа и только для этого типа - это преступлении против языка.
Я мог умножить что угодно на что угодно, хоть Number хоть Object хоть чёрта в ступе, и продолжить работу со своим NaN. Но тут вылезает BigInt, который умножается только на BigInt да ещё и кидает exception. Это позволительно для сторонней либы, но никак не для нового примитивного типа.
__________________
29375, 35
Ответить с цитированием
  #7 (permalink)  
Старый 17.10.2019, 22:00
Новичок на форуме
Отправить личное сообщение для Добрый_Серый_Волк Посмотреть профиль Найти все сообщения от Добрый_Серый_Волк
 
Регистрация: 20.08.2017
Сообщений: 3

Спасибо, дорогие товарищи, за ответы. Читал про BigInt и пробовал с этим типом, но что-то не пошло. Видать не умею их готовить.
Проблему потери точности(ну и задачу) решил написанием и добавлением двух простых алгоритмов: умножения(по Трахтенбергу) и вычитания (заменил им деление по модулю) чисел в их строковом представлении.

Последний раз редактировалось Добрый_Серый_Волк, 17.10.2019 в 22:02.
Ответить с цитированием
  #8 (permalink)  
Старый 18.10.2019, 18:03
Аватар для Malleys
Профессор
Отправить личное сообщение для Malleys Посмотреть профиль Найти все сообщения от Malleys
 
Регистрация: 20.12.2009
Сообщений: 1,714

Сообщение от Добрый_Серый_Волк
Вот, к примеру входные значения:366142356 1447804911 219020071
(вероятно)Правильный ответ - 38504623
Действительно правильный!
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

Сообщение от Aetae
бесит что нельзя смешивать BigInt и Number - это против всей парадигмы языка идёт
А как такое смешение должно работать? Например, поделим 5 на 2n. Какой результат должен получиться? 2.5 или 2n или NaN, как вы предлагаете? На самом деле математическое значение 2.5.

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

Тип Number может представить только математические значения c точностью в 15—17 десятичных цифр и масштабы в диапазоне примерно от 10⁻³⁰⁸ до 10³⁰⁸. Т. е. он представляет конечное число чисел. Это конечное множество чисел.

Тип BigInt представляет целочисленные математические значения. Т. е. этот тип представляет бесконечное число чисел. Это множество целых чисел.

Т. е. получается, что тип BigInt в основном представляет бесконечное кол-во чисел, которые не могут быть выражены через тип Number.

Сообщение от Aetae
или, если так принципиально - NaN
Определённо не NaN, поскольку результатом является математическое значение 2.5.

Сообщение от Aetae
Возвращали бы BigInt в итоге
Лучше всего в данном случае выкинуть исключение о неправильных типах, поскольку и тип Number содержит числа, не приводимые к типу BigInt, и тип BigInt содержит числа, не приводимые к типу Number.

Сообщение от Aetae
можно было любые операции к чему угодно применять не боясь словить Exception
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/

Последний раз редактировалось Malleys, 18.10.2019 в 18:31.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Возведение в степень больших чисел. Алгоритм DH Morr123 Элементы интерфейса 0 13.09.2016 22:07
Не работает if(true){}, что не так? switch001 Javascript под браузер 5 09.08.2013 10:17
Извините что создаю еще одну тему, но мне нужна помощь и ваше мнение megaupload Оффтопик 11 27.05.2013 12:58
Посоветуйте новику, что я делаю не так danil-n2 Общие вопросы Javascript 5 26.04.2013 21:22
Как мне написать свою тему так что бы вы прочитали и помогли ?? Андрей Лебедев Элементы интерфейса 2 09.02.2013 17:49