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

Откуда: loopback
Сообщений: 41808
 		Говоришь загадками. Какой блок? Сколько у тебя получилось?
12 сен 19, 09:36    [21969127]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Говоришь загадками. Какой блок? Сколько у тебя получилось?
Мне удобно работать блоками по 50 000 000 чисел. Это видно по программе. Следующий блок от 50 000 005 и ещё 50 000 000 чисел. И т.д.

В первом блоке определилось 3 001 132 простых чисел.
От 50 000 005 (начало второго блока) до 68 200 187 найдено 1 017 273 простых числа.

Итого на диапазоне от 5 до 68 200 187 было найдено 4 018 405 простых чисел.
12 сен 19, 13:24    [21969405]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 
Primes detected      : 4018407
Twin primes          : 314068
Triplet primes       : 80895
Range                : [2..68200187]
Memory cache used    : 32768 K
Square root algorithm: Henry Warren's 'isqrt64'
AVG speed generation : 52187 units/sec
Elapsed time         : 77 sec

Итого 4018407 минус 2 числа (2 и 3) получается 4 018 405

Теперь поговорим об оптимизациях. Вырожденный Миллер Рабин превращается в метод грубой силы?

Или нет?
12 сен 19, 15:20    [21969571]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Теперь поговорим об оптимизациях.
Вырожденный Миллер Рабин превращается в метод грубой силы?
Или нет?
Тест Миллера-Рабина (сами формулы) остаётся в силе.

Просто меняется последовательность поиска параметров для формул теста Миллера-Рабина.

В эвристическом алгоритме:
Для 50 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина.
Для других 25 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина, а также иногда имеет место 2-й этап (автоматически) - ещё 9 раундов (автоматически - может быть меньше) .
И т.д.

По тесту Миллера-Рабина:
количество раундов равно log( p ).
И считать по двум формулам,
И то - то ли простое число, то ли нет.

Разница есть?

Это для начала оптимизации...
12 сен 19, 15:38    [21969586]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Ещё одно наблюдение при тестировании программы.

Предварительное определение множителей чисел (метод грубой силы до определённого множителя)
позволяет уменьшить количество применяемых циклов для величины s2 21968895,
что помогает уменьшить среднее время при определении простоты для каждого из этих чисел.
12 сен 19, 21:07    [21969892]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Решил проверить программу на числах 2^1024.

Для этого поменял немного заставку программы - смотрел 5000 чисел после 2^1024:
Q = 2**(1024)								
p1 =   5								
P1 = p1 + 5000								
while p1 <=P1:								
	p = Q + p1							
	num =  delit_vse_pre(p, 160)	# проверка на множители до 160						
								
	if num == 0:							
		x =   pow(2,p-1, p)		# тест Ферма				
		if x == 1:						
			print (Q -p)


Получилось:
+
2019-09-13-06.04.01
-643
-blok-a- 643 -s- 1
-1081
-blok-a- 1081 -s- 3
-2113
-blok-a- 2113 -s- 6
-2715
-blok-a- 2715 -s- 1
-3711
-blok-a- 3711 -s- 1
-N blok- 5

2019-09-13-06.04.09
13 сен 19, 06:12    [21969978]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Так что, критика и обсуждения закончились?

А как же дежурные фразы, mayton 21908442?
13 сен 19, 16:41    [21970552]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Сколько времени он у тебя работал?
13 сен 19, 17:15    [21970591]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Сколько времени он у тебя работал?
Эвристический алгоритм для формул теста Миллера-Рабина окончательно "сформировался" дня три назад.

До этого были пробные тесты для s = 1, для s = 2, для s = 3.
После этого был пробный тест для всех s.

Поскольку ПК - старенький, то прогон проводился для отдельных s до 250 000 00, а для всех s - до 68 000 000.
Стараюсь запускать программу тогда, когда нахожусь рядом.

Поскольку для небольших n всё проходит, то наступает "эвристика". Можно распространять на большие числа.

В частности, был прогон для чисел около 2^1024.
13 сен 19, 17:47    [21970615]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Надо оценить асимптоматику.
Не вычислить. А именно оценить.
Для этого надо сделать штук 5 запусков
С линейно меняющимся параметром
И засечь с точностью до секунд время.
После этого посмотреть в Экселе график
И прикинуть что это. Полином? Экспонента? Etc.
13 сен 19, 19:00    [21970664]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Надо оценить асимптоматику.
Не вычислить. А именно оценить.
Для этого надо сделать штук 5 запусков
С линейно меняющимся параметром
И засечь с точностью до секунд время.
После этого посмотреть в Экселе график
И прикинуть что это. Полином? Экспонента? Etc.
Ваши предложения по диапазонам?

Нужно ли предварительное деление?

Нужен ли предварительный тест Ферма?
13 сен 19, 19:02    [21970667]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Выше ты делил по 50 лимонов.

Вот пускай так и будет.

По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько?
13 сен 19, 20:03    [21970714]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Основные параметры эвристического алгоритма:
- число значений s2;
- число раундов при одном s2, после которого узнаём, что число составное ( остаток не равен ни 1, ни (n - 1))
- число значений s2, после которых определяется простое число.

По каждому значению можно определить мax или min на некотором интервале чисел (у меня либо 200000, либо 1000000).
13 сен 19, 20:05    [21970716]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Выше ты делил по 50 лимонов.
Вот пускай так и будет.
По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько?
Ферма по любому быстрее определяет множество чисел, среди которых все простые числа.

Ведь тест Ферма - это один раунд.
Тест Миллера-Рабина - это несколько раундов.
Причём, это по всем числам: и составным, и простым.

Мне видится следующий подход: тест Ферма ограничивает количество чисел, среди которых все простые числа,
а тест Миллера-Рабина (с эвристическим алгоритмом или с другим алгоритмом) "зачищает" полученные числа,
выбирая из них только простые числа.

Это моё видение процесса поиска простых чисел,
при этом ещё в начале процесса поиска - деление на небольшие множители.

Можно рассмотреть вопрос применения одного эвристического алгоритма для формул теста Миллера-Рабина,
и сравнить результат применения алгоритма с результатами теста Ферма.
13 сен 19, 20:17    [21970721]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Сейчас у меня заканчилась работа программы для второго диапазона: от 50 000 005 до 100 000 005.
На этом диапазоне получено 2760321 простых чисел.
Программа не ошиблась - среди полученных простых чисел нет составных чисел.

Вначале программы идёт проверка на множители до 643 (так решил),
далее тест Ферма,
далее алгоритм.

И даже в таком виде диапазон из 1 000 000 чисел рядом с числом 100 000 000 программа "проходит" за 3 минуты.

Применение множителей и Ферма, как я уже говорил ранее,
позволило уменьшить количество изменений значений s2 для одного числа до 4 (ранее были случаи 7 ).

Основное значение количества раундов (а1) при одном значении s2,
когда выявляется составное число, в основном - значение 3,
но есть случаи, когда встречается значение 5, очень редко 7.
(обращаю внимание - значения нечётные)
13 сен 19, 20:31    [21970727]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Вот ты мастак все усложнять.

Я хотел посмотреть имеет ли смысл изучать твой Питонский исходник. И хотел посмотреть его отклик.

Знаешь как в радиоэлектронике. Подали входной сигнал. Встали осцилографом на выход. Посмотрели.
Поменяли сигнал и т д.
13 сен 19, 20:36    [21970730]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Убрал все добавления, оставил один эвристический алгоритм.

Программа считает.
На 2 000 000 чисел 148932 простых.
Время работы 1,5 минуты.
Программа продолжает работу...
13 сен 19, 21:02    [21970735]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Нужно хотя-бы 5 точек на плоскости чтоб мы построили график зависимости времени от параметра алгоритма.
13 сен 19, 22:32    [21970755]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Геннадий? Куда-то пропал. Или построение 5 измерений так долго?
14 сен 19, 14:05    [21970891]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Геннадий? Куда-то пропал. Или построение 5 измерений так долго?
Не пропал.

Продолжаю считать. Уже прошёл (с остановками) число 153 000 000.
Есть интересное число 133800661, разбирался с ним.
14 сен 19, 14:14    [21970899]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Так долго? Ладно побей на интервалы поменьше.
14 сен 19, 15:37    [21970927]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Так долго? Ладно побей на интервалы поменьше.
В начале на диапазон в 1 000 000 чисел уходило 1,5 минуты.
На отметке 175 000 000 уходит уже 2,5 минуты
14 сен 19, 15:43    [21970930]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
 		Ну дык... цифры есть? 4-5 штук.
14 сен 19, 15:45    [21970931]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
mayton
Ну дык... цифры есть? 4-5 штук.
Сейчас основные цифры, которые печатаются после мини диапазона (1 000 000), это:
- на каком раунде (а1) выявляется составное число (максимальное по мини диапазону);
- сколько может быть значений s2 (максимум на мини диапазоне) - дополнительные 9 раундов на каждое значение.

На текущий момент max a1 - очень редко 7, один раз - 11,
а для s2 - почти всегда 4.
14 сен 19, 16:14    [21970943]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1694
 		Прошел 250 000 000.

В конце этого диапазона время обработки мини диапазона увеличилась до 3 мин. 09 сек.

На текущий момент max a1 - очень редко 7,
а для s2 - почти всегда 4, редко 5,6, один раз 8.
14 сен 19, 19:29    [21970980]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: ←Ctrl  назад   1 [2] 3   вперед  Ctrl→      все
Все форумы / Программирование Ответить