powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
25 сообщений из 402, страница 10 из 17
Генератор простых чисел (до 10^9 за 5 сек)
    #38926336
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
#include "../next_prime.h" 

uint8_t get_mask(uint32_t 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...
  }
}

#define TEST 0xFFFFFFFF

int main(int argc, char* argv[])
{
	int size = TEST / 30 + 1;
	uint8_t* bitmap = (uint8_t*)calloc(size, 1);
	uint32_t x = 7;
	while(x && x < TEST) {
		bitmap[x/30] |= get_mask(x);
		x = next_prime(x);
	}
	FILE* f = fopen("bitmap30.bin", "wb");
	fwrite(bitmap, size, 1, f);
	fclose(f);

	printf("bitmap ready size = %d\n", size);
	x = 7;
	for(uint32_t i = 0; i < TEST; i++) {
		if((bitmap[i/30] & get_mask(i))) {
			if(i != x) {printf("error %u != %u\n", i, x);break;}
			x = next_prime(x);
		}
	}
	printf("check end\n");

	any_key();
}


Типразмерисходная143 165 577zip105 477 171rar106 706 171
ИМХУ это пока самый оптимальный вариант для хранения.
switch() только на массив заменить, чтобы так было mask[n%30]
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926373
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneЭто как бы детерменированный тест. Про какую вероятность речь? Что для простого N и некоторого а (которое в примере 2) gcd будет не 1? Не знаю, на самом деле это вообще маловероятно.
Да, этот критерий используют не для проверки простоты, а для её доказательства. Разница понятна? Для проверки простоты используют вероятностный тест Миллера-Рабина - он говорит "число точно не простое / возможно простое". А критерий Поклингтона - "число точно простое / возможно не простое".
Спасибо. Всё это надо обдумать.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926381
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TТипразмерисходная143 165 577zip105 477 171rar106 706 171
ИМХУ это пока самый оптимальный вариант для хранения.
switch() только на массив заменить, чтобы так было mask[n%30]Надо уже куда-нибудь выложить файл.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926466
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneНадо уже куда-нибудь выложить файл.
Смысл один файл вкладывать? Он дольше качаться будет чем генериться.
Причесал немного. Сделал x64. Выложил исходник https://sourceforge.net/projects/primegen/
только там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926495
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tтолько там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса. strtoull ?
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926536
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneDima Tтолько там _strtoui64(), как понял только в MSVC скомпилируется. Не искал еще аналог для линукса. strtoull ?
Поправил. Компилируется в линуксе. Залил.
https://sourceforge.net/p/primegen/code/HEAD/tree/trunk/DimaT/bitmap30.cpp
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926634
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Взлетает идея с оптимизацией шагов цикла.
Результаты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.
...
		// для определения номера текущего шага
		static uint32_t offset[] = {9,0,9,9,9,9,9,1,9,9,9,2,9,3,9,9,9,4,9,5,9,9,9,6,9,9,9,9,9,7};
		// порядок шагов
		static uint32_t step5[] = {6,4,2,4,2,4,6,2};
		uint32_t step_id = offset[max_prime % 30]; // max_prime последнее найденное простое
		for(uint32_t i = max_prime + step5[step_id]; i < limit; i += step5[step_id]) {
			step_id++;
			step_id &= 7; //if(step_id == 8) step_id = 0;
			cnt++;
			cnt2++;
...
		}
	}
	free(bitmap);
	printf("eratosfen5() %dM(%dM) steps\n", (uint32_t)(cnt / 1000000), (uint32_t)(cnt2 / 1000000));


Целиком тут https://sourceforge.net/p/primegen/code/HEAD/tree/trunk/DimaT/eratosfentest.cpp

Можно писать генератор, только мне массив offset[] не нравится. Как бы его укоротить. Попробую на switch() заменить.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926648
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тут решил посчитать сколько primes мы выкурим по 64-битной архитектуре.

Максимальное целое unit64 = 0xFFFF FFFF FFFF FFFF = 18 446 744 073 709 551 615



415 828 534 307 635 091

или 415 "пета"-чисел.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926651
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Плотность primes на последних интервалах стремиться к 2%.
Если работать по Эратосфену - то по сути гоняем воздух.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926658
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926668
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
0.0508 всего в 2.258 раза больше 0.0225. Решаемо. Оптимизатор цикла поглубже сделать. Тестю switch(), есть мысли по 17471110 ?
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926678
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм... оказывается в Java (BigInteger) есть имплементация некой проверки на простоту.
Метод isProbablePrime() который в свою очередь сложно зависим либо от теста passesMillerRabin(),
(насколько я понял имеется в виду этот метод) и либо от совокупности решений
passesMillerRabin(..) && passesLucasLehmer(..). Последний - скорее всего https://ru.wikipedia.org/wiki/Тест_Люка_—_Лемера

Забавно что isProbablePrime в методе МиллераРабина оставляет за собой право вызывать функцию SecureRandom()
очевидно для получения некой энтропии. Интересно насколько это влияет на дерерминизм самого метода
isProbablePrime.

Мда. Коллеги. Я многих веще признаться не знал. Надо подумать.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926679
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЗабавно что isProbablePrime в методе МиллераРабина оставляет за собой право вызывать функцию SecureRandom()
очевидно для получения некой энтропии. Интересно насколько это влияет на дерерминизм самого метода
isProbablePrime.
Ну, учитывая основное назначение подобных функций, детерминизм был бы там скорее минус чем плюс ))
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926684
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Еще метод isProbablePrime (в стеке вызовов внутренних методов) содержит искусственный
ограничитель раундов проверки Рабина. Машинально делая code-review глазами я застрял на нём сейчас.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }


Обратите внимание что чем больше разрядная сетка основного числа которое мы проверяем тем
меньше циклов Рабина идёт на выход. По всей видимости это искусственное ограничение
на сам метод чтобы не грузить пользователя долгим откликом.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926688
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЗабавно что isProbablePrime в методе МиллераРабина оставляет за собой право
вызывать функцию SecureRandom() очевидно для получения некой энтропии.
А может они в качестве финальной проверки используют генерацию RSA-ключа и
шифрование-дешифрование блока.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926689
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BigInteger не содержит зависимостей от крипто-библиотек. Скорее наоборот.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926690
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovА может
Пардон, брякнул не прочитав ссылку.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926693
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonBigInteger не содержит зависимостей от крипто-библиотек.
Для проверки на простоту не надо генерировать криптостойкий RSA ключ, поэтому
криптобиблиотеки и не нужны.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926728
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Модератор: Коллеги. Я потёр весь оффтопик касающийся SVN клиента и настроек. В дальнейшем давайте либо личным сообщением либо в отдельный топик
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926823
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tпамяти в x32 не хватает чтобы результаты обоих хранитьСравните контрольные суммы, а не сами результаты.
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38926961
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дима. Я на выходных попробую запилить Рабина-Миллера. И посмотреть
его погрешность в определении простоты.

Особо меня заинтересовало как можно устранить источник энтропии
внутри функции. Иначе это путает все карты.

offОказывается Рабин - это не только фамилия. Это еще и титул учёного-толкователя ("раввин").
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38927133
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДима. Я на выходных попробую запилить Рабина-Миллера. И посмотреть
его погрешность в определении простоты.
Всё уже украдено до нас - https://oeis.org/A001262 https://oeis.org/A020229 https://oeis.org/A074773
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38927144
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
http://web.mit.edu/primes/materials/2014/conf/5-1-Narayanan.pdf

Модератор: Не ленись давать комментарии к ссылкам, пожалуйста
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38927176
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone, почитал ссылки. А на каком языке написан код в разделе 'PROG' ?
...
Рейтинг: 0 / 0
Генератор простых чисел (до 10^9 за 5 сек)
    #38927268
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonBarlone, почитал ссылки. А на каком языке написан код в разделе 'PROG' ?
https://en.wikipedia.org/wiki/PARI/GP
...
Рейтинг: 0 / 0
25 сообщений из 402, страница 10 из 17
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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