Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Gennadiy Usov
И там и там - Python.
Две формулы по три оператора - что проще?

Шо там пробовать? Сало - як сало.
25 окт 19, 18:49    [22002973]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Однако, 5% - это хорошее подспорье.

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

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

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

Такое бывает?
25 окт 19, 19:26    [22002996]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
Да яж говорю. Плевать на 5%.

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

Откуда:
Сообщений: 1347
Gennadiy Usov
mayton
5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

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

Уж если бахнуть так бахнуть.
И там и там - Python.
Две формулы по три оператора - что проще?
pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.
25 окт 19, 21:41    [22003056]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Малыхин Сергей
Member

Откуда: г. Курск
Сообщений: 729
Странно что в теме нет графика простых чисел в полярных координатах

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

Откуда:
Сообщений: 1834
Barlone
Gennadiy Usov
И там и там - Python.
Две формулы по три оператора - что проще?
pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.
Две программы написаны на питоне.

Эта часть программы для эвристического алгоритма
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

Откуда:
Сообщений: 1347
Gennadiy Usov,

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

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

Откуда: loopback
Сообщений: 42891
Gennadiy Usov
Barlone
Gennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
Хотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?

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

Но другие участники форума могут помочь тебе с портированием твоего кода на С.
Только его надо причесать. Выделить главную функцию и параметризировать ее.
26 окт 19, 13:58    [22003184]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

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

Откуда:
Сообщений: 1834
Barlone
На самом деле, даже не в скорости дело.
Тест Люка-Лемера для чисел Мерсенна детерменированный,
то есть доказано, что число, пошедшее тест - действительно простое.
В отличие от...
... более быстрого эвристического детерминированного алгоритма.

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

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

И кроме того, существует алгоритм, "работающий" быстрее теста Люка-Лемера.
26 окт 19, 19:37    [22003304]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1834
Barlone
Gennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
Поставил функцию, время работы алгоритма "просело".
Однако, за счет последующего улучшения алгоритма, над которым идёт работа,
время работы алгоритма превышает время работы теста Люка-Лемера примерно на 2 - 3 %.

Есть ещё сложности: на моём ПК время работы программы зависит от времени суток (?).
Поэтому стараюсь проводить сравнение сразу друг за другом.
27 окт 19, 07:18    [22003497]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

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

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

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

Откуда: loopback
Сообщений: 42891
Поскольку ты - новичек в анализе перформанса приложений то послушай совет.

Нажми Ctr+Shift+Esc. Для Windows будет такая картинка.

Картинка с другого сайта.

Ты должен запускать замер производительности когда "CPU Usage" будет близко к нулю.
Это означает что в данный момент нет посторонних активностей в ОС Windows.
А там их бывает много.

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

Понаблюдай насколько оно загружено.
27 окт 19, 10:58    [22003531]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

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

Запустил Люка-Лемера.
Ядер у меня 4.(четыре картинки сверху). Все загружены. одно очень сильно.Одно слабо.
ЦП - 26-29%
27 окт 19, 11:34    [22003558]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42891
В форуме С++

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

Откуда:
Сообщений: 1834
mayton
В форуме С++

Дано натуральное число P. Определить все совершенные числа, не превосходящие P
И что?
Определяет и определяет.
Обычное деление на множители.
28 окт 19, 17:07    [22004449]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

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

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

Откуда:
Сообщений: 1834
mayton
Вот ты спрашивал про С++. Вот тебе и С++.
Типы данных - от 32 до 64 бит вобщем.
То что обзывают int.
Не спрашивал я про С++, про С, про ...
И какая разница, какой язык применяется при расчётах.
Главное: чтобы этот язык работал с большими числами.

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

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

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

Откуда:
Сообщений: 1834
При работе с эвристическим алгоритмом при определении чисел Мерсенна 21980061 меня удивляло:
почему для проверки числа достаточно только одного раунда (одно обращение к оператору pow).

Проведённые исследования 22015600 показали, что числа Мерсенна входят в рабочий диапазон этих чисел Мерсенна.

Поэтому для проверки числа Мерсенна достаточно одно обращение к оператору pow (с основанием степени 3).
14 ноя 19, 18:28    [22016510]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3]      все
Все форумы / Программирование Ответить