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

Откуда:
Сообщений: 1846
Gennadiy Usov
mayton
Или ты имел в виду дистрибутивность операции mod?
Да. Может быть можно получить функцию вида
x mod(c) +- y mod(d) +- (что-то), или другие опперации?
Вопрос странный. Формулу вида x mod(c) +- y mod(d) +- (что-то) получитьможно всегда.
Надо тщательнЕе расставлять скобки, а то догадки разбегаются как тараканы:
b (mod x) = c + (d (mod x))
b (mod x) = (c + d)(mod x)
b (mod x) = c(mod x) + d (mod x)
((c + d)(mod x))(mod x)
Здесь только один вариант верен для натуральных в общем случае.
А вообще, найти опровергающие примеры было в тягость, школьная арифметика, не царское это дело.
13 окт 19, 14:12    [21993052]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
exp98
Gennadiy Usov
Да. Может быть можно получить функцию вида
x mod(c) +- y mod(d) +- (что-то), или другие опперации?
Вопрос странный. Формулу вида x mod(c) +- y mod(d) +- (что-то) получитьможно всегда.
Надо тщательнЕе расставлять скобки, а то догадки разбегаются как тараканы:
b (mod x) = c + (d (mod x))
b (mod x) = (c + d)(mod x)
b (mod x) = c(mod x) + d (mod x)
((c + d)(mod x))(mod x)
Здесь только один вариант верен для натуральных в общем случае.
А вообще, найти опровергающие примеры было в тягость, школьная арифметика, не царское это дело.
Здесь надо было связать сообщение с предыдущим сообщением:

Если есть
a mod (x+y),
то можно ли это выражение разложить на
a1 (mod x) и a2 (mod y)?
13 окт 19, 16:59    [21993099]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov, нет конечно
Легко найти пару чисел, равных по модулям a и b, но при этом неравных по модулю a+b.
Или наоборот, пару чисел, равны по модулю a+b, но неравных по модулям a и b.
13 окт 19, 20:35    [21993233]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Убежден что Геннадия ведет какая-то интуиция. И она ему подсказывает искать формулы
ускоренного сложения чисел по модулю. Очевидно что за этим стоит некая оптимизационная
цель.
13 окт 19, 21:46    [21993261]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
- Гена, знаешь, когда идёшь по рельсам,то никогда не заблудишься.
- Эт ты пральна сказал, Чебурашка.
(цэ)
13 окт 19, 23:05    [21993281]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Здесь больше подходит диалог Алисы и Чеширского кота

— Скажите, пожалуйста, куда мне отсюда идти?
— А куда ты хочешь попасть? — ответил Кот.
— Мне все равно... — сказала Алиса.
— Тогда все равно куда и идти, — заметил Кот.
— Только бы попасть куда-нибудь, — пояснила Алиса.
— Куда-нибудь ты обязательно попадешь, — сказал Кот. — Нужно только достаточно долго идти.
13 окт 19, 23:55    [21993300]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Нашел для Питона распечатку программы pow:
http://qaru.site/questions/132239/how-did-python-implement-the-built-in-function-pow

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?
16 окт 19, 09:20    [21995132]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov,
"Быстрая" и "для питона" - это оксюморон.
В природе существуют https://ru.wikipedia.org/wiki/Алгоритм_Монтгомери и https://ru.wikipedia.org/wiki/Умножение_Карацубы но это не для питона
16 окт 19, 12:18    [21995349]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Для прототипирования Питона вполне достаточно. Если мы упрёмся именно в процессорные ресурсы для умножения
или деления то можно подключать к питону библиотечки-ускорители.

Но об этом еще рано говорить IMHO. Мы же не делаем новый стандарт несимметричного шифра.

Мы - экспериментируем.
16 окт 19, 12:29    [21995366]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Убежден что Геннадия ведет какая-то интуиция. И она ему подсказывает искать формулы
ускоренного сложения чисел по модулю. Очевидно что за этим стоит некая оптимизационная
цель.
Расчёты на ПК по определению простых чисел Мерсенна показали, что практически за одно и тоже время определяют простые числа Мерсенна
как тест Люка-Лемера, так и эвристический алгоритм (одна формула вида pow).

Поэтому ставится задачка:

доработать алгоритм для процедуры pow таким образом, чтобы эвристический алгоритм при определении простых чисел Мерсенна работал быстрее, чем тест Люка-Лемера.
mayton
Если мы упрёмся именно в процессорные ресурсы для умножения
или деления то можно подключать к питону библиотечки-ускорители.
Но об этом еще рано говорить IMHO. Мы же не делаем новый стандарт несимметричного шифра.
Мы - экспериментируем.
Скорее всего, подключение библиотечек-ускорителей мало что даст.

Ведь идёт поиск алгоритма для программы, а не поиск самой программы.

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

Откуда:
Сообщений: 1840
Если сравнивать тест Люка-Лемера и процедуру типа pow для чисел Мерсенна Mn, то оказывается, что :
- в каждом тесте количество циклов равно n;
- в каждом тесте в цикле идет умножение х = х*х;
- в тесте Люка-Лемера от числа х отнимается 2 для каждого элемента цикла;
- в pow число х умножается на предыдущее число (number) для каждого элемента цикла;
- и после каждой операции идёт операция %.

Данные рассуждения говорят о том, что скорости работы теста Люка-Лемера и процедуры pow почти равны,
о чём уже говорилось на топике по результатам работы прораммы.
17 окт 19, 06:08    [21995992]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Gennadiy Usov, я несколько раз обращался к тебе с просьбой собрать отклик твоего кода через равные
промежутки интервалов. Я хотел построить график. И по нему оценить асимптоматику. Это важно.
Важные даже не числа а форма графика. Парабола. Экспонента. Или x в степени x как некая ссылка
на комбинаторную сложность. Но мне показалось что данные у тебя беспорядочны и их мало и я отбросил
эту затею.

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

Откуда:
Сообщений: 1840
mayton
А асимптоматику надо считать.
В данном топике рассматривается задачка
построения алгоритма для определения очень больших простых чисел,
например, простых чисел Мерсенна, простых чисел, расположенных недалеко от чисел Мерсенна.

Программа на ПК показала, что эвристический алгоритм 21980061(одна формула) показывает результаты,
сравнимые с результатами работы теста Люка-Лемера:
- количество и перечень простых чисел Mn , время работы.
Проверено до n = 20000 (далее - ПК очень долго считает).

Как быть здесь с асимптоматикой?
17 окт 19, 13:14    [21996479]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

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

Откуда:
Сообщений: 1840
mayton
Если полином то хорошо.
Алгоритм для pow - полином?
17 окт 19, 13:49    [21996516]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Сложно сказать как нам поможет это знание.
17 окт 19, 14:03    [21996537]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Сравнил pow из 21995132 и оказалось,
что этот алгоитм работает в два раза медленнее pow из стандартной библиотеки Питона.

Может быть есть ещё алгоритм для pow?
17 окт 19, 18:24    [21996850]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Сравнил pow из 21995132 и оказалось,
что этот алгоитм работает в два раза медленнее pow из стандартной библиотеки Питона.

Может быть есть ещё алгоритм для pow?
Учитывая, что pow из стандартной библиотеки питона написан не на питоне, даже удивительно, что всего в два раза медленнее...
17 окт 19, 20:11    [21996908]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Алгоритмы есть конечно - вот можно http://cacr.uwaterloo.ca/hac/about/chap14.pdf посмотреть
17 окт 19, 21:03    [21996939]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Вот pow из питона https://github.com/python/cpython/blob/master/Objects/longobject.c#L4243
а тут gmp https://gmplib.org/repo/gmp/file/tip/mpn/generic/powm.c
17 окт 19, 21:19    [21996947]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Вот pow из питона https://github.com/python/cpython/blob/master/Objects/longobject.c#L4243
а тут gmp https://gmplib.org/repo/gmp/file/tip/mpn/generic/powm.c
Если это питон, то почему скобки {?
17 окт 19, 21:41    [21996956]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov,
Интерпретатор питона написан на С. Сюрприз!
18 окт 19, 06:32    [21997019]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм (тест простоты) для определения очень больших простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Немного отдохнул, и решил сравнить два теста: тест Люка-Лемера и эвристический алгоритм21980061.

Составил две программы на Питоне и выбрал интервал чисел Мерсенна от 11 до 5000 без применения делителей с шагом 2.

Получились следующие результаты:
для теста Люка-Лемера определение простых чисел Мерсенна шло 14 мин. 05 сек.
2019-10-25-15.11.25
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
2019-10-25-15.25.30 
Для эвристического алгоритма определение простых чисел Мерсенна шло 13 мин. 20 сек.
2019-10-25-15.31.05
13
17
19
31
61
89
107
127
521
607
1279
2203
2281
3217
4253
4423
2019-10-25-15.44.25 
То есть, эвристический алгоритм «работает» на 5% быстрее, чем тест Люка-Лемера.

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

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

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

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

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

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

Уж если бахнуть так бахнуть.
И там и там - Python.
Две формулы по три оператора - что проще?
25 окт 19, 18:46    [22002972]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Программирование Ответить