2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Функция Эйлера
Сообщение30.04.2022, 16:17 
Аватара пользователя
slavav в сообщении #1553590 писал(а):
Вам понадобится быстрое возведение в степень
Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 17:58 
Аватара пользователя
mihaild в сообщении #1553686 писал(а):
slavav в сообщении #1553590 писал(а):
Вам понадобится быстрое возведение в степень
Не понадобится, сумма всех степеней простых, входящих в $500000!$, меньше 2 миллионов.

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

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 19:28 
Согласен mihaild, можно без быстрого возведения в степень.

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

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 20:22 
Аватара пользователя
slavav в сообщении #1553691 писал(а):
Согласен mihaild, можно без быстрого возведения в степень.

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

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

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 20:45 
Аватара пользователя
Geen в сообщении #1553694 писал(а):
Двойку надо реально возводить в степень несколько тысяч.
Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 23:43 
Аватара пользователя
mihaild в сообщении #1553696 писал(а):
Для этого нужно возведение в степень по модулю. Для этого не нужно быстрое возведение в степень.

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

 
 
 
 Re: Функция Эйлера
Сообщение30.04.2022, 23:53 
Аватара пользователя
Geen в сообщении #1553702 писал(а):
Допустим в однобайтной арифметике нам надо возвести 3 в десятую степень по модулю 101 - что предлагается?
Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную. По модулю 83 - просто в цикле пишем x = (x * 3) % 83.

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 04:03 
Аватара пользователя
mihaild в сообщении #1553703 писал(а):
Не получится, нужно чтобы модуль - 1, умноженный на основание степени, влезал в переменную.

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

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 10:45 
Geen, смысл в том чтобы снизить общую сложность первой реализации. Для решения задачи требуется изучить три-четыре новые для ТС вещи. Это много. Если можно обойтись без быстрого возведения, надо это сделать. Тут я согласен с mihaild.

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 11:58 
Аватара пользователя
slavav
Да, но умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути.

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:05 
Аватара пользователя
Geen в сообщении #1553721 писал(а):
умножение по модулю и быстрое возведение в степень - один и тот же алгоритм, по сути
Простите, каким образом?
Быстрое возведение в степень - это алгоритм, позволяющий вычислить $n$-ю степень относительно любой ассоциативной операции на $O(\log n)$ её применений (в отличии от наивного цикла за $\Theta(n)$).
Умножение по модулю - подсчет произведения в кольце вычетов, использующий что если в качестве представителей элементов $\mathbb Z_n$ брать числа $0, \ldots, n - 1$, то представитель произведение есть остаток от деления произведения представителей на $n$.
Я знаю, что вы написанное выше знаете, но не понимаю, как можно сказать что это "один и тот же алгоритм", я не вижу между ними вообще никакой связи.

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:13 
Аватара пользователя
mihaild в сообщении #1553722 писал(а):
как можно сказать что это "один и тот же алгоритм"

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

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

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:17 
Аватара пользователя
Geen в сообщении #1553723 писал(а):
А как иначе умножать по модулю?
А, я понял. Да, так можно реализовать умножение в случае, когда просто произведение сомножителей в арифметику не влезает (и мне это как-то в голову не приходило). Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:19 
Аватара пользователя
mihaild в сообщении #1553724 писал(а):
Но в нашем случае это не нужно - нам доступна 64-битная арифметика, в которую влезает квадрат модуля.

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

-- 01.05.2022, 12:24 --

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

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

 
 
 
 Re: Функция Эйлера
Сообщение01.05.2022, 12:26 
Аватара пользователя
Geen в сообщении #1553726 писал(а):
Ну, а в JS, к примеру - нет
Там есть даблы с 53 битами, которых тоже хватит:)
ТС писал на джаве, так что она доступна, и в ней 64-битные числа наверняка есть.

 
 
 [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group