|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovРазница между и очень мала. Разница где-то на 50-м знаке. Это надо обязательно учесть?Да. В этом проблема больших чисал. Эта малая разница встанет в знаменатель и даст нам приближенное количество простых на самом проблемном интревале. На малом криптографическом пороге. На 2^512 степени. А я уверен что у тебя в коде есть слабое место. И эту слабость можно проверить через такую приближённую оценку.Но у нас нет точной формулы количества простых чисел на интервале. Только оценка количества. Так что, там допуск, здесь допуск... ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:35 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Нам нужно сравить твой алгоритм с чем-то эталонным. Самое простое сравнение на малых числах - это гонять решето и метод грубой силы. Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать взаимные сверки. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:40 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
maytonНам нужно сравить твой алгоритм с чем-то эталонным. Самое простое сравнение на малых числах - это гонять решето и метод грубой силы. Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать взаимные сверки.Метод грубой сила или что-то подобное "заканчивается" где-то далеко от 2^1024. Один известный мне "калькулятор - определение простых чисел" работает только до 2^420. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:52 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
По поводу толстых натуральных логарифмов я создам отдельный топик. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:57 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
20.09.2019, 12:11 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.09.2019, 19:00 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
exp98Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас?В тесте Миллера-Рабина упор идёт на вероятность. Он не знает, что делать с получаемыми числами: у многих составных чисел по разным a и s иногда "выскакивают" нужные для простых чисел значения остатков по модулю. А раз есть вероятность, то надо быть уверенным: чем больше нужных чисел, тем большая уверенность. Появился log(n) для полной уверенности. Часть составных чисел быстро "вылетают" - там нет нужных для простых чисел величин. А у другой части составных чисел "большое засилье" таких величин. У меня простая система, без вероятностей, с определённым количеством раундов, проверенная уже на числах от 5 до 930 000 000. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.09.2019, 19:32 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Прошел число 1 000 000 000. -perep- 998000131 3045476 31524295 0 5 3 2019-09-21-11.58.37 -perep- 999000133 3093917 32024662 0 3 3 2019-09-21-12.04.52 -N blok- 3141866 3 3 В конце этого диапазона время обработки мини диапазона составляет 6 мин. 15 сек. На текущий момент max a1 - очень редко 7, иногда 11,13. а для s2 - почти всегда 4, редко 5, есть один раз 7 и 8. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.09.2019, 13:23 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Добавил колонку average speed. Range Primes Found Primes (theoretical) Elapsed time Average Speed (primes/sec)3 - 50 000 000 3 001 132 2 820 471 8,38 358 130350_000_000 - 400_000_000 2 532 800 2 404 426 9,59 264 108750_000_000 - 800_000_000 2 442 998 2 330 675 10,06 242 8421_500_000_000 - 1_550_000_000 2 364 554 2 252 774 надо пересчитать 2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 3 4632^500 +1 - 2^500 + 1 + 200 000 576 3,21 1792^1024 +1 - 2^1024 +1 + 200 000 281 21,59 13 ... |
|||
:
Нравится:
Не нравится:
|
|||
23.09.2019, 00:26 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
maytonДобавил колонку average speed. Range Primes Found Primes (theoretical) Elapsed time Average Speed (primes/sec)3 - 50 000 000 3 001 132 2 820 471 8,38 358 130350_000_000 - 400_000_000 2 532 800 2 404 426 9,59 264 108750_000_000 - 800_000_000 2 442 998 2 330 675 10,06 242 8421_500_000_000 - 1_550_000_000 2 364 554 2 252 774 11,04 2^200 +1 - 2^200 + 1 + 1 000 000 7134 2,06 3 4632^500 +1 - 2^500 + 1 + 200 000 576 3,21 1792^1024 +1 - 2^1024 +1 + 200 000 281 21,59 13 ... |
|||
:
Нравится:
Не нравится:
|
|||
23.09.2019, 10:08 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Добавил 100 тысяч на диапазоне 2048 бит. Вот данные для проверки. Две таблички надо соединить. Но уже поздно. Я засыпаю. Range Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)2^200 +1 - 2^200 + 1 + 1 000 0007135611892^500 +1 - 2^500 + 1 + 200 00057722882^1024 +1 - 2^1024 + 1 + 200 0002828352^2048 +1 - 2^2048 + 1 + 100 00079272 Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21.
... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 00:50 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Здесь я выскакиваю за range. Код: java 1. 2. 3. 4.
Последний инкремент - лишний. Поэтому от всех результатов можно вычесть 1. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 09:28 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Поскольку появилась новая строка в таблице, то решил ещё раз эту строку пересчитать (не помню, чтобы считал диапазон на 100000) 2^2048 +1 - 2^2048 + 1 + 100 000 Определено 78 простых чисел. Программа считала с 2019-09-30-11.35.28 по 2019-09-30-13.14.28 ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 13:19 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Это мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c. В принципе Рабин-Миллер+Люка и создавались для этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 13:40 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
maytonЭто мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c. В принципе Рабин-Миллер+Люка и создавались для этого.Так это прекрасное сообщение! Мы расходимся в одном числе! (79 и 78) Прекрасно! ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 14:12 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Яж говорю. Я допустил ошибку. Самое последнее простое число превышает правую границу. Поэтому надо делать мину 1 ко всем моим результатам. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 14:45 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Но не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 14:56 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
maytonНо не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.Или строгая формула (алгоритм) ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 15:13 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Gennadiy UsovmaytonНо не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.Или строгая формула (алгоритм) Рано хвастаешся. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 17:05 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Почему Primes (theoretical) до сих пор не заполнено? Может это тоже теперь эвристика для всех последующих диапазонов. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 17:34 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Ребята я все не успеваю. Заполните плиз табличку. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 18:06 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Это любой же может. Ну дык ведь я теперь девочка для набивки, с длинными ноготочками. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
....... и так далее )) Можно даже не считать уже Достаточно делить и умножать предыдущее. Но вы пока это посчитайте ... а я потом ещё оценок подкину. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 22:06 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Опровержение) RangePrimes(theoretical)2^200+1млн71612^500+200тыр5752^1024+200тыр2812^2048+100тыр702^4096+500тыр1762^4096+1млн3522^8192+500тыр882^8192+1млн176 Модератор: Поправил ... |
|||
:
Нравится:
Не нравится:
|
|||
30.09.2019, 22:10 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
Я говорю табличку заполните. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.10.2019, 11:28 |
|
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
|
|||
---|---|---|---|
#18+
mayton, я первым это сказал. И потом, кто больше всех заинтересован в пиаре этой темы, того пусть и тапки. Имхо, отчёты и презентации - занятие для благородных особ, а я - золушка, мне бы вечером принц приехал на серебрянном коне. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.10.2019, 14:38 |
|
|
start [/forum/topic.php?fid=16&msg=39869177&tid=1339873]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
148ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
66ms |
get tp. blocked users: |
2ms |
others: | 233ms |
total: | 495ms |
0 / 0 |