Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Вс фев 25, 2018 11:41

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Сумма простых чисел
СообщениеДобавлено: Вс янв 06, 2013 11:03 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Ниже свое решение задачи с Хабра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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Сумма простых чисел
СообщениеДобавлено: Пн янв 07, 2013 14:45 
Не в сети

Зарегистрирован: Вс окт 15, 2006 13:05
Сообщения: 149
Откуда: Украина, Киев
Благодарил (а): 1 раз.
Поблагодарили: 0 раз.
Вариант с хранением ранее вычисленных простых чисел. За счет сокращения кол-ва переборов на этапе проверке простое число или нет скорость выросла в 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
;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Сумма простых чисел
СообщениеДобавлено: Пн янв 07, 2013 22:06 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2100
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 34 раз.
Код:
\ Реализация решета Сундарама

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)

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB