ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм (тест простоты) для определения очень больших простых чисел
25 сообщений из 76, страница 3 из 4
  3  все
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881738
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovИ там и там - Python.
Две формулы по три оператора - что проще?
Шо там пробовать? Сало - як сало.
...
Рейтинг: 0 / 0
25.10.2019, 18:49
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881746
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Однако, 5% - это хорошее подспорье.

При 20 часах работы ПК экомится 1 час работы!
(или вместо 20 чисел можно проверить 21 число за то же время.)
...
Рейтинг: 0 / 0
25.10.2019, 19:11
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881751
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Для крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.
...
Рейтинг: 0 / 0
25.10.2019, 19:20
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881754
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonДля крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.Просто так отказаться от алгоритма, который считает на 5% быстрее?
Всего-то: каких-то 3 оператора меняются на 3 других оператора.

Такое бывает?
...
Рейтинг: 0 / 0
25.10.2019, 19:26
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881757
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да яж говорю. Плевать на 5%.

Это не стоит никакого апгрейта. Тут не то что алгоритм. Тут люди ключи годами не хотят менять.
...
Рейтинг: 0 / 0
25.10.2019, 19:33
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881797
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy Usovmayton5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

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

Уж если бахнуть так бахнуть.И там и там - Python.
Две формулы по три оператора - что проще?pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.
...
Рейтинг: 0 / 0
25.10.2019, 21:41
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881815
Фотография Малыхин Сергей
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Малыхин Сергей
Участник
Странно что в теме нет графика простых чисел в полярных координатах

[youtube=
YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
25.10.2019, 23:45
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881830
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy UsovИ там и там - Python.
Две формулы по три оператора - что проще?pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.Две программы написаны на питоне.

Эта часть программы для эвристического алгоритма
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
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

Эта часть программы для теста Люка-Лемера
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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

И где нечестное сравнение?
...
Рейтинг: 0 / 0
26.10.2019, 07:25
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881835
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy Usov,

Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честно
...
Рейтинг: 0 / 0
26.10.2019, 08:08
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881845
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честноХотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?
...
Рейтинг: 0 / 0
26.10.2019, 09:03
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881868
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovBarloneGennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честноХотите сказать, что цикл на Питоне работает медленнее цикла на С, на котором написана процедура pow?
В целом да. Но тебе на сях писать не надо. Там - другие сложности в которых ты потонешь.

Но другие участники форума могут помочь тебе с портированием твоего кода на С.
Только его надо причесать. Выделить главную функцию и параметризировать ее.
...
Рейтинг: 0 / 0
26.10.2019, 13:58
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881928
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
На самом деле, даже не в скорости дело. Тест Люка-Лемера для чисел Мерсенна детерменированный , то есть доказано, что число, пошедшее тест - действительно простое. В отличие от...
...
Рейтинг: 0 / 0
26.10.2019, 18:41
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39881932
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneНа самом деле, даже не в скорости дело.
Тест Люка-Лемера для чисел Мерсенна детерменированный ,
то есть доказано, что число, пошедшее тест - действительно простое.
В отличие от...... более быстрого эвристического детерминированного алгоритма.

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

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

И кроме того, существует алгоритм, "работающий" быстрее теста Люка-Лемера .
...
Рейтинг: 0 / 0
26.10.2019, 19:37
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882008
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy Usov,
Вызов pow против цикла на питоне. Вместо pow подставьте свою функцию из 21995132 - это будет честноПоставил функцию, время работы алгоритма "просело".
Однако, за счет последующего улучшения алгоритма, над которым идёт работа,
время работы алгоритма превышает время работы теста Люка-Лемера примерно на 2 - 3 %.

Есть ещё сложности: на моём ПК время работы программы зависит от времени суток (?).
Поэтому стараюсь проводить сравнение сразу друг за другом.
...
Рейтинг: 0 / 0
27.10.2019, 07:18
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882015
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Может антивирус работает параллельно.
...
Рейтинг: 0 / 0
27.10.2019, 09:33
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882022
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonМожет антивирус работает параллельно.Может и антивирус. Давно не обновлял, хотя есть напоминания.
Но вчера и сегодня могут отличаться на 30 сек для программы на 13 минут.

Компьютер старенький...
...
Рейтинг: 0 / 0
27.10.2019, 10:09
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882028
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Поскольку ты - новичек в анализе перформанса приложений то послушай совет.

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



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

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

Понаблюдай насколько оно загружено.
...
Рейтинг: 0 / 0
27.10.2019, 10:58
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882041
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПонаблюдай как коррелирует загрузка с твоем процессом. Возможно ты увидешь как 1 ядро будет загружено (из 8 возможных на картинке).
Понаблюдай насколько оно загружено.Спасибо!

Запустил Люка-Лемера.
Ядер у меня 4.(четыре картинки сверху). Все загружены. одно очень сильно.Одно слабо.
ЦП - 26-29%
...
Рейтинг: 0 / 0
27.10.2019, 11:34
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882384
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В форуме С++

Дано натуральное число P. Определить все совершенные числа, не превосходящие P
...
Рейтинг: 0 / 0
28.10.2019, 16:55
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882391
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonВ форуме С++

Дано натуральное число P. Определить все совершенные числа, не превосходящие P И что?
Определяет и определяет.
Обычное деление на множители.
...
Рейтинг: 0 / 0
28.10.2019, 17:07
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882393
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Может быть, было бы интереснее сделать двухступенчатое деление:
сначала определяются простые числа для деления, а потом само деление.
И всё это идет по наростающей.
...
Рейтинг: 0 / 0
28.10.2019, 17:11
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882397
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вот ты спрашивал про С++. Вот тебе и С++.
Типы данных - от 32 до 64 бит вобщем.
То что обзывают int.
...
Рейтинг: 0 / 0
28.10.2019, 17:16
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882424
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonВот ты спрашивал про С++. Вот тебе и С++.
Типы данных - от 32 до 64 бит вобщем.
То что обзывают int.Не спрашивал я про С++, про С, про ...
И какая разница, какой язык применяется при расчётах.
Главное: чтобы этот язык работал с большими числами.

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

А как всё это реализовать, каждый решает на удобном ему языке.
(естественно, с учетом быстродействия).
...
Рейтинг: 0 / 0
28.10.2019, 18:17
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39882427
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Как будет угодно.
...
Рейтинг: 0 / 0
28.10.2019, 18:19
| Ответить | Цитировать | Написать  
Алгоритм (тест простоты) для определения очень больших простых чисел
    #39889246
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
При работе с эвристическим алгоритмом при определении чисел Мерсенна 21980061 меня удивляло:
почему для проверки числа достаточно только одного раунда (одно обращение к оператору pow).

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

Поэтому для проверки числа Мерсенна достаточно одно обращение к оператору pow (с основанием степени 3).
...
Рейтинг: 0 / 0
14.11.2019, 18:28
| Ответить | Цитировать | Написать  
25 сообщений из 76, страница 3 из 4
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм (тест простоты) для определения очень больших простых чисел
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39882393&tid=1339872]:
 0ms
get settings:
 9ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 344ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 66ms
get tp. blocked users:
 1ms
others: 242ms
total:  695ms
созд. / загр.: 695ms
x
x
Закрыть


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