Алгоритм (тест простоты) для определения очень больших простых чисел / Страница 3 / Программирование / Sql.ru

Добро пожаловать в форум, Guest >> Войти \| Регистрация \| Поиск \| Правила \|			В избранное \| Подписаться
Все форумы / Программирование

Топик располагается на нескольких страницах: ←Ctrl назад 1 2 [3] 4 вперед Ctrl→ все

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

mayton
Member

Откуда: loopback
Сообщений: 51153

Gennadiy Usov
И там и там - Python. Две формулы по три оператора - что проще?

Шо там пробовать? Сало - як сало.

25 окт 19, 18:49 [22002973] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Gennadiy Usov Member Откуда: Сообщений: 2357	Однако, 5% - это хорошее подспорье. При 20 часах работы ПК экомится 1 час работы! (или вместо 20 чисел можно проверить 21 число за то же время.)
25 окт 19, 19:11 [22002987] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Для крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.
25 окт 19, 19:20 [22002993] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

mayton
Для крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.

Просто так отказаться от алгоритма, который считает на 5% быстрее?
Всего-то: каких-то 3 оператора меняются на 3 других оператора.

Такое бывает?

25 окт 19, 19:26 [22002996] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Да яж говорю. Плевать на 5%. Это не стоит никакого апгрейта. Тут не то что алгоритм. Тут люди ключи годами не хотят менять.
25 окт 19, 19:33 [22003002] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Barlone
Member

Откуда:
Сообщений: 1451

Gennadiy Usov

mayton

5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

Вообще интересно было-бы рассматривать 1000% и больше. Этож криптография мать ее так.
Полумеры нам не нужны.

Уж если бахнуть так бахнуть.

И там и там - Python.
Две формулы по три оператора - что проще?

pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.

25 окт 19, 21:41 [22003056] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Малыхин Сергей Member Откуда: г. Курск Сообщений: 743	Странно что в теме нет графика простых чисел в полярных координатах [youtube=]
25 окт 19, 23:45 [22003081] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

Barlone

Gennadiy Usov
И там и там - Python. Две формулы по три оператора - что проще?

Две программы написаны на питоне.

Эта часть программы для эвристического алгоритма

a1 = 3					
while p <= P:					
	Mp = pow(2, p) -1 				
	t1 = (Mp -1)//2				
	x = pow(a1, t1, Mp)				
	if x == Mp- 1:				
		print (p)			
					
	p  +=2

Эта часть программы для теста Люка-Лемера

while p <= P:					
	Mp = pow(2, p) -1 				
	c = 4				
	i = 2				
	while i <= p-1:				
		c =(c*c-2) % Mp 			
		i += 1			
	if c == 0:				
		print(p)			
	p +=2

И где нечестное сравнение?

26 окт 19, 07:25 [22003102] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	Gennadiy Usov, Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
26 окт 19, 08:08 [22003109] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

Barlone
Gennadiy Usov, Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно

Хотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?

26 окт 19, 09:03 [22003121] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

mayton
Member

Откуда: loopback
Сообщений: 51153

Gennadiy Usov

Barlone
Gennadiy Usov, Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно

Хотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?

В целом да. Но тебе на сях писать не надо. Там - другие сложности в которых ты потонешь.

Но другие участники форума могут помочь тебе с портированием твоего кода на С.
Только его надо причесать. Выделить главную функцию и параметризировать ее.

26 окт 19, 13:58 [22003184] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	На самом деле, даже не в скорости дело. Тест Люка-Лемера для чисел Мерсенна детерменированный, то есть доказано, что число, пошедшее тест - действительно простое. В отличие от...
26 окт 19, 18:41 [22003293] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

Barlone
На самом деле, даже не в скорости дело. Тест Люка-Лемера для чисел Мерсенна детерменированный, то есть доказано, что число, пошедшее тест - действительно простое. В отличие от...

... более быстрого эвристического детерминированного алгоритма.

На то он и эвристический алгоритм, что он помогает в расчётах, и его не обязательно доказывать.
Главное - проверено на небольших числах:

Найденные эвристическим алгоритмом простые числа совпадают с простыми числами Мерсенна
(ранее найденными тестом Люка-Лемера).

И кроме того, существует алгоритм, "работающий" быстрее теста Люка-Лемера.

26 окт 19, 19:37 [22003304] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

Barlone
Gennadiy Usov, Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно

Поставил функцию, время работы алгоритма "просело".
Однако, за счет последующего улучшения алгоритма, над которым идёт работа,
время работы алгоритма превышает время работы теста Люка-Лемера примерно на 2 - 3 %.

Есть ещё сложности: на моём ПК время работы программы зависит от времени суток (?).
Поэтому стараюсь проводить сравнение сразу друг за другом.

27 окт 19, 07:18 [22003497] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Может антивирус работает параллельно.
27 окт 19, 09:33 [22003509] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

mayton
Может антивирус работает параллельно.

Может и антивирус. Давно не обновлял, хотя есть напоминания.
Но вчера и сегодня могут отличаться на 30 сек для программы на 13 минут.

Компьютер старенький...

27 окт 19, 10:09 [22003521] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Поскольку ты - новичек в анализе перформанса приложений то послушай совет. Нажми Ctr+Shift+Esc. Для Windows будет такая картинка. Ты должен запускать замер производительности когда "CPU Usage" будет близко к нулю. Это означает что в данный момент нет посторонних активностей в ОС Windows. А там их бывает много. Понаблюдай как коррелирует загрузка с твоем процессом. Возможно ты увидешь как 1 ядро будет загружено (из 8 возможных на картинке). Понаблюдай насколько оно загружено.
27 окт 19, 10:58 [22003531] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

mayton
Понаблюдай как коррелирует загрузка с твоем процессом. Возможно ты увидешь как 1 ядро будет загружено (из 8 возможных на картинке). Понаблюдай насколько оно загружено.

Спасибо!

Запустил Люка-Лемера.
Ядер у меня 4.(четыре картинки сверху). Все загружены. одно очень сильно.Одно слабо.
ЦП - 26-29%

27 окт 19, 11:34 [22003558] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	В форуме С++ Дано натуральное число P. Определить все совершенные числа, не превосходящие P
28 окт 19, 16:55 [22004437] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

mayton
В форуме С++ Дано натуральное число P. Определить все совершенные числа, не превосходящие P

И что?
Определяет и определяет.
Обычное деление на множители.

28 окт 19, 17:07 [22004449] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Gennadiy Usov Member Откуда: Сообщений: 2357	Может быть, было бы интереснее сделать двухступенчатое деление: сначала определяются простые числа для деления, а потом само деление. И всё это идет по наростающей.
28 окт 19, 17:11 [22004458] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Вот ты спрашивал про С++. Вот тебе и С++. Типы данных - от 32 до 64 бит вобщем. То что обзывают int.
28 окт 19, 17:16 [22004465] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]

Gennadiy Usov
Member

Откуда:
Сообщений: 2357

mayton
Вот ты спрашивал про С++. Вот тебе и С++. Типы данных - от 32 до 64 бит вобщем. То что обзывают int.

Не спрашивал я про С++, про С, про ...
И какая разница, какой язык применяется при расчётах.
Главное: чтобы этот язык работал с большими числами.

Ведь разговор идёт об алгоритме, о тесте, о формуле.

А как всё это реализовать, каждый решает на удобном ему языке.
(естественно, с учетом быстродействия).

28 окт 19, 18:17 [22004510] Ответить | Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
mayton Member Откуда: loopback Сообщений: 51153	Как будет угодно.
28 окт 19, 18:19 [22004513] Ответить \| Цитировать Сообщить модератору

Re: Алгоритм (тест простоты) для определения очень больших простых чисел [new]
Gennadiy Usov Member Откуда: Сообщений: 2357	При работе с эвристическим алгоритмом при определении чисел Мерсенна 21980061 меня удивляло: почему для проверки числа достаточно только одного раунда (одно обращение к оператору pow). Проведённые исследования 22015600 показали, что числа Мерсенна входят в рабочий диапазон этих чисел Мерсенна. Поэтому для проверки числа Мерсенна достаточно одно обращение к оператору pow (с основанием степени 3).
14 ноя 19, 18:28 [22016510] Ответить \| Цитировать Сообщить модератору

Топик располагается на нескольких страницах: ←Ctrl назад 1 2 [3] 4 вперед Ctrl→ все

Все форумы / Программирование

Ссылка на сообщение

Ссылка (включая название темы)

Ссылка (URL)