ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
25 сообщений из 402, страница 15 из 17
  15  все
Генератор простых чисел (до 10^9 за 5 сек)
    #39347913
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Доброго времени суток господа. Смотрю так буйно бились и подостыли?) Я какоето время тоже простыми числами интересуюсь, вот появилось пару недель свободных засел.. Бегло пролистал топик, пока мулач Аткина. Домучал его х32 до 6FFFFFFF размерности.. дальше Аут оф мемори.. а вы вроде все х32 значения им считали? упаковывали байты в биты? (типа по памяти в раз экономи) на производительность пофигу.
...
Рейтинг: 0 / 0
15.11.2016, 21:07
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39347962
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
VodoleYka,

Битовая карта всех 32-битных чисел занимает 4Г/8бит=512 МБ (без упаковки).
Такое помещается обычно в памяти, если конечно не совсем древний комп.
...
Рейтинг: 0 / 0
15.11.2016, 23:54
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348028
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Anatoly Moskovsky, да не древний.. один 7ая корка,16ГБ . 2ой 2ух процессорный ксенон 8гб.. та реализация Аткина что у меня попалась 1 бит занимает 1 байт.(с вики стянул потом допиливал..) т.е в моем случае как раз 4ГБ памяти и надо. и на переполнение 4*x*x+y*y наступил.. пол часа в отладке сидел, не мог понять почему таблицы портятся.. Но это скорее мои личные проблемы.
я незнаю может комуто будет интересно, страдал фигней, оптимизировал тривиальный брут простых чисел. Кину сюда на всяк случай, может комуто сгодится. Вроде оптимальней некуда

Код: 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.
function isPrime_asm(dwIn,Prime_tlb:DWord):boolean ;assembler;
asm
        mov ecx,eax //eax-dwIn  save for work
        mov esi,edx //edx-table prime numbers
@loop:
        lodsd       //load prime from tlb
        test eax,eax
        jz @prime

        mov ebx,eax //data from Prime_tlb
        xor edx,edx
        mov eax,ecx//copy dwIn
        div ebx
        test edx,edx
        jz @not_prime
        nop
        jmp @loop
//-------------------
@not_prime:
        xor eax,eax
        jmp @exit
//-------------------
@prime:
        mov [esi-4],ecx  //save prime
        mov eax,1
@exit:
end;
...
Рейтинг: 0 / 0
16.11.2016, 07:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348033
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
и да.. 1. таблица с праймами.. должна быть 0-терминейт... вобщем по хорошему сразу файл с нулями.
2. и чтоб избегать 2ой проверки при каждом вызове isPrime_asm на предмет prime mod 5.. при старте таблу заполняю сраз до 5ки включительно. Производительность даже в таком виде конечно удручает.. на Коре и7.. гдето 70-80 дней 32бит праймы собираются.. но это скорее для эксперементов, а не для работы
ЗЫ. сори за дабл пост, но чет не вижу.. тут свои посты править можно после публикации?
...
Рейтинг: 0 / 0
16.11.2016, 07:26
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348168
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
VodoleYka,

Посты здесь править нельзя, к сожалению.
Никакой оптимизацией у тебя и не пахнет, причем алгоритм - перебора по таблице, причем до конца таблицы тоже вряд ли эффективен.
И конечно, чтобы проверить на простоту N - эту таблицу надо сначала всю заполнить, хотя бы до sqrt(N)
...
Рейтинг: 0 / 0
16.11.2016, 10:58
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348197
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Siemargl, оптимизация как бы по скорости.. все в регистрах. это раз. как бы профилировка по скорости. перебор до конца таблицы и вычисления sqrt тоже спорный вопрос, если кому надо добавляем ще 1 параметр, и еще одну проверку после loasd .. ток в так как простые числа идут 1 к 10. и множитель в 90 проц случаев находится быстрее чем + еще одна проверка.. и на каждом этапе вычислять корень. можно конечно его вычислять типа раз в 1000 итераций.. вобщем это на любителя.
Допилил Аткина.. судя по всему Done save primes 203 280 221 09:12:20.. верный результат.. ибо сошелся с primesieve-5.7.0
...
Рейтинг: 0 / 0
16.11.2016, 11:12
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348263
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
VodoleYkaDone save primes 203 280 221 09:12:20
Если это 9 часов, то это многовато.
Все должно быть в пределах нескольких минут.
...
Рейтинг: 0 / 0
16.11.2016, 11:57
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348288
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
VodoleYkaSiemargl, оптимизация как бы по скорости.. все в регистрах. это раз. как бы профилировка по скорости. перебор до конца таблицы и вычисления sqrt тоже спорный вопрос, если кому надо добавляем ще 1 параметр, и еще одну проверку после loasd .. ток в так как простые числа идут 1 к 10. и множитель в 90 проц случаев находится быстрее чем + еще одна проверка.. и на каждом этапе вычислять корень. можно конечно его вычислять типа раз в 1000 итераций.. вобщем это на любителя.
Допилил Аткина.. судя по всему Done save primes 203 280 221 09:12:20.. верный результат.. ибо сошелся с primesieve-5.7.0
Какие однако познания в оптимизации от дельфиста =)

Открываем сайт http://primesieve.org/#implementation и читаем, что сделали грамотные люди.
...
Рейтинг: 0 / 0
16.11.2016, 12:26
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348358
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Anatoly MoskovskyVodoleYkaDone save primes 203 280 221 09:12:20
Если это 9 часов, то это многовато.
Все должно быть в пределах нескольких минут.
9мин 12 сек 20 милисек. то я криво формат указал при выводе.. сори.
касательно быстрого извлечения корня и возведения в квадрат , а также умнжоения и деления.. простите.. но я вкурсе. я на асме с 94го года.. я вобщемто не спорю.. не нравится.. не берите.
...
Рейтинг: 0 / 0
16.11.2016, 13:38
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348361
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VodoleYkaи на каждом этапе вычислять корень. можно конечно его вычислять типа раз в 1000 итераций.. вобщем это на любителя.
Корень можно заменить на возведение в квадрат.
Суть корня в том что проверку по таблице нужно останавливать когда p i > sqrt(N) или по другому p i *p i > N где p i очередное простое, N проверяемое.
Для 32бит таблицу простых надо всего до 65536.
...
Рейтинг: 0 / 0
16.11.2016, 13:40
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348371
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima TVodoleYkaи на каждом этапе вычислять корень. можно конечно его вычислять типа раз в 1000 итераций.. вобщем это на любителя.
Корень можно заменить на возведение в квадрат.
Суть корня в том что проверку по таблице нужно останавливать когда p i > sqrt(N) или по другому p i *p i > N где p i очередное простое, N проверяемое.
Для 32бит таблицу простых надо всего до 65536.

ок
@loop:
lodsd //load prime from tlb
----------
cmp eax,FFFF
ja @prime
----------
test eax,eax
jz @prime

так легче? без корня. потеря в скорости не существенная. вместо FFFF sroot можно если хотите считать.
...
Рейтинг: 0 / 0
16.11.2016, 13:53
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348376
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
типа при самом фиговом варианте обработается 6488+54 праймов..
1..2^8 = 54
2^8..2^16 =6488
2^16..2^24=1 071 329
2^24..2^32=202 202 350

total 2^32 =203 280 221

вы лучше подскажите, кто знает сколько праймов в диапазоне 2^32..2^64.
...
Рейтинг: 0 / 0
16.11.2016, 13:57
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348382
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VodoleYkaтак легче?
Не знаю. По времени расчета какие изменения?

Можно квадраты не считать каждый раз, а добавить таблицу квадратов и сравниваться с ней.
...
Рейтинг: 0 / 0
16.11.2016, 14:00
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348386
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VodoleYkaвы лучше подскажите, кто знает сколько праймов в диапазоне 2^32..2^64.
в 2^64 примерно 415 828 534 307 635 091 простых (тут прикидывали 17471253 )
...
Рейтинг: 0 / 0
16.11.2016, 14:05
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348407
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima T,

cmp eax, $FFFF //0:00:37 vs 0:00:03
ja @prime
считай в 40 раз. при одинаковых условиях при расчете 1го 1кк чисел.. (не праймов.. просчет чисел от 0 до 1кк) и по идее дальше должна еще увеличиваться.
...
Рейтинг: 0 / 0
16.11.2016, 14:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348415
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Еще можно ускорить перебирая не все подряд, а пропуская кратные первым простым 2,3,5,7..., т.е. построить таблицу смещений.
Например для 2,3,5 таблица 4,2,4,2,4,6,2,6. т.е. проверять значения 5,7,11,13,17,19... Тут генератор 17479728
...
Рейтинг: 0 / 0
16.11.2016, 14:26
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348427
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima T,
это видел. я собственно этот код для себя писал. он все равно сильно много не насчитает. поэтому вылизывать его можно конечно, для перфекционизма, но как рабочий инструмент он почти бесполезен. не ну можно переползти на BigMath и считать дальше.. но смысл.
я тут кстати.. ввиде маразма запустил тест 1024 RSA modulus на праймах х32.. чуть позже сообщу время.. на глаз.. гдето 22ч либу там скрещивал сам.. там половина асм кода.. но там еще оптимизировать и оптимизировать.. но по крайней мере бОльшая часть кода там по уму сделана.
...
Рейтинг: 0 / 0
16.11.2016, 14:33
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348436
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно по минимуму, четные пропускать. Уже в два раза меньше проверять.

В том коде главная проблема в div. Деление достаточно тяжелая операция.
...
Рейтинг: 0 / 0
16.11.2016, 14:41
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348443
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima T,

ну совсем меня за лоха то не держи? и 5 пропускается в том числе.. четные просто inc 2 числам.. а 5 ща mod но можно еще ускорить, но повторюсь.. сильно не вижу смысла. я просто кинул кусок кода на асме, который в плане скорости и размера очень мал. поверь.. я в своей жизни на говнокода насмотрелся. я собственно последние лет 10 ток кейгены и пишу.. поэтому и гремучая смесь делфи+асм
...
Рейтинг: 0 / 0
16.11.2016, 14:51
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348449
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima T,
я тебе скажу по секрету.. там самая тяжелая операция это lodsd ... а регистровый div он еще на конвеере полу обрабатывается.. а вот работа с памятью.. в частности использования переменных... вот это самые большие тормоза. но никуда без таблицы праймов не дется. когдато у меня была табла про такты которые тратит проц на обработку комманды.. гдето пол года назад пытался найти свежую, уже не публикуют вроде ибо стало все сложно. ибо CISCO RISC процы уже отсутсвуют.. ща они все гибридные
...
Рейтинг: 0 / 0
16.11.2016, 14:55
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348505
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VodoleYkaработа с памятью.. в частности использования переменных... вот это самые большие тормоза. но никуда без таблицы праймов не дется.
для расчета 2^32 надо всего 6500 чисел или ~26 Кб под таблицу. Она целиком в кэш проца влезет и не будет никаких обращений в память.
...
Рейтинг: 0 / 0
16.11.2016, 15:42
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348573
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VodoleYkaDima T,

cmp eax, $FFFF //0:00:37 vs 0:00:03
ja @prime
считай в 40 раз. при одинаковых условиях при расчете 1го 1кк чисел.. (не праймов.. просчет чисел от 0 до 1кк) и по идее дальше должна еще увеличиваться.
Затестил, таблица квадратов дает ускорение еще на порядок.
Диапазон 2^16..2^24
ФункцияВремяis_prime()14.4 сек.is_prime2()1.2 сек.

 
Исходник
Код: 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.
#define PRIME_TABLE 6541

uint32_t primes[PRIME_TABLE]; // простые до 2^16
uint32_t primes2[PRIME_TABLE]; // квадраты до 2^16

// Перебор всего массива
bool is_prime(uint32_t n) {
	for(int i = 0; i < PRIME_TABLE; i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}

// Перебор до sqrt(n)
bool is_prime2(uint32_t n) {
	int i;
	for (i = 0; n >= primes2[i]; i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}

// Инициализация таблиц
void init_primes() {
	int pos = 1;
	primes[0] = 3;
	primes2[0] = 9;
	for (int i = 5; i < 65536; i += 2) {
		if (is_prime2(i)) {
			primes[pos] = i;
			primes2[pos] = i*i;
			pos++;
		}
	}
}

...
Рейтинг: 0 / 0
16.11.2016, 16:50
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348580
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
Dima T,

кстати.. о таблице праймов.. там на хабре статейка была.. на предмет того чтоб не хранить прайм, а хранить шаг между соседом. там получается что всего около 10ка праймов находятся на расстоянии больше 256 байт.. т.е можно просто хранить не
2 3 5 7 а
2 2 2 и т.д.. для тех, где расстояние больше тратить 3 байта типа 0 хх хх, так базу можно на 25 проц ужать, вобщемто без потери скорости работы.. все равно праймы друг за другом перебираются
...
Рейтинг: 0 / 0
16.11.2016, 17:02
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348591
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В 4 раза ужимается.
Где-то в топике выше обсуждали. Одного байта достаточно до 2^64. Максимум разницу 300 с небольшим находил. Дополнительно еще на 2 делил, т.к. разница всегда четная. Так в 1 байт шаг до 512 влазит.

Таблица квадратов не нужна, с умножением время точно такое же
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
bool is_prime3(uint32_t n) {
	int i;
	for (i = 0; n >= primes[i] * primes[i]; i++) {
		if (n % primes[i] == 0) return false;
	}
	return true;
}
...
Рейтинг: 0 / 0
16.11.2016, 17:15
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39348595
VodoleYka
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VodoleYka
Гость
ДА но тебе все равно нужен маркер какойто.. что число больше байта. вобщем и это детали
...
Рейтинг: 0 / 0
16.11.2016, 17:22
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 15 из 17
  15  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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