Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: ←Ctrl назад 1 [2] 3 4 5 6 7 8 9 10 вперед Ctrl→ все |
mayton Member Откуда: loopback Сообщений: 51128 |
Говоришь загадками. Какой блок? Сколько у тебя получилось? |
12 сен 19, 09:36 [21969127] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
В первом блоке определилось 3 001 132 простых чисел. От 50 000 005 (начало второго блока) до 68 200 187 найдено 1 017 273 простых числа. Итого на диапазоне от 5 до 68 200 187 было найдено 4 018 405 простых чисел. |
||
12 сен 19, 13:24 [21969405] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
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] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Просто меняется последовательность поиска параметров для формул теста Миллера-Рабина. В эвристическом алгоритме: Для 50 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина. Для других 25 % чисел достаточно для проверки только 9 раундов (автоматически - может быть меньше) расчета по формулам теста Миллера-Рабина, а также иногда имеет место 2-й этап (автоматически) - ещё 9 раундов (автоматически - может быть меньше) . И т.д. По тесту Миллера-Рабина: количество раундов равно log( p ). И считать по двум формулам, И то - то ли простое число, то ли нет. Разница есть? Это для начала оптимизации... |
||
12 сен 19, 15:38 [21969586] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Ещё одно наблюдение при тестировании программы. Предварительное определение множителей чисел (метод грубой силы до определённого множителя) позволяет уменьшить количество применяемых циклов для величины s2 21968895, что помогает уменьшить среднее время при определении простоты для каждого из этих чисел. |
12 сен 19, 21:07 [21969892] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Решил проверить программу на числах 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) Получилось:
|
|
13 сен 19, 06:12 [21969978] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Так что, критика и обсуждения закончились? А как же дежурные фразы, mayton 21908442? |
13 сен 19, 16:41 [21970552] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Сколько времени он у тебя работал? |
13 сен 19, 17:15 [21970591] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
До этого были пробные тесты для s = 1, для s = 2, для s = 3. После этого был пробный тест для всех s. Поскольку ПК - старенький, то прогон проводился для отдельных s до 250 000 00, а для всех s - до 68 000 000. Стараюсь запускать программу тогда, когда нахожусь рядом. Поскольку для небольших n всё проходит, то наступает "эвристика". Можно распространять на большие числа. В частности, был прогон для чисел около 2^1024. |
||
13 сен 19, 17:47 [21970615] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Надо оценить асимптоматику. Не вычислить. А именно оценить. Для этого надо сделать штук 5 запусков С линейно меняющимся параметром И засечь с точностью до секунд время. После этого посмотреть в Экселе график И прикинуть что это. Полином? Экспонента? Etc. |
13 сен 19, 19:00 [21970664] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Нужно ли предварительное деление? Нужен ли предварительный тест Ферма? |
||
13 сен 19, 19:02 [21970667] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Выше ты делил по 50 лимонов. Вот пускай так и будет. По Ферма не понял. Мы ведь один алгоритм обсуждаем? Или несколько? |
13 сен 19, 20:03 [21970714] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Основные параметры эвристического алгоритма: - число значений s2; - число раундов при одном s2, после которого узнаём, что число составное ( остаток не равен ни 1, ни (n - 1)) - число значений s2, после которых определяется простое число. По каждому значению можно определить мax или min на некотором интервале чисел (у меня либо 200000, либо 1000000). |
13 сен 19, 20:05 [21970716] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Ведь тест Ферма - это один раунд. Тест Миллера-Рабина - это несколько раундов. Причём, это по всем числам: и составным, и простым. Мне видится следующий подход: тест Ферма ограничивает количество чисел, среди которых все простые числа, а тест Миллера-Рабина (с эвристическим алгоритмом или с другим алгоритмом) "зачищает" полученные числа, выбирая из них только простые числа. Это моё видение процесса поиска простых чисел, при этом ещё в начале процесса поиска - деление на небольшие множители. Можно рассмотреть вопрос применения одного эвристического алгоритма для формул теста Миллера-Рабина, и сравнить результат применения алгоритма с результатами теста Ферма. |
||
13 сен 19, 20:17 [21970721] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Сейчас у меня заканчилась работа программы для второго диапазона: от 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] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Вот ты мастак все усложнять. Я хотел посмотреть имеет ли смысл изучать твой Питонский исходник. И хотел посмотреть его отклик. Знаешь как в радиоэлектронике. Подали входной сигнал. Встали осцилографом на выход. Посмотрели. Поменяли сигнал и т д. |
13 сен 19, 20:36 [21970730] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Убрал все добавления, оставил один эвристический алгоритм. Программа считает. На 2 000 000 чисел 148932 простых. Время работы 1,5 минуты. Программа продолжает работу... |
13 сен 19, 21:02 [21970735] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Нужно хотя-бы 5 точек на плоскости чтоб мы построили график зависимости времени от параметра алгоритма. |
13 сен 19, 22:32 [21970755] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Геннадий? Куда-то пропал. Или построение 5 измерений так долго? |
14 сен 19, 14:05 [21970891] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Продолжаю считать. Уже прошёл (с остановками) число 153 000 000. Есть интересное число 133800661, разбирался с ним. |
||
14 сен 19, 14:14 [21970899] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Так долго? Ладно побей на интервалы поменьше. |
14 сен 19, 15:37 [21970927] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
На отметке 175 000 000 уходит уже 2,5 минуты |
||
14 сен 19, 15:43 [21970930] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 51128 |
Ну дык... цифры есть? 4-5 штук. |
14 сен 19, 15:45 [21970931] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
- на каком раунде (а1) выявляется составное число (максимальное по мини диапазону); - сколько может быть значений s2 (максимум на мини диапазоне) - дополнительные 9 раундов на каждое значение. На текущий момент max a1 - очень редко 7, один раз - 11, а для s2 - почти всегда 4. |
||
14 сен 19, 16:14 [21970943] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2355 |
Прошел 250 000 000. В конце этого диапазона время обработки мини диапазона увеличилась до 3 мин. 09 сек. На текущий момент max a1 - очень редко 7, а для s2 - почти всегда 4, редко 5,6, один раз 8. |
14 сен 19, 19:29 [21970980] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: ←Ctrl назад 1 [2] 3 4 5 6 7 8 9 10 вперед Ctrl→ все |
Все форумы / Программирование | ![]() |