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/