Forth http://fforum.winglion.ru/ |
|
Сумма простых чисел http://fforum.winglion.ru/viewtopic.php?f=19&t=2914 |
Страница 1 из 1 |
Автор: | AlexF [ Вс янв 06, 2013 11:03 ] |
Заголовок сообщения: | Сумма простых чисел |
Ниже свое решение задачи с Хабраhttp://habrahabr.ru/post/164515. Заинтересовало: - сравнить скорость разработки с С++; - скорость работы; - просто мозги поразмять. Фактически просят найти все простые числа в заданном интервале за минимальное время. Результаты здесь http://habrahabr.ru/post/164567 Свой вариант получился медленный, однопоточный. Использующий минимум памяти. Все операции выполяются на стеке. Оосбенность использования числа двойной точности для суммы, т.к суммы получаются довольно большие. В реализации много операций со стеком, поэтому в варианте 3.2 решил сравнить размещение суммы отдельно в памятии. Вывод: кол-во стековых операций не уменьшилось, сложность программы выросла, время работы программы тоже. В планах: - сделать многопоточную версию; - с сохранением найденных простых чисел. Было бы интересно сравнить с другими реализациями. Код: ( Задача с хабра: http://habrahabr.ru/post/164515
Программа должна прочитать из стандартного потока ввода целое число N {от 1 до 230}, напечатать сумму простых чисел меньших либо равных N. Статья на Вики: http://ru.wikipedia.org/wiki/Простое_число Результаты конкурса: http://habrahabr.ru/post/164567 Достигнутые результаты: i7-2700K (Win7 64 / 1908937595474167 / 0.465 s Тесты 1000 --> 76127 100000 --> 454396537 1000000 --> 37550402023 980000000 --> 23783220704190493 ) REQUIRE CASE-INS lib/ext/caseins.f \ Регитро независимость WINAPI: GetTickCount KERNEL32.DLL \ DIS-OPT \ Отключение оптимизации \ ---------- Вар. 1 Простой перебор чисел в поисках простого -------------- : isSimple? ( n -- 0|1 ) dup 2/ 2 do dup i mod if else drop unloop 0 exit then loop drop 1 ; : SumProst ( n -- i ) \ n > 5 1+ 10 swap 5 do i isSimple? if i + then loop ; \ ----------------------- Вар 3. Перебор возможно протсых чисел------------------------------------ : NextP ( n -- n1 ) \ n >= 5 dup 3 + 6 mod + ; : isNotSimple ( n -- n 1|0 ) 5 ( n p ) begin 2dup dup * 1- ( n p n p**2 ) > while 2dup mod 0= if drop 1 exit then NextP repeat drop 0 ; : NextSimple3 ( n1 -- n2 ) \ n>=5 NextP begin isNotSimple while NextP repeat ; : SumProst3 ( n -- dsum ) 17 0 rot 7 ( dsum n p ) begin NextSimple3 2dup > while ( dsum n p ) swap ( dsum p n ) over ( dsum p n p ) >r >r 0 D+ r> r> repeat 2drop ; \ ---- Tест 3.2 Если уменьшть кол-во стековых операций и переместить в память? CREATE AddSimpl_ 8 ALLOT \ стек указателей (растет в сторону увеличеня адресов)) : AddSimple ( p -- p ) dup 0 AddSimpl_ 2@ D+ AddSimpl_ 2! ; : SumProst3.2 ( n -- ) 17 0 AddSimpl_ 2! 7 ( n p ) begin NextSimple3 2dup > while AddSimple repeat 2drop ; \ --------------- Test ------ : test1 ( n -- n ) GetTickCount over dup ." Test1: " . ." --> " SumProst . GetTickCount - ABS ." time " . ." ms." CR ; : test3 GetTickCount over dup ." Test3: " . ." --> " SumProst3 D. \ over SumProst3 D. CR \ 980000000 SumProst4 D. CR GetTickCount - ABS ." time " . ." ms." CR ; : test3.2 GetTickCount over dup ." Test.1: " . ." --> " SumProst3.2 AddSimpl_ 2@ D. GetTickCount - ABS ." time " . ." ms." CR ; \ ------------- Execute ----------- 100000 test1 test3 test3.2 |
Автор: | AlexF [ Пн янв 07, 2013 14:45 ] |
Заголовок сообщения: | Re: Сумма простых чисел |
Вариант с хранением ранее вычисленных простых чисел. За счет сокращения кол-ва переборов на этапе проверке простое число или нет скорость выросла в 5-ть раз. Код ниже. Результат несколько неожиданный на первый взгляд: вычисления в памяти в современных CPU прозоводятся много эффективно, а память медленная. Сделанные оценки показали что выигрыш должен был быть -- средний цикл проверки в чисто алгоритмическом варианте составлял 65 итераций. То использование в проверках предварительно найденных простых чисел сократил кол-во итераций в 2 раза Дальше ускорение можно получить за счет более точного прогнозирования следующего простого числа. Одним из вариантов, который использовался победителями конкурса, применение алгоритма "Решето Эрастофена". Код: 1000000 constant SimplsMaxCount
0 value Simpls_ 1 value SimplsLastI : SimplsInit SimplsMaxCount 2+ cells allocate throw to Simpls_ 5 Simpls_ ! 7 Simpls_ 4 + ! ; : Simpls[] ( i -- n ) cells Simpls_ + @ ; : AddSimple ( n -- n ) SimplsLastI SimplsMaxCount < if dup SimplsLastI 1+ dup to SimplsLastI cells Simpls_ + ! then ; : isNotSimple5 ( n -- n 1|0 ) 0 ( n ip ) begin 2dup Simpls[] dup * 1- ( n ip n p**2 ) > while 2dup Simpls[] mod 0= if drop 1 exit then 1+ repeat drop 0 ; : NextSimple5 ( n1 -- n2 ) \ n>=5 NextP begin isNotSimple5 while NextP repeat AddSimple ; : SumProst5 ( n -- dsum ) 17 0 rot 7 ( dsum n p ) begin NextSimple5 2dup > while ( dsum n p ) swap ( dsum p n ) over ( dsum p n p ) >r >r 0 D+ r> r> repeat 2drop ; |
Автор: | chess [ Пн янв 07, 2013 22:06 ] |
Заголовок сообщения: | Re: Сумма простых чисел |
Код: \ Реализация решета Сундарама sito: ( n -- sum ) \ сумма всех простых чисел в диапазоне от 1 до n 2/ DUP Len! 1- 2/ n! 0 sum! Len ALLOCATE THROW addr! addr Len ERASE n 1 DO I 1+ 1 DO 1 I J + 2 J * I * + DUP 1+ Len < IF addr + C! ELSE 2DROP THEN LOOP LOOP 2 . addr Len 1- + addr 1+ DO I C@ 0= IF I addr - 2* 1+ DUP . sum + is sum THEN LOOP addr FREE THROW sum 2+ CR . ; \ манипуляторный аналог решения sito1: ( n -- sum ) 1/1`2/d'2!`1-`2/'3!`0'4!2'hao'5!52[ERASE]_ \ инициализация 3`1DI`1+`1D`1IJ+`2IJ**+d`1+2<i5+we`xtLL_ \ разметка непростых `2.52+`1-5`1+DIbZiI5-`2*`1+d.4+'4!tL4`2+\.5'hfo ; \ вывод простых и сборка мусора ps 1. решение без перехода на разрядность 64 ( n =< 130000 ) 2. все простые числа 'записываются' в хипе 3. исходник транслировать файлом spf4e.exe(из репозитория https://github.com/chess2007/-chess) |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |