Javascript.RU

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

Возведение в степень по модулю. Что не так?
Здравствуйте, гениальный математик, просматривающий тему.
Помогите починить мою бедную, сломанную голову и дайте совет что может быть не так и как должно быть ТАК.
Имеем набор функций, собранных из разных уголков интернета(изложенных мной) и предназначенных для возведения большого числа в большую степень по модулю:
/*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
Сообщений: 26,830

Добрый_Серый_Волк,
искать библиотеку которая поддерживает большие числа типа 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
Сообщений: 5,439

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
Сообщений: 5,439

Тесты это прекрасно, но изменение основной логики при введении нового типа и только для этого типа - это преступлении против языка.
Я мог умножить что угодно на что угодно, хоть Number хоть Object хоть чёрта в ступе, и продолжить работу со своим NaN. Но тут вылезает BigInt, который умножается только на BigInt да ещё и кидает exception. Это позволительно для сторонней либы, но никак не для нового примитивного типа.
__________________
29375, 35
Ответить с цитированием
Ответ



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

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


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