ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
25 сообщений из 402, страница 9 из 17
  9  все
Генератор простых чисел (до 10^9 за 5 сек)
    #38926033
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneНапример, между 139 и 149 дельта 10.
Точно, тест про другое. Это не проверилось т.к. раньше было 127 - 113 = 14
Тогда 1 байт.
...
Рейтинг: 0 / 0
03.04.2015, 11:11
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926048
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TТогда 1 байт.Надо к ним кодирование Хаффмана применить.
...
Рейтинг: 0 / 0
03.04.2015, 11:20
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926088
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я предполагал использовать знаковое кодирование для кодов Левенштейна или Фибоначчи.
Чтобы плотно ужимать поток "Дельт".
...
Рейтинг: 0 / 0
03.04.2015, 11:42
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926106
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BarloneDima TТогда 1 байт.Надо к ним кодирование Хаффмана применить.
Хаффман - это очень хороший вариант. Но надо будет делать перерасчёт
таблицы для каждого файла-блока primes.
...
Рейтинг: 0 / 0
03.04.2015, 11:57
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926129
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Да там кстати и повторяющиеся последовательности будут, та же "4,2,4,2,4,6,2,6" где-то вылезет. Так что взять и пожать zlib, ничего не изобретая.
...
Рейтинг: 0 / 0
03.04.2015, 12:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926166
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
zlib нас ограничивает в произвольном доступе.
К примеру если 2-Гб трафик (потока дельт) был сжат.
Но нам нужно получить актуальность какогото prime
который лежит в середине файла - придётся
пробегать с самого начала.

Кастомные-же форматы позволяют нам строить
индекс по этому сжатому трафику.
...
Рейтинг: 0 / 0
03.04.2015, 12:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926167
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
 
Посчитал распределение
end calc to 4294967295 time 9203 msec
DeltaCountДоляНарастающим120.00%0.00%2127366336.27%6.27%4127372846.27%12.53%62284663311.24%23.78%8102021715.02%28.80%10132239506.51%35.30%12171747328.45%43.75%1495354204.69%48.45%1672012983.54%51.99%18131830606.49%58.48%2072957043.59%62.07%2262556103.08%65.14%2495642594.71%69.85%2645805112.25%72.10%2849938332.46%74.56%3090758874.47%79.03%3228918161.42%80.45%3430441011.50%81.95%3650125382.47%84.41%3823725181.17%85.58%4028216181.39%86.97%4242218192.08%89.05%4417398230.86%89.90%4615094880.74%90.65%4826237321.29%91.94%5015043530.74%92.68%5211399490.56%93.24%5419155290.94%94.18%569988550.49%94.67%588618580.42%95.10%6017945700.88%95.98%625690120.28%96.26%645806200.29%96.54%6610762230.53%97.07%684429190.22%97.29%706351460.31%97.60%726508570.32%97.92%743227110.16%98.08%762889520.14%98.23%785545090.27%98.50%802871550.14%98.64%822038530.10%98.74%844257720.21%98.95%861540200.08%99.03%881601340.08%99.10%903258690.16%99.26%921105000.05%99.32%941012970.05%99.37%961794880.09%99.46%98948970.05%99.50%100989750.05%99.55%1021326480.07%99.62%104610420.03%99.65%106539270.03%99.67%108935500.05%99.72%110569220.03%99.75%112448270.02%99.77%114691480.03%99.80%116294880.01%99.82%118290010.01%99.83%120624470.03%99.86%122199640.01%99.87%124201770.01%99.88%126388010.02%99.90%128140210.01%99.91%130193130.01%99.92%132245740.01%99.93%134105980.01%99.94%13693960.00%99.94%138179890.01%99.95%140112410.01%99.96%14267860.00%99.96%144116100.01%99.96%14649930.00%99.97%14854920.00%99.97%150113100.01%99.98%15236100.00%99.98%15444950.00%99.98%15663390.00%99.98%15826220.00%99.98%16030600.00%99.99%16240850.00%99.99%16419610.00%99.99%16617320.00%99.99%16838700.00%99.99%17018560.00%99.99%17212310.00%99.99%17422060.00%99.99%17610270.00%99.99%1789050.00%99.99%18020070.00%100.00%1827830.00%100.00%1846860.00%100.00%18610700.00%100.00%1884250.00%100.00%1906670.00%100.00%1927390.00%100.00%1943550.00%100.00%1963820.00%100.00%1986480.00%100.00%2003150.00%100.00%2022310.00%100.00%2044130.00%100.00%2061730.00%100.00%2081700.00%100.00%2104190.00%100.00%2121240.00%100.00%214990.00%100.00%2161880.00%100.00%218810.00%100.00%2201140.00%100.00%2221100.00%100.00%224660.00%100.00%226560.00%100.00%228870.00%100.00%230570.00%100.00%232320.00%100.00%234890.00%100.00%236320.00%100.00%238340.00%100.00%240560.00%100.00%242220.00%100.00%244180.00%100.00%246280.00%100.00%248170.00%100.00%250150.00%100.00%252250.00%100.00%25460.00%100.00%256100.00%100.00%258160.00%100.00%26080.00%100.00%26280.00%100.00%264100.00%100.00%266100.00%100.00%26850.00%100.00%270100.00%100.00%27220.00%100.00%27420.00%100.00%27670.00%100.00%27810.00%100.00%28040.00%100.00%28260.00%100.00%28430.00%100.00%28620.00%100.00%28850.00%100.00%29050.00%100.00%29230.00%100.00%30410.00%100.00%30610.00%100.00%31010.00%100.00%32010.00%100.00%33620.00%100.00%203231689100.00%

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
		uint32_t t = now_msec();
		uint32_t cnt[337] = {0};
		uint32_t delta = 0;
		uint32_t x = 1;
		while(x && x < TEST) {
			uint32_t xn = next_prime(x);
			if(xn) cnt[xn - x]++;
			x = xn;
		}
		printf("end calc to %u time %u msec\nDelta,Count\n", TEST, now_msec() - t);
		for(int i = 1; i < 337; i++) if(cnt[i]) printf("%d,%d\n",i, cnt[i]);


150 вариантов. Минимум 8 бит. Весь диапазон 168 (336/2). ИМХУ нет смысла заморачиваться на хитрое хранение.
Не совсем понял зачем вы коды добавлять собрались. Если для контроля целостности при хранении, то проще писать блоками, в начале и конце указывать полное значение, проверить не сложно.
Судя по распределению обычный архиватор должен хорошо пожать.
...
Рейтинг: 0 / 0
03.04.2015, 12:42
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926192
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Сохранил в файл. Не особо жмется
Типразмерисходный203 231 689zip168 118 383rar158 861 104
...
Рейтинг: 0 / 0
03.04.2015, 12:58
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926194
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonzlib нас ограничивает в произвольном доступе.
К примеру если 2-Гб трафик (потока дельт) был сжат.
Но нам нужно получить актуальность какогото prime
который лежит в середине файла - придётся
пробегать с самого начала.

Кастомные-же форматы позволяют нам строить
индекс по этому сжатому трафику.Ну чтобы получить prime по дельтам, по любому надо с самого начала начинать.
...
Рейтинг: 0 / 0
03.04.2015, 13:00
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926202
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TПосчитал распределение
DeltaCountДоляНарастающим120.00%0.00%
Это что за артефакт? Понятно, 3-2 = 1. А откуда вторая дельта = 1?
...
Рейтинг: 0 / 0
03.04.2015, 13:05
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926207
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
А, увидел, начальное значение, 2-1
...
Рейтинг: 0 / 0
03.04.2015, 13:07
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926209
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneЭто что за артефакт? Понятно, 3-2 = 1. А откуда вторая дельта = 1?
2-1 перебор с единицы начинается. Код там же. Накосячил немного :)
...
Рейтинг: 0 / 0
03.04.2015, 13:08
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926212
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Что в распределении явно выделяются кратные 6 - кажется довольно неожиданным.
...
Рейтинг: 0 / 0
03.04.2015, 13:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926216
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Сохранил бикарту в файл:
Типразмерисходный268 435 456zip141 244 527rar133 962 811
Биткарта лучше жмется. И для произвольного доступа удобнее.
...
Рейтинг: 0 / 0
03.04.2015, 13:14
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926220
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TБиткарта лучше жмется. И для произвольного доступа удобнее.Я уже предлагал делать биткарту только для некратных 2,3,5. Получается по байту на 30 чисел. Правда доступ чуть сложнее.
...
Рейтинг: 0 / 0
03.04.2015, 13:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926231
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneЧто в распределении явно выделяются кратные 6 - кажется довольно неожиданным.
Это не кратные, а разница 6. В принципе объяснимо кратными 3.
для исключения кратных 3 так перебор строится
Код: plaintext
1.
2.
3.
4.
int step = 4;
for(int i = 5; i < N; i += step) {
  step = 6 - step;
...


половина двоек и четверок отсекается
...
Рейтинг: 0 / 0
03.04.2015, 13:23
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926232
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Barlonemaytonzlib нас ограничивает в произвольном доступе.
К примеру если 2-Гб трафик (потока дельт) был сжат.
Но нам нужно получить актуальность какогото prime
который лежит в середине файла - придётся
пробегать с самого начала.

Кастомные-же форматы позволяют нам строить
индекс по этому сжатому трафику.Ну чтобы получить prime по дельтам, по любому надо с самого начала начинать.
Всё зависит от того как мы спроектируем.

Варианты:

1) Быстрое получение признака primary. Большой объём дискового хранилища.
2) Среднее время получения признака primary. Компромиссный (регулируемый объём)
дискового хранилища исходя из требования или пожелания по времени ожидания.
3) Медленное получение признака. Компактный объём. Архив.
...
Рейтинг: 0 / 0
03.04.2015, 13:24
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926240
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
BarloneDima TБиткарта лучше жмется. И для произвольного доступа удобнее.Я уже предлагал делать биткарту только для некратных 2,3,5. Получается по байту на 30 чисел. Правда доступ чуть сложнее.
Думаю оптимальный вариант для хранения и произвольного доступа.
Компактнее будет чем у меня в RARе. У меня только кратные пропущены. 1 байт 16 чисел.

Можно затестить если код будет:
Код: plaintext
1.
2.
set_bit(uint32_t x, uint8_t *bitmap);
get_bit(uint32_t x, uint8_t *bitmap);
...
Рейтинг: 0 / 0
03.04.2015, 13:38
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926250
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TBarloneЧто в распределении явно выделяются кратные 6 - кажется довольно неожиданным.
Это не кратные, а разница 6. В принципе объяснимо кратными 3.
для исключения кратных 3 так перебор строится
Код: plaintext
1.
2.
3.
4.
int step = 4;
for(int i = 5; i < N; i += step) {
  step = 6 - step;
...


половина двоек и четверок отсекается
Дима. А если мы оставшийся трафик прогоним через какой-нибудь анализ.
Вдруг еще чего-то "кикнуть" можно будет? Но желательно чтоб формула
была простака. Типа вот разность или xor.
...
Рейтинг: 0 / 0
03.04.2015, 13:44
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926255
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TЭто не кратные, а разница 6.Понятно, что разности кратные 6. Почему-то мне казалось, что распределение должно убывать более равномерно. А нет, например 30 встречается заметно чаще, чем 28 и т.д.
...
Рейтинг: 0 / 0
03.04.2015, 13:49
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926256
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
2 all.

В сборке pbfa-x64 я добавил подсчёт "чисел-близнецов" twin-primes. Возможно пригодится для оценки.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
Primes detected      : 5761455
Twin primes          : 440311
Range                : [2..100000000]
Memory cache used    : 65536 K
Square root algorithm: Henry Warren's 'isqrt64'
AVG speed generation : 37170 units/sec
Elapsed time         : 155 sec
...
Рейтинг: 0 / 0
03.04.2015, 13:50
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926260
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Dima TBarloneпропущено...
Я уже предлагал делать биткарту только для некратных 2,3,5. Получается по байту на 30 чисел. Правда доступ чуть сложнее.
Думаю оптимальный вариант для хранения и произвольного доступа.
Компактнее будет чем у меня в RARе. У меня только кратные пропущены. 1 байт 16 чисел.

Можно затестить если код будет:
Код: plaintext
1.
2.
set_bit(uint32_t x, uint8_t *bitmap);
get_bit(uint32_t x, uint8_t *bitmap);

навскидку что-то такое
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
int get_bit(int n) {
  switch(n % 30) {
    case 1:  return 1;
    case 7:  return 2;
    case 11: return 4;
    case 13: return 8;
    case 17: return 16;
    case 19: return 32;
    case 23: return 64;
    case 29: return 128;
    default: return 0; // делится на 2,3 или 5...
  }
}
...
Рейтинг: 0 / 0
03.04.2015, 13:54
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926263
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BarloneКритерий Поклингтона для вашего числа:
N = 271963805968702864258461551790513043662751795453
N-1 = 90233392513315464829662320219386916428363 * 3014004
Берем a=2, проверяем что 2^(N-1) mod N = 1 и gcd(2^3014004-1, N) = 1 - это легко, возьмите gmp (или mpir под windows) и проверьте. Я проверил.
Правда теперь надо еще доказать, что 90233392513315464829662320219386916428363 простое.
Для него можно проделать все то же самое, теперь упремся в доказательство простоты 10378812113332811689632196942648598623.
С этим хуже, для него N-1 = 2*3*11*73*761*83537*403253*1108092371*75833962769 - тут нет простого множителя больше квадратного корня, критерий Поклингтона не получиться использовать.
Уже третий раз берусь писать комментарий но всё откладываю.

Спрошу проще.

Данный критерий даёт примерно одинаковую вероятность простоты для всех чисел?
Или одни числа могут быть простыми с большей вероятностью чем другие?
...
Рейтинг: 0 / 0
03.04.2015, 13:56
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926282
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима. А если мы оставшийся трафик прогоним через какой-нибудь анализ.
Вдруг еще чего-то "кикнуть" можно будет? Но желательно чтоб формула
была простака. Типа вот разность или xor.
Который трафик? на входе (диапазон чисел) или на выходе (простые).

Я как раз этим и занимался. Не закончил. С тройкой все просто, шаг 2,4,2,4...
Дальше сложнее: для (2,3,5) шаги 4,2,4,2,4,6,2,6
тут уже таблица нужна, но тоже достаточно быстро должно быть
Код: plaintext
1.
2.
3.
4.
5.
6.
int step[] = {4,2,4,2,4,6,2,6};
int step_id = 1;
for(int i = 5; i < N; i += step[step_id]) {
  step_id++;
  if(step_id == 8) step_id = 0;
...


это непроверенный код, пока только вычислил шаги, не факт что не ошибся.

(2,3,5,7) - 48 шагов
(2,3,5,7,11) - 480 шагов
(2,3,5,7,11,13) - 5720 шагов

По хорошему надо генератор последовательностей написать и затестить какая выше взлетит.
...
Рейтинг: 0 / 0
03.04.2015, 14:08
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38926292
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonBarloneКритерий Поклингтона для вашего числа:
N = 271963805968702864258461551790513043662751795453
N-1 = 90233392513315464829662320219386916428363 * 3014004
Берем a=2, проверяем что 2^(N-1) mod N = 1 и gcd(2^3014004-1, N) = 1 - это легко, возьмите gmp (или mpir под windows) и проверьте. Я проверил.
Правда теперь надо еще доказать, что 90233392513315464829662320219386916428363 простое.
Для него можно проделать все то же самое, теперь упремся в доказательство простоты 10378812113332811689632196942648598623.
С этим хуже, для него N-1 = 2*3*11*73*761*83537*403253*1108092371*75833962769 - тут нет простого множителя больше квадратного корня, критерий Поклингтона не получиться использовать.
Уже третий раз берусь писать комментарий но всё откладываю.

Спрошу проще.

Данный критерий даёт примерно одинаковую вероятность простоты для всех чисел?
Или одни числа могут быть простыми с большей вероятностью чем другие?Это как бы детерменированный тест. Про какую вероятность речь? Что для простого N и некоторого а (которое в примере 2) gcd будет не 1? Не знаю, на самом деле это вообще маловероятно.
Да, этот критерий используют не для проверки простоты, а для её доказательства. Разница понятна? Для проверки простоты используют вероятностный тест Миллера-Рабина - он говорит "число точно не простое / возможно простое". А критерий Поклингтона - "число точно простое / возможно не простое".
...
Рейтинг: 0 / 0
03.04.2015, 14:17
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 9 из 17
  9  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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