[code]\ Реализация решета Сундарама

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 ; \ вывод простых и сборка мусора
[/code]
ps
1. решение без перехода на разрядность 64 ( n =< 130000 )
2. все простые числа 'записываются' в хипе
3. исходник транслировать файлом spf4e.exe(из репозитория [url]https://github.com/chess2007/-chess[/url])

Вариант с хранением ранее вычисленных простых чисел. За счет сокращения кол-ва переборов на этапе проверке простое число или нет скорость выросла в 5-ть раз. Код ниже.

Результат несколько неожиданный на первый взгляд: вычисления в памяти в современных CPU прозоводятся много эффективно, а память медленная. Сделанные оценки показали что выигрыш должен был быть -- средний цикл проверки в чисто алгоритмическом варианте составлял 65 итераций. То использование в проверках предварительно найденных простых чисел сократил кол-во итераций в 2 раза

Дальше ускорение можно получить за счет более точного прогнозирования следующего простого числа. Одним из вариантов, который использовался победителями конкурса, применение алгоритма "Решето Эрастофена".

[code]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
;[/code]

Ниже свое решение задачи с Хабра[url]http://habrahabr.ru/post/164515[/url]. Заинтересовало:
- сравнить скорость разработки с С++;
- скорость работы;
- просто мозги поразмять.
Фактически просят найти все простые числа в заданном интервале за минимальное время. Результаты здесь [url]http://habrahabr.ru/post/164567[/url]

Свой вариант получился медленный, однопоточный. Использующий минимум памяти. Все операции выполяются на стеке. Оосбенность использования числа двойной точности для суммы, т.к суммы получаются довольно большие.

В реализации много операций со стеком, поэтому в варианте 3.2 решил сравнить размещение суммы отдельно в памятии. Вывод: кол-во стековых операций не уменьшилось, сложность программы выросла, время работы программы тоже.

В планах:
- сделать многопоточную версию;
- с сохранением найденных простых чисел.

Было бы интересно сравнить с другими реализациями.

[code]( Задача с хабра: 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
[/code]