2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Функция Эйлера
Сообщение30.04.2022, 16:17 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
slavav в сообщении #1553590 писал(а):
Вам понадобится быстрое возведение в степень
Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 17:58 
Заслуженный участник
Аватара пользователя


01/09/13
4480
mihaild в сообщении #1553686 писал(а):
slavav в сообщении #1553590 писал(а):
Вам понадобится быстрое возведение в степень
Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

Для двойки ведь и двух тысяч достаточно для переполнения...

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 19:28 
Заслуженный участник


26/05/14
981
Согласен mihaild, можно без быстрого возведения в степень.

Geen, последовательное перемножение по модулю решает проблему переполнения.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 20:22 
Заслуженный участник
Аватара пользователя


01/09/13
4480
slavav в сообщении #1553691 писал(а):
Согласен mihaild, можно без быстрого возведения в степень.

Geen, последовательное перемножение по модулю решает проблему переполнения.

Что-то я потерялся - это же как?
Двойку надо реально возводить в степень несколько тысяч. И простые числа порядка десятка тысяч надо возводить в степень порядка десятков.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 20:45 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
Geen в сообщении #1553694 писал(а):
Двойку надо реально возводить в степень несколько тысяч.
Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 23:43 
Заслуженный участник
Аватара пользователя


01/09/13
4480
mihaild в сообщении #1553696 писал(а):
Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

Не понимаю. Допустим в однобайтной арифметике нам надо возвести 3 в десятую степень по модулю 101 - что предлагается?

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение30.04.2022, 23:53 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
Geen в сообщении #1553702 писал(а):
Допустим в однобайтной арифметике нам надо возвести 3 в десятую степень по модулю 101 - что предлагается?
Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную. По модулю 83 - просто в цикле пишем x = (x * 3) % 83.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 04:03 
Заслуженный участник
Аватара пользователя


01/09/13
4480
mihaild в сообщении #1553703 писал(а):
Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную.

Так я и говорю, что ещё и умножение по модулю ("медленное") надо реализовать. И какой смысл умножать в цикле, если быстрое возведение в степень реализуется всего парой дополнительных строчек?

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 10:45 
Заслуженный участник


26/05/14
981
Geen, смысл в том чтобы снизить общую сложность первой реализации. Для решения задачи требуется изучить три-четыре новые для ТС вещи. Это много. Если можно обойтись без быстрого возведения, надо это сделать. Тут я согласен с mihaild.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 11:58 
Заслуженный участник
Аватара пользователя


01/09/13
4480
slavav
Да, но умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:05 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
Geen в сообщении #1553721 писал(а):
умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути
Простите, каким образом?
Быстрое возведение в степень - это алгоритм, позволяющий вычислить $n$-ю степень относительно любой ассоциативной операции на $O(\log n)$ её применений (в отличии от наивного цикла за $\Theta(n)$).
Умножение по модулю - подсчет произведения в кольце вычетов, использующий что если в качестве представителей элементов $\mathbb Z_n$ брать числа $0, \ldots, n - 1$, то представитель произведение есть остаток от деления произведения представителей на $n$.
Я знаю, что вы написанное выше знаете, но не понимаю, как можно сказать что это "один и тот же алгоритм", я не вижу между ними вообще никакой связи.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:13 
Заслуженный участник
Аватара пользователя


01/09/13
4480
mihaild в сообщении #1553722 писал(а):
как можно сказать что это "один и тот же алгоритм"

mihaild в сообщении #1553722 писал(а):
вычислить $n$-ю степень относительно любой ассоциативной операции на $O(\log n)$ её применений

Умножение это $n$-ая степень сложения.
А как иначе умножать по модулю? Например, как в примере выше, в однобайтной арифметике 3 умножить на 100 по модулю 101?

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:17 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
Geen в сообщении #1553723 писал(а):
А как иначе умножать по модулю?
А, я понял. Да, так можно реализовать умножение в случае, когда просто произведение сомножителей в арифметику не влезает (и мне это как-то в голову не приходило). Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:19 
Заслуженный участник
Аватара пользователя


01/09/13
4480
mihaild в сообщении #1553724 писал(а):
Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

Ну, а в JS, к примеру - нет :-)
И язык, кстати, в стартовом сообщении не задан.

-- 01.05.2022, 12:24 --

slavav в сообщении #1553590 писал(а):
Понадобятся простые, которые можно получить с помощью решета Эратосфена
.

Кстати, на JS сделал три вариации "расширения списка простых"....
Увы, "решето" победило :mrgreen:

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:26 
Заслуженный участник
Аватара пользователя


16/07/14
8826
Цюрих
Geen в сообщении #1553726 писал(а):
Ну, а в JS, к примеру - нет
Там есть даблы с 53 битами, которых тоже хватит:)
ТС писал на джаве, так что она доступна, и в ней 64-битные числа наверняка есть.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group