powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Эвристический алгоритм (формула, тест простоты) для определения простых чисел
25 сообщений из 233, страница 5 из 10
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864194
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovРазница между и очень мала.
Разница где-то на 50-м знаке. Это надо обязательно учесть?Да. В этом проблема больших чисал. Эта малая разница встанет в знаменатель и даст нам приближенное
количество простых на самом проблемном интревале. На малом криптографическом пороге. На 2^512 степени.
А я уверен что у тебя в коде есть слабое место. И эту слабость можно проверить через такую приближённую
оценку.Но у нас нет точной формулы количества простых чисел на интервале.
Только оценка количества.

Так что, там допуск, здесь допуск...
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864196
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нам нужно сравить твой алгоритм с чем-то эталонным.
Самое простое сравнение на малых числах - это гонять решето и метод грубой силы.

Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую
метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать
взаимные сверки.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864202
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНам нужно сравить твой алгоритм с чем-то эталонным.
Самое простое сравнение на малых числах - это гонять решето и метод грубой силы.
Для толстых чисел я пока придумал просто учет количества. Если он не прокатит - я попробую
метод isProbablePrime. Поскольку твой метод считает точное количество - мы можем делать
взаимные сверки.Метод грубой сила или что-то подобное "заканчивается" где-то далеко от 2^1024.

Один известный мне "калькулятор - определение простых чисел" работает только до 2^420.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864204
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу толстых натуральных логарифмов я создам отдельный топик.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864501
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864824
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас?
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864834
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
exp98Хотел ещё уточнить. Вы писали, что эталонный мюллер работает со скор-ю ln(n) или что-то подобное. Но ведь это теоретическая оценка? Мне непонятно, может на практике он работает как получится? и может очень часто получается гораздо быстрее, нет? у вас чевой-то говорилось про раунды, про то, про сё. Может в большинстве случаев всё как у вас?В тесте Миллера-Рабина упор идёт на вероятность.
Он не знает, что делать с получаемыми числами:
у многих составных чисел по разным a и s иногда "выскакивают" нужные для простых чисел значения остатков по модулю.

А раз есть вероятность, то надо быть уверенным:
чем больше нужных чисел, тем большая уверенность.

Появился log(n) для полной уверенности.
Часть составных чисел быстро "вылетают" - там нет нужных для простых чисел величин.
А у другой части составных чисел "большое засилье" таких величин.

У меня простая система, без вероятностей, с определённым количеством раундов,
проверенная уже на числах от 5 до 930 000 000.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39864988
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Прошел число 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.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39865351
Фотография 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 надо пересчитать 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
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39865431
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39868815
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Добавил 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.
public static void test(String label, BigInteger a, BigInteger b) {
        long t1 = currentTimeMillis();
        int cnt = 0;
        while(a.compareTo(b) < 0) {
            a = a.nextProbablePrime();
            cnt++;
        }
        long t2 = currentTimeMillis();
        long elapedTimeS = (t2 - t1) / 1000;
        long avgSpeed = elapedTimeS != 0 ? cnt / elapedTimeS : 0;
        printf("%s;;%d;;%d;%d\n", label, cnt, elapedTimeS, avgSpeed);
    }

    public static void main(String[] args) {
        printf("[CSV=;]Range; Primes Found(Usoff) ; Primes Found(JDK::BigInteger) ; Primes (theoretical) ; Elapsed time(s) ; Average Speed (primes/sec)\n");
        test("2^200 +1 - 2^200 + 1 + 1 000 000", TWO.pow(200).add(ONE),  TWO.pow(200).add(ONE).add(BigInteger.valueOf(1_000_000)));
        test("2^500 +1 - 2^500 + 1 + 200 000",   TWO.pow(500).add(ONE),  TWO.pow(500).add(ONE).add(BigInteger.valueOf(200_000)));
        test("2^1024 +1 - 2^1024 + 1 + 200 000", TWO.pow(1024).add(ONE), TWO.pow(1024).add(ONE).add(BigInteger.valueOf(200_000)));
        test("2^2048 +1 - 2^2048 + 1 + 100 000", TWO.pow(2048).add(ONE), TWO.pow(2048).add(ONE).add(BigInteger.valueOf(100_000)));
        printf("[/CSV]");
    }
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39868909
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здесь я выскакиваю за range.

Код: java
1.
2.
3.
4.
while(a.compareTo(b) < 0) {
            a = a.nextProbablePrime();
            cnt++;
        }



Последний инкремент - лишний. Поэтому от всех результатов можно вычесть 1.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869102
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Поскольку появилась новая строка в таблице, то решил ещё раз эту строку пересчитать
(не помню, чтобы считал диапазон на 100000)

2^2048 +1 - 2^2048 + 1 + 100 000

Определено 78 простых чисел.
Программа считала с 2019-09-30-11.35.28 по 2019-09-30-13.14.28
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869124
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c.
В принципе Рабин-Миллер+Люка и создавались для этого.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869154
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonЭто мы протестили генерацию простых на крипто-диапазоне. 2^2048 e.t.c.
В принципе Рабин-Миллер+Люка и создавались для этого.Так это прекрасное сообщение!

Мы расходимся в одном числе! (79 и 78)

Прекрасно!
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869177
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Яж говорю. Я допустил ошибку. Самое последнее простое число превышает правую границу. Поэтому надо делать мину 1 ко всем
моим результатам.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869191
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869211
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНо не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.Или строгая формула (алгоритм)
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869342
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonНо не обольщайся. Миллер-Рабит хоть и шумит но имеет шанс поймать составное. Тоесть несколько запусков
Миллера - выровняют картинку. У тебя-же 100% детерминизм. Невыявленная ошибка.Или строгая формула (алгоритм)
Рано хвастаешся.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869362
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему Primes (theoretical) до сих пор не заполнено? Может это тоже теперь эвристика для всех последующих диапазонов.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869386
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ребята я все не успеваю. Заполните плиз табличку.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869590
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это любой же может. Ну дык ведь я теперь девочка для набивки, с длинными ноготочками.
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
Range	Primes(theoretical)
2^200+1млн	7161
2^500+200тыр	575
2^1024+200тыр	281
2^2048+1тыр	70
2^4096+5тыр	176
2^4096+1млн	352
2^8192+5тыр	88
2^8192+1млн	176


....... и так далее )) Можно даже не считать уже
Достаточно делить и умножать предыдущее. Но вы пока это посчитайте ... а я потом ещё оценок подкину.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869593
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Опровержение)

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
Модератор: Поправил
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869786
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я говорю табличку заполните.
...
Рейтинг: 0 / 0
Эвристический алгоритм (формула, тест простоты) для определения простых чисел
    #39869981
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, я первым это сказал. И потом, кто больше всех заинтересован в пиаре этой темы, того пусть и тапки. Имхо, отчёты и презентации - занятие для благородных особ, а я - золушка, мне бы вечером принц приехал на серебрянном коне.
...
Рейтинг: 0 / 0
25 сообщений из 233, страница 5 из 10
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Эвристический алгоритм (формула, тест простоты) для определения простых чисел
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]