ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм (тест простоты) для определения очень больших простых чисел
1 сообщений из 76, страница 4 из 4
  4  все
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39893132
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Gennadiy Usov
Нашел для Питона распечатку программы pow:
http://qaru.site/questions/132239/how-did-python-implement-the-built-in-function-pow
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
def pow_mod(x, y, z):				
	"Calculate (x ** y) % z efficiently."			
	number = 1			
	while y:			
		if y & 1:		
			number = number * x % z	
		y >>= 1		
		x = x * x % z		
	return number

Это самая быстрая программа для Питона для pow?
Решил ещё раз исследовать эту программу.

Если проверяемое число будет немного меньше 2^n - 1, то данная программа вычисляет 2*n умножений по модулю.

Эвристический алгоритм 22015600 для аналогичного числа вычисляет n + 1 умножений по модулю.

Это объясняет то, что эвристический алгоритм работает быстрее алгоритма pow для чисел, которые немного меньше 2^n - 1.
...
Рейтинг: 0 / 0
22.11.2019, 19:14
| Ответить | Цитировать | Написать  
1 сообщений из 76, страница 4 из 4
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм (тест простоты) для определения очень больших простых чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]