Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Barloneнавскидку что-то такое Затестил, работает Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. Типразмерисходная143 165 577zip105 477 171rar106 706 171 ИМХУ это пока самый оптимальный вариант для хранения. switch() только на массив заменить, чтобы так было mask[n%30] ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 14:52 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
BarloneЭто как бы детерменированный тест. Про какую вероятность речь? Что для простого N и некоторого а (которое в примере 2) gcd будет не 1? Не знаю, на самом деле это вообще маловероятно. Да, этот критерий используют не для проверки простоты, а для её доказательства. Разница понятна? Для проверки простоты используют вероятностный тест Миллера-Рабина - он говорит "число точно не простое / возможно простое". А критерий Поклингтона - "число точно простое / возможно не простое". Спасибо. Всё это надо обдумать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 15:08 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Dima TТипразмерисходная143 165 577zip105 477 171rar106 706 171 ИМХУ это пока самый оптимальный вариант для хранения. switch() только на массив заменить, чтобы так было mask[n%30]Надо уже куда-нибудь выложить файл. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 15:11 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
BarloneНадо уже куда-нибудь выложить файл. Смысл один файл вкладывать? Он дольше качаться будет чем генериться. Причесал немного. Сделал x64. Выложил исходник https://sourceforge.net/projects/primegen/ только там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 16:03 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Dima Tтолько там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса. strtoull ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 16:19 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
BarloneDima Tтолько там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса. strtoull ? Поправил. Компилируется в линуксе. Залил. https://sourceforge.net/p/primegen/code/HEAD/tree/trunk/DimaT/bitmap30.cpp ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 16:43 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Взлетает идея с оптимизацией шагов цикла. Результатыtest eratosfen2() skip 2 from 1 to 1000M eratosfen2() 1524M(499M) steps count 50847534 primes time 4786 msec test eratosfen3() skip 2,3 from 1 to 1000M eratosfen3() 1191M(333M) steps count 50847534 primes time 4277 msec test eratosfen5() skip 2,3,5 from 1 to 1000M eratosfen5() 1024M(266M) steps count 50847534 primes time 4095 msec это замер трех вариантов перебора до 10^9 с пропусками кратно 2, затем 2,3, затем 2,3,5 Синим: количество млн. итераций всего(в т.ч. оптимизируемого цикла) Красным: общее время расчета. Цикл такой Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Целиком тут https://sourceforge.net/p/primegen/code/HEAD/tree/trunk/DimaT/eratosfentest.cpp Можно писать генератор, только мне массив offset[] не нравится. Как бы его укоротить. Попробую на switch() заменить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 18:02 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Я тут решил посчитать сколько primes мы выкурим по 64-битной архитектуре. Максимальное целое unit64 = 0xFFFF FFFF FFFF FFFF = 18 446 744 073 709 551 615 415 828 534 307 635 091 или 415 "пета"-чисел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 18:22 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Плотность primes на последних интервалах стремиться к 2%. Если работать по Эратосфену - то по сути гоняем воздух. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 18:26 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonЯ нарисовал табличку для тестов и для оценки плотности распределения primes. Selection from 2 to..Primes detectedAll to primes ratio10025 0.251000 168 0.16810000 1 229 0.1229100000 9 592 0.095921000000 78 498 0.07849810000000 664 579 0.0664579100000000 5 761 455 0.057614551000000000 50 847 534 0.05084753418 446 744 073 709 551 615415 828 534 307 635 091(approx)0.0225421100 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 18:40 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
0.0508 всего в 2.258 раза больше 0.0225. Решаемо. Оптимизатор цикла поглубже сделать. Тестю switch(), есть мысли по 17471110 ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 18:48 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Хм... оказывается в Java (BigInteger) есть имплементация некой проверки на простоту. Метод isProbablePrime() который в свою очередь сложно зависим либо от теста passesMillerRabin(), (насколько я понял имеется в виду этот метод) и либо от совокупности решений passesMillerRabin(..) && passesLucasLehmer(..). Последний - скорее всего https://ru.wikipedia.org/wiki/Тест_Люка_—_Лемера Забавно что isProbablePrime в методе МиллераРабина оставляет за собой право вызывать функцию SecureRandom() очевидно для получения некой энтропии. Интересно насколько это влияет на дерерминизм самого метода isProbablePrime. Мда. Коллеги. Я многих веще признаться не знал. Надо подумать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:05 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonЗабавно что isProbablePrime в методе МиллераРабина оставляет за собой право вызывать функцию SecureRandom() очевидно для получения некой энтропии. Интересно насколько это влияет на дерерминизм самого метода isProbablePrime. Ну, учитывая основное назначение подобных функций, детерминизм был бы там скорее минус чем плюс )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:11 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Еще метод isProbablePrime (в стеке вызовов внутренних методов) содержит искусственный ограничитель раундов проверки Рабина. Машинально делая code-review глазами я застрял на нём сейчас. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Обратите внимание что чем больше разрядная сетка основного числа которое мы проверяем тем меньше циклов Рабина идёт на выход. По всей видимости это искусственное ограничение на сам метод чтобы не грузить пользователя долгим откликом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:19 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonЗабавно что isProbablePrime в методе МиллераРабина оставляет за собой право вызывать функцию SecureRandom() очевидно для получения некой энтропии. А может они в качестве финальной проверки используют генерацию RSA-ключа и шифрование-дешифрование блока. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:24 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
BigInteger не содержит зависимостей от крипто-библиотек. Скорее наоборот. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:29 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovА может Пардон, брякнул не прочитав ссылку. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:30 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonBigInteger не содержит зависимостей от крипто-библиотек. Для проверки на простоту не надо генерировать криптостойкий RSA ключ, поэтому криптобиблиотеки и не нужны. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 19:35 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Модератор: Коллеги. Я потёр весь оффтопик касающийся SVN клиента и настроек. В дальнейшем давайте либо личным сообщением либо в отдельный топик ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.04.2015, 21:01 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Dima Tпамяти в x32 не хватает чтобы результаты обоих хранитьСравните контрольные суммы, а не сами результаты. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2015, 00:03 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Дима. Я на выходных попробую запилить Рабина-Миллера. И посмотреть его погрешность в определении простоты. Особо меня заинтересовало как можно устранить источник энтропии внутри функции. Иначе это путает все карты. offОказывается Рабин - это не только фамилия. Это еще и титул учёного-толкователя ("раввин"). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2015, 11:40 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonДима. Я на выходных попробую запилить Рабина-Миллера. И посмотреть его погрешность в определении простоты. Всё уже украдено до нас - https://oeis.org/A001262 https://oeis.org/A020229 https://oeis.org/A074773 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2015, 20:37 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
http://web.mit.edu/primes/materials/2014/conf/5-1-Narayanan.pdf Модератор: Не ленись давать комментарии к ссылкам, пожалуйста ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2015, 20:51 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
Barlone, почитал ссылки. А на каком языке написан код в разделе 'PROG' ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.04.2015, 22:34 |
|
||
|
Генератор простых чисел (до 10^9 за 5 сек)
|
|||
|---|---|---|---|
|
#18+
maytonBarlone, почитал ссылки. А на каком языке написан код в разделе 'PROG' ? https://en.wikipedia.org/wiki/PARI/GP ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.04.2015, 07:19 |
|
||
|
|

start [/forum/topic.php?fid=57&msg=38926668&tid=2017971]: |
0ms |
get settings: |
9ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
160ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
58ms |
get tp. blocked users: |
1ms |
| others: | 14ms |
| total: | 275ms |

| 0 / 0 |
