Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 06:25

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 42 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: сосчитать самую длинную последовательность двоичных единиц
СообщениеДобавлено: Пт окт 12, 2007 20:44 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
чтобы даром не пропадало 8)
случился такой в irc-е разговор:

[01:24][forther] а мне задачка на ум пришла
[01:24][mOleg] ?
[01:24][forther] сосчитать самую длинную последовательность единиц в 32 битном слове
[01:25][mOleg] это для конкурса?
[01:25][forther] т.е. для 0111000111101001101
[01:25][forther] ответ 4
[01:25][forther] нет, просто так
[01:26][forther] сам собираюсь сделать и подумал, что по простоте постановки она катит


Последний раз редактировалось mOleg Чт мар 20, 2008 16:41, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 12, 2007 20:48 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
[VoidVolker] тз на форуме я так понял уже не будет для числа еденичек?
[VoidVolker] вот что у меня получилось:

Код:
  VARIABLE #1N
  VARIABLE MAX_#1N

: 1SEARCH#  ( n -- #1 )
            0 #1N ! 0 MAX_#1N !
            32 0 DO DUP 1 I LSHIFT AND
                    #1N @ SWAP
                    IF 1+
                     ELSE MAX_#1N @ MAX MAX_#1N ! 0
                    THEN  #1N !
                 LOOP
            DROP MAX_#1N @ ;


Последний раз редактировалось mOleg Пт окт 12, 2007 21:22, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 12, 2007 20:51 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
[mOleg] forter, мое решение надо?
[forther] давайте, только я немножко попозже посмотрю. я свое пишу сейчас

Код:

   : ?long ( n --> nn a )
           0 BEGIN OVER 1 AND WHILE
                   1 + SWAP 1 RSHIFT SWAP
             REPEAT ;
             
   : skip0 ( n --> )
           BEGIN 1 OVER AND 0= WHILE
                 1 RSHIFT
           REPEAT ;
           
   : countit ( n --> # )
             0 BEGIN SWAP skip0 ?long ROT MAX OVER WHILE REPEAT NIP ;


[mOleg] в принципе, если забыть о переполнении стека и заботиться лишь о вычислениях можно обойтись без SWAP 1 RSHIFT SWAP
[mOleg] Которые некрасиво смотрятся
[mOleg] кстати, жаль, что команды R+ не предусмотрено
[mOleg] да, на вход skip0 нельзя подавать 0
[mOleg] то есть на входе countit нужна проверка на 0

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Последний раз редактировалось mOleg Пт окт 12, 2007 21:21, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 12, 2007 20:55 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
[mOleg] кстати, forther, ты сразу пишешь на t18 форте, или сначала решаешь на классическом форте, а потом адаптируешь на t18 ассемблер 8)
[forther] вот счас написал на обычном
[forther] а получилось, как на сифорте
[forther] вот, что у меня:

Код:
: bc ( u -- c )
      0 dup rot \ cnt max u
      31 0 do dup 0<
              if >r >r 1+ dup r> max r>
               else >r >r drop 0 r> r>
              then 2*
           loop drop ;


Последний раз редактировалось mOleg Пт окт 12, 2007 21:17, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 12, 2007 20:58 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
[in41] у мя тоже есть решение

Код:
  VARIABLE м
  VARIABLE х

  : m1 ( число -- макс_кол-во1 )
       м 0! х 0!
       BEGIN DUP WHILE
             DUP 1 AND
             IF х 1+!
              ELSE м @ х @ MAX м !
                   х 0!
                   \ I . м @ . х @ . CR
             THEN
          1 RSHIFT
       REPEAT DROP
       м @ х @ MAX ;
       
   \ конец
   BIN 0111000111101001101 DECIMAL m1 . 4 . CR
   BIN 0111000111111001101 DECIMAL m1 . 6 . CR
   BIN 0111000110101001101 DECIMAL m1 . 3 . CR
   BIN 0000000000000000000 DECIMAL m1 . 0 . CR
   BIN 11111111111111111111111111111111 DECIMAL m1 . 32 . CR
   BIN 0000000000000000001 DECIMAL m1 . 1 . CR
   \ 0123456789012345678901


[in41] forther: а с переменными нельзя было?
[in41] с ними проще! ;)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 12, 2007 22:48 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
25 слов. Так вроде поизящней будет. Но все равно лобовое решение :-(

Код:
: bc ( u -- c )
  0 dup rot     \ cnt max u
  begin ?dup while
    dup 0< if
      rot 1+ rot over max rot
    else
      rot drop 0 -rot
    then
    2*
  repeat
  nip
;



Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 13, 2007 02:09 
Не в сети

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
profiT писал(а):
Поэтому, их можно просто вывести за условие.

а как именно?


Вернуться к началу
 Профиль  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 13, 2007 13:40 
Не в сети

Зарегистрирован: Ср май 03, 2006 11:27
Сообщения: 1394
Откуда: St.Petersburg
Благодарил (а): 2 раз.
Поблагодарили: 11 раз.
Код:
REQUIRE /TEST ~profit/lib/testing.f

: LONGEST-BITS ( u -- c )
  0 DUP ROT     \ cnt max u
  BEGIN ?DUP WHILE
    DUP 0< IF
      SWAP 1+ SWAP
    ELSE
      >R MAX 0 R>
    THEN
    2*
  REPEAT
  MAX
;

/TEST

S" ~mak/lib/fpcnum.f" INCLUDED
REQUIRE TESTCASES ~ygrek/lib/testcase.f

TESTCASES longest bit sequence
(( 0111000111101001101B LONGEST-BITS -> 4 ))
(( 0111000111111001101B LONGEST-BITS -> 6 ))
(( 0111000110101001101B LONGEST-BITS -> 3 ))
(( 0000000000000000000B LONGEST-BITS -> 0 ))
(( 11111111111111111111111111111111B LONGEST-BITS -> 32 ))
(( 0000000000000000001B LONGEST-BITS -> 1 ))
END-TESTCASES


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 13, 2007 14:28 
Только max и cnt местами переставить

Код:
: 1# ( u -- m )
  0 dup rot     \ max cnt u
  begin  ?dup while
    dup 0<   if >r 1+ r> 
          else >r max 0 r>
          then
    2*   repeat
  max
;

или
Код:
variable bbb
: 1# ( u -- m )
bbb ! 0 dup   
32 0 do bbb @  0< if 1+ else max 0 then
bbb @ 2* bbb !
loop max
;


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб окт 13, 2007 14:34 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Дорабатываем форт-процессор.

Код:
signal data : std_logic_vector(MSB downto 0);
signal cnt, max_cnt : integer;


В декодере команд:

Код:
when 128 => if data(0) = '1' then max_cnt <= 1; cnt <= 1; else max_cnt <= 0; cnt <= 0; end if; index <= MSB;
                    data(MSB - 1 downto 0) <= data(MSB downto 1); ip <= ip + 1;
when 129 => if data(0) = '1' then cnt <= cnt + 1; if cnt + 2 > max_cnt then max_cnt <= cnt + 1; end if; else cnt <= 0;
                    data(MSB - 1 downto 0) <= data(MSB downto 1);
                    if index /= 0 then index <= index - 1; ip <= ip; else ip <= ip + 1;


Код:

Код:
128 129


По завершению в регистре max_cnt число единиц, можно класть его на стек.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 15, 2007 10:10 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Чтобы быстрее, можно
создать таблицу пред-решений . Если для 32-битного числа таблица будет слишком велика (2 в степени 32) то число можно побить на байты и создать таблицу на 2 в степени 8
каждому байту придать три значения "голова", "хвост" и "наибольшая последовательность посредине" и анализировать побайтно

p.s. на форте я такой алгоритм быстро не сделаю ...

преимущества - скорость (если нужна)

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 15, 2007 10:11 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хищник писал(а):
Дорабатываем форт-процессор.

Код:
signal data : std_logic_vector(MSB downto 0);
signal cnt, max_cnt : integer;

.

А что оно делает? Я что-то сразу не пойму

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 15, 2007 10:40 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
вопрос писал(а):
А что оно делает? Я что-то сразу не пойму

Заводит дополнительные регистры в процессоре и создает схему, которая по команде 128 инициализирует поиск последовательности, а по 129 - циклически пробегает по числу в регистре data. В процессор можно добавить два аппаратных примитива типа start_search и continue_search. Это, собственно, демонстрация аппаратного решения.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 15, 2007 12:17 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
мои 2 копейки...
количество циклов равно количеству смежных блоков бит
и нет никаких условий

Код:
: cbits ( val -- max_cont_bits_count )
0 >R BEGIN DUP WHILE
    DUP DUP 1+ XOR
    OVER INVERT DUP 1+ XOR 2 /
    SWAP DUP R> OR >R
    OR 1+ /
REPEAT

R> BEGIN 2 / DUP WHILE
    SWAP 1+ SWAP
REPEAT DROP ;

HEX
    EF1F cbits .
       0 cbits .
      10 cbits .
    AA55 cbits .
    FF10 cbits .
DECIMAL


мммм, чтобы никто не ломал голову, вот комментарий к коду:
Код:
#include <stdio.h>

bin(int v){int i;putchar(' ');for(i=31;i>=0;i--)putchar(1<<i&v?'1':'0');}
main(){int val, ones, zeros, maxones, result;

val=0xEF1F;
//val=0xAA00;
//val=0x10;

result = maxones = 0; while(val)
{
    ones  =    val ^  (  val +1);
    zeros = ((~val) ^ ((~val)+1)) / 2;
    maxones |= ones;

    bin(val); printf(" %x %x %x %x\n", val, ones, zeros, maxones);

    val = val / ((ones|zeros) + 1);
}

while (maxones>>=1) result++;
printf("%x\n", result);
}


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн окт 15, 2007 15:01 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
garbler писал(а):
мои 2 копейки...

Неточность - вместо / нужно U/ (числа могут быть и отрицательными)

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


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

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


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

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


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

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