| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Turbo
Site Admin
Зарегистрирован: 19.02.2006
Сообщения: 248
|
 Добавлено: Ср Апр 16, 2008 8:53 am Заголовок сообщения: Ваши решения для задачи В ожидании начала ZCon2008 |
 |
|
| В этой теме можно обсудить ваш подход к решению этой задачи. |
|
| Вернуться к началу |
|
 |
Michael
Зарегистрирован: 16.04.2008
Сообщения: 5
|
| Добавлено: Ср Апр 16, 2008 1:42 pm Заголовок сообщения: |
|
|
Интересно, как были получены результаты больше 33 млн (не говоря уже про 57) ?
Я решал классически - сначала проверял на маленькие делители
по предварительным табличкам делимости, потом (то что осталось) - вероятностным алгоритмом, ну и оставшиеся несколько непростых убивал просто табличкой...
Пытался делать предсказание длинных последовательностей непростых
(на основании генератора чисел), но получилось медленнее.
Наверное, можно было еще оптимизировать, но
блин не в четыре же раза. Очевидно фишка в подходах. |
|
| Вернуться к началу |
|
|
pperm
Зарегистрирован: 25.02.2007
Сообщения: 26
|
| Добавлено: Ср Апр 16, 2008 1:56 pm Заголовок сообщения: |
|
|
Ну можно получить не плохого результата если сделать что-то похожее на решето.
для числа a мы можем легко найти его номер в последовательности...
ну и значит может отметить те числа, которые не простые в нужном диапазоне... |
|
| Вернуться к началу |
|
|
levlam
Зарегистрирован: 25.01.2007
Сообщения: 11
|
| Добавлено: Ср Апр 16, 2008 2:17 pm Заголовок сообщения: |
|
|
| Michael писал(а): | | Интересно, как были получены результаты больше 33 млн (не говоря уже про 57) ? |
Хорошо написанное решето Эратосфена нашло все простые числа до 2147483647 примерно за 10 секунд, дальше все проверки на простоту шли за O(1). |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Ср Апр 16, 2008 3:28 pm Заголовок сообщения: |
|
|
Сначала проверка на делимость на простые до 71-го. В процессе выяснилось, что gcc не умеет оптимизировать деление на константу, пришлось делать самому.
Если не прокатило - тест Миллера-Рабина псевдопростоты по основанию 2. На некоторых числах тест обламывался - пришлось захардкодить их )
Все оптимизировано на асме )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
Michael
Зарегистрирован: 16.04.2008
Сообщения: 5
|
| Добавлено: Ср Апр 16, 2008 3:45 pm Заголовок сообщения: |
|
|
| Цитата: | | ...решето Эратосфена... |
Как все просто...
У меня была такая мысль, но, честно говоря, постеснялся хапать столько памяти (2^27 байт - по биту на нечетное число = 130 метров),
и дальше в эту сторону не думал...
Очевидно, зря 
Можно было бы, наверное, и выдумать, как поэкономить память...
Да и решето разогнать - то же Аткина к примеру... |
|
| Вернуться к началу |
|
|
Michael
Зарегистрирован: 16.04.2008
Сообщения: 5
|
| Добавлено: Чт Апр 17, 2008 1:22 pm Заголовок сообщения: |
|
|
| Werewolf писал(а): | | ...Все оптимизировано на асме ) |
А можно примерчик инлайна или Си-функции на асме.
А то я как ни пытался, так и не смог заставить GCC сожрать свои вставки 
Тупо синтаксис не проходил...
(Пытался степени двойки по модулю взять...) |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Чт Апр 17, 2008 2:15 pm Заголовок сообщения: |
|
|
Проверяет, является ли n сильно псевдопростым по основанию 2, возвращает '1' или '0'.
| Код: | char isPrimeRabin( unsigned n )
{
char b = '0';
asm (
"mov %7,%2;\
mov %2,%1;\
dec %1;\
bsf %1, %4;\
mov %4, %%ebp;\
shr %%cl, %1;\
mov %1, %4;\
mov %1, %6;\
and $0x1F, %4;\
mov $1, %1;\
shl %%cl, %1;\
mov $5, %%cl;\
shr %%cl, %6;\
jz exit;\
mov %1, %4;\
inc %5;\
xor %1, %1;\
div %2;\
cycle:;\
shr $1, %6;\
jz last;\
jnc mulx;\
mov %5, %3;\
mov %4, %1;\
mul %3;\
div %2;\
mov %5, %4;\
mov %3, %5;\
mulx:;\
mov %5, %1;\
mul %1;\
div %2;\
jmp cycle;\
last:;\
mov %5, %1;\
mul %4;\
exit:;\
div %2;\
cmp $1, %5;\
jz prime;\
lea 1(%5), %1;\
cmp %2, %1;\
jz prime;\
nexts:;\
mov %5, %1;\
mul %1;\
div %2;\
lea 1(%5), %1;\
cmp %2, %1;\
jz prime;\
dec %%ebp;\
jnz nexts;\
jmp end;\
prime:;\
movb $49, %0;\
end:;"
: "=m"(b)
: "a"(0),"S"(0),"b"(0),"c"(0),"d"(0),"D"(0),"r"(n));
return b;
} |
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
Michael
Зарегистрирован: 16.04.2008
Сообщения: 5
|
| Добавлено: Чт Апр 17, 2008 3:22 pm Заголовок сообщения: |
|
|
Круто!  
Ну... вроде бы так примерно я и писал
(в смысле синтаксиса, конечно )...
А оно на asm ругалось... Ну я и решил, что не поддерживается 
В кавычках, наверное, запутамшись   |
|
| Вернуться к началу |
|
|
xaxa3217
Зарегистрирован: 19.04.2008
Сообщения: 2
|
| Добавлено: Сб Апр 19, 2008 11:28 am Заголовок сообщения: |
|
|
| 2levlam а что это за хитрая реализация решета такая чтоб за 10 секунд все лишнее отсеять? |
|
| Вернуться к началу |
|
|
levlam
Зарегистрирован: 25.01.2007
Сообщения: 11
|
| Добавлено: Сб Апр 19, 2008 12:46 pm Заголовок сообщения: |
|
|
| xaxa3217 писал(а): | | 2levlam а что это за хитрая реализация решета такая чтоб за 10 секунд все лишнее отсеять? |
Я написал решето Эратосфена, которое шло только по остаткам 1, 7, 11, 13, 17, 19, 23 и 29 по модулю 30(как я потом узнал, эта оптимизация называется wheel factorization). Также исследуемый интервал пришлось разбить на более мелкие, чтобы память, используемая непосредственно алгоритмом, помещалась в кеш процессора. Это изменение дало очень существенное ускорение. |
|
| Вернуться к началу |
|
|
zhengxi
Зарегистрирован: 25.03.2008
Сообщения: 19
|
| Добавлено: Сб Апр 19, 2008 9:39 pm Заголовок сообщения: |
|
|
кстати, на spoj есть результат больше 200M (4.02сек на все числа)
http://www.spoj.pl/ranks/PRIC/ |
|
| Вернуться к началу |
|
|
Werewolf
Зарегистрирован: 16.03.2007
Сообщения: 28
|
| Добавлено: Вс Апр 20, 2008 10:50 am Заголовок сообщения: |
|
|
Японцы - маниаки )
_________________
Þá skelfur askr Yggdrasils, ok engi hlutr er þá óttalaus á himni eða jörðu. |
|
| Вернуться к началу |
|
|
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
