Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 19:49

...
Google Search
Forth-FAQ Spy Grafic

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




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

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Возможно, оно и велосипед, и придумано уже кем-то, но я не вдавался в подробности чужих решений, просто появилась мысля, и оно само собой решилось:

Код:
: RSHIFT 2/ ; ( доопределение слова, которого нету в Моем-Форте )
: BITS_COUNT ( nn -- n_ones)
   0 SWAP
   BEGIN DUP 0<> WHILE
   DUP RSHIFT AND
   SWAP 1+ SWAP
   REPEAT
   DROP
;

: TEST DECIMAL
10 BITS_COUNT  .
FF00 BITS_COUNT .
FFFF BITS_COUNT .
;
TEST


_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


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

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

Скорее всего уже придумано, но очень остроумно - считаю лучшим решением.
Для СПФ это будет так:
Код:
: BITS_COUNT ( nn -- n_ones)
   0 SWAP
   BEGIN DUP 0<> WHILE
   DUP 1 RSHIFT AND
   SWAP 1+ SWAP
   REPEAT
   DROP
;

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


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

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

создать таблицу пред-решений . Если для 32-битного числа таблица будет слишком велика (2 в степени 32) то число можно побить на байты и создать таблицу на 2 в степени 8

каждому байту придать три значения "голова", "хвост" и "наибольшая последовательность посредине" и анализировать побайтно

p.s. на форте я такой алгоритм быстро не сделаю ...
преимущества - скорость (если нужна)


логично, и это первое, что приходит в голову для решения.
Но тут есть маленький нюанс, мы изначально предполагали, что алгоритм должен работать на SEAforth чипе, а это сильно меняет дело, так как памяти у него 64 ячейки ОЗУ всего, и столько же ПЗУ, при том, что команды исполняются очень быстро. То есть именно алгоритмическое решение наиболее приемлемо.

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


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

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

создать таблицу пред-решений . Если для 32-битного числа таблица будет слишком велика (2 в степени 32) то число можно побить на байты и создать таблицу на 2 в степени 8

каждому байту придать три значения "голова", "хвост" и "наибольшая последовательность посредине" и анализировать побайтно

p.s. на форте я такой алгоритм быстро не сделаю ...
преимущества - скорость (если нужна)


логично, и это первое, что приходит в голову для решения.
Но тут есть маленький нюанс, мы изначально предполагали, что алгоритм должен работать на SEAforth чипе, а это сильно меняет дело, так как памяти у него 64 ячейки ОЗУ всего, и столько же ПЗУ, при том, что команды исполняются очень быстро. То есть именно алгоритмическое решение наиболее приемлемо.

Неужели такаяч маленькая ОЗУ? Это ужас!
А где размещать хоть что-то? Где хоть сам Форт лежит? или это только для стека?
Для предложенного алгоритма хватит около 1 кб

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


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

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
вопрос писал(а):
Чтобы быстрее, можно
создать таблицу пред-решений . Если для 32-битного числа таблица будет слишком велика (2 в степени 32) то число можно побить на байты и создать таблицу на 2 в степени 8
каждому байту придать три значения "голова", "хвост" и "наибольшая последовательность посредине" и анализировать побайтно
p.s. на форте я такой алгоритм быстро не сделаю ...

Для данной задачи нет смысла - кол-во дополнительных операций (и/или таблиц) будет превышать возможное увеличение скорости выполнения. :( Вот если бы последовательность была бы длиннее... ;)

_________________
With best wishes, in4.


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

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


Я, во всяком случае, этого не преполагал (посмотрите, если не лень, логи IRC)


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

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

Но тут есть маленький нюанс, мы изначально предполагали, что алгоритм должен работать на SEAforth чипе, а это сильно меняет дело, так как памяти у него 64 ячейки ОЗУ всего, и столько же ПЗУ, при том, что команды исполняются очень быстро. То есть именно алгоритмическое решение наиболее приемлемо.

Неужели такаяч маленькая ОЗУ? Это ужас!
А где размещать хоть что-то? Где хоть сам Форт лежит? или это только для стека?
Для предложенного алгоритма хватит около 1 кб

да, только это не байты, а 18 байтовые значения, в каждое из которых упаковывается до 4х команд.
стеки имеют размер в 10 ячеек(данных) и 9 ячеек(возвратов).

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


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

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

8) смотрю. Вы собирались решать задачку для SF, и предложили ее. Это задало направление, может и подсознательно.

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


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

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

Код:

: RSHIFT 2/ ; ( доопределение слова, которого нету в Моем-Форте )
: BITS_COUNT ( nn -- n_ones)
0 SWAP
BEGIN DUP 0<> WHILE
DUP RSHIFT AND
SWAP 1+ SWAP
REPEAT
DROP
;


Браво! Я думаю лучьше никто уже не придумает! можно вместо "dup 0<>" "?dup" поставить и drop в конце выкинуть. Но это не принципиально.


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

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

Для данной задачи нет смысла - кол-во дополнительных операций (и/или таблиц) будет превышать возможное увеличение скорости выполнения. :( Вот если бы последовательность была бы длиннее... ;)

Вообще, побайтовый алгоритм будет работать для последовательности любой длины (если число - массив байтов )
Но имеет ли это практическую ценность или так - просто интересно?

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


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

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

: bc ( n --> # )
     dup dup xor not push
: loop
     if dup 2* and .
        [ ' loop ] next
     then
     drop pop not ;
\ node}
\ 0 10 .adrs


вариант решения алгоритма WingLion-a на SEAforth.

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


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

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

0 {node

: bcm ( n --> # )
      0 a!
      begin while
            dup 2* and
            @a+ drop
      repeat
      drop a@ ;

\ тестируем так:
: proba 1377C bcm ;

node} runs proba

0 8 .adrs

\ go2d

да, особенность здесь такая. while не удаляет верхнее значение со стека - это раз.
регистр A при @a+ автоинкрементируется, но данная команда выкладывает ненужное на самом деле значение на стек, и его приходится удалять. Вместо 0 а! было бы правильнее(что ли) написать dup dup xor a! Но в памяти всеравно это занимает тот же объем, в то же время 0 a! и понятнее, и короче запись, и использует на одну ячейку в стеке меньше места, что при глубине стека данных в 10 ячеек очень даже чувствительно... Недостаток - портится содержимое переменной A.

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


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
Согласен по поводу dup dup xor not. Только стек данных напрягает, а потому вот так надо:
Код:
\ 0 {node

: bc ( n --> # )
     -1 push
: loop
     if
        dup 2* and .
        [ ' loop ] next
     then
     drop pop not ;
\ node}
\ 0 10 .adrs


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Алгоритм Wingliona на своем ассме \ в комментариях на ассме СПФ
Код:
L: maxlen-bits
$ 0 bB=b#      \ MOV  BL, # 0
L1: A|A        \ @@1: OR EAX, EAX
L2  JE         \      JE SHORT @@2
    C=A        \ MOV  ECX, EAX
    $ 1 #C>>   \ SHR  ECX, # 1
    A&C        \ AND  EAX, ECX
    bB++       \ INC  BL
L1  JMP        \      JMP SHORT @@1
L2: bA=bB      \ @@2: MOV AL, BL
L;             \ RET

Код:
CODE maxlen-bits
58E7F0 C6C300           MOV     BL , # 0
58E7F3 0BC0             OR      EAX , EAX
58E7F5 740B             JE      58E802
58E7F7 8BC8             MOV     ECX , EAX
58E7F9 C1E901           SHR     ECX , 1
58E7FC 23C1             AND     EAX , ECX
58E7FE FEC3             INC     BL
58E800 EBF1             JMP     58E7F3
58E802 8AC3             MOV     AL , BL
58E804 C3               RET     NEAR
END-CODE

Всего 21 байт, 9 команд(без учета RET), три регистра, время выполнения 275 нсек(проверял на P4-3000 при Ft=2.0 GHz ).
Интересно узнать сколько будет на SEA-Forth. Да забыл сказать, что выравнивание адресов для JMP специально не делал(это 11-ть NOP после команды OR) чтобы
байтов меньше было. С выравниванием время выполнения падает до 91 нсек.

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


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

Зарегистрирован: Сб май 06, 2006 12:01
Сообщения: 959
Откуда: Украина, Харьков
Благодарил (а): 2 раз.
Поблагодарили: 7 раз.
chess писал(а):
время выполнения 275 нсек(проверял на P4-3000 при Ft=2.0 GHz ).
С выравниванием время выполнения падает до 91 нсек.

Время выполнения этого алгоритма зависит от входных данных, а они не приведены. :(
Хорошо бы показать и способ получения временных параметров... я бы хотел проверить на своем компе ;)

_________________
With best wishes, in4.


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

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


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

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


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

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