|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeny Sharandin 2:5020/755.12 22 Mar 2002 20:31:00
To : Andrew Doroshev
Subject : Пpостые числа...
--------------------------------------------------------------------------------
Привет Andrew!
20 марта 2002 года (а было тогда 16:00)
Andrew Doroshev в своем письме к Mike Gorchak писал:
AD> И чисел не 63Mб, и даже не 63M*sizeof(long) а немного больше 400Mб,
AD> если хранить именно так, как у Вас.
AD> Файл хранить лучше в виде одно нечётное число - один бит.
AD> Можно даже компактнее, почти вдвое, если заметить, что из каждых 30
AD> чисел кандидатов в простые только 8 Это 30*K+{1,07,11,13,17,19,23,29}.
AD> Прочие делятся на 2,3,5. Однако программулка сильно прибавляет в
AD> размере, и ещё сильнее теряет в скорости. Сейчас вполне можно
AD> позволить себе под каждое нечётное от 0 до 2^32 выделить бит памяти -
AD> всего 256М.
А еще лучше хранить только простые числа в диапазоне до sqrt(max). И никаких
битов - только байты. Тогда все с легкостью уместится в кеш любого современного
процессора, что вкупе с отсутствием битовых операций позволит увеличить
скорость на порядок. Исходник можно утянуть отсюда
http://www.bmstu.ru/~lid/benchs/pi.zip
Скомпилированная gnu pascal compiler программа на Athlon XP1500+ успевает
отстреляться за 10сек (без сохранения результатов в файл).
С уважением, Evgeny 22 марта 2002 года
---
* Origin: LID (2:5020/755.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
