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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - *битовое преобразование числа
Автор Сообщение
  Заголовок сообщения:   Ответить с цитатой
вопрос писал(а):
Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах

не верно, так как обычно к более простым решениям.
А более простые решения, как раз чаще алгоритмические.
А вообще форт не гнушается ни одним из подходов
Сообщение Добавлено: Ср апр 23, 2008 13:39
  Заголовок сообщения:   Ответить с цитатой
кто склоняется, а кто нет. если памяти мало особо не посклоняешься
Сообщение Добавлено: Вт апр 22, 2008 20:34
  Заголовок сообщения:   Ответить с цитатой
вопрос -
Цитата:
Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах


просто Форт - это эффективность - основанная на понимании задачи и анализе её решений.. не более..
Сообщение Добавлено: Вт апр 22, 2008 16:13
  Заголовок сообщения:   Ответить с цитатой
вопрос писал(а):
Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах

С этим вообще говоря не согласен. Лучший вариант выбирается взависимости от ситуации.
Сообщение Добавлено: Вт апр 22, 2008 12:14
  Заголовок сообщения:   Ответить с цитатой
Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах
Сообщение Добавлено: Вт апр 22, 2008 12:00
  Заголовок сообщения:   Ответить с цитатой
Для коллекции еще асмовский вариант табличного решения

Код:
CREATE [b-wrd] 0x10000 ALLOT

REQUIRE IDN ~chess\assm\sp-assm.f

: gen-lut
[b-wrd] 0x10000 + [b-wrd]
DO I [b-wrd] -
   C^C C-- L1: C++ B=L\A C=B\A0 L1 J0<> A=C
   I C!
LOOP ;  gen-lut

: transform
[ ' [b-wrd] >CS D=#
B^B wB=wA bC=@bBD $ 10 #A>> bC+@bAD
A^A A++ A<< A--
;

: dt
DUP A^A CPUID DA=TSC

0xAAAAAAAA transform

DUP A^A CPUID DA=TSC ROT -
DUP A^A CPUID DA=TSC
DUP A^A CPUID DA=TSC SWAP - - .
;

STARTLOG

SEE transform

CR
dt dt dt dt dt dt dt dt dt dt

лог
Код:
CODE transform
5B5393 C7C253B55600     MOV     EDX , # 56B553
5B5399 33DB             XOR     EBX , EBX
5B539B 66               D16:
5B539C 8BD8             MOV     BX , AX
5B539E 8A0C13           MOV     CL , [EBX] [EDX]
5B53A1 C1E810           SHR     EAX , 10
5B53A4 020C10           ADD     CL , [EAX] [EDX]
5B53A7 33C0             XOR     EAX , EAX
5B53A9 40               INC     EAX
5B53AA D3E0             SHL     EAX , CL
5B53AC 48               DEC     EAX
5B53AD C3               RET     NEAR
END-CODE

481 32 32 32 11 11 11 11 11 11


Все-таки чуть быстрее нетабличных вариантов и по объему кода меньше,
а память для таблицы можно взять из хипа-там ее много.
Сообщение Добавлено: Вт апр 22, 2008 11:54
  Заголовок сообщения:   Ответить с цитатой
Еще один быстрый нетабличный вариант на ассме
(примерно одинаковый по быстродействию с табличным - при таблице в 64кбайт)

Код:
REQUIRE IDN ~CHESS\ASSM\SP-ASSM.F

: transform
C=A $ 55555555 C&# $ AAAAAAAA A&#      1A>> A+C
C=A $ 33333333 C&# $ CCCCCCCC A&# $  2 #A>> A+C
C=A $ 0F0F0F0F C&# $ F0F0F0F0 A&# $  4 #A>> A+C
C=A $ 00FF00FF C&# $ FF00FF00 A&# $  8 #A>> A+C
C=A $ 0000FFFF C&# $ FFFF0000 A&# $ 10 #A>> C+A
$ 1 A=# A<< A--
;

: dt  \ время без учета ошибки измерения
DUP A^A CPUID DA=TSC
0xAAAAAAAA transform
DUP A^A CPUID DA=TSC ROT - . ;

: dtR \ время с учетом ошибки измерения(близкое к реальному)
DUP A^A CPUID DA=TSC
0xAAAAAAAA transform
DUP A^A CPUID DA=TSC ROT -

DUP A^A CPUID DA=TSC
DUP A^A CPUID DA=TSC SWAP - - .
;

STARTLOG

SEE transform

CR dt dt dt dt dt dt dt dt dt dt

CR dtR dtR dtR dtR dtR dtR dtR dtR dtR dtR
лог
Код:
CODE transform
5A52FF 8BC8             MOV     ECX , EAX
5A5301 81E155555555     AND     ECX , # 55555555
5A5307 81E0AAAAAAAA     AND     EAX , # AAAAAAAA
5A530D D1E8             SHR     EAX , 1
5A530F 03C1             ADD     EAX , ECX
5A5311 8BC8             MOV     ECX , EAX
5A5313 81E133333333     AND     ECX , # 33333333
5A5319 81E0CCCCCCCC     AND     EAX , # CCCCCCCC
5A531F C1E802           SHR     EAX , 2
5A5322 03C1             ADD     EAX , ECX
5A5324 8BC8             MOV     ECX , EAX
5A5326 81E10F0F0F0F     AND     ECX , # F0F0F0F
5A532C 81E0F0F0F0F0     AND     EAX , # F0F0F0F0
5A5332 C1E804           SHR     EAX , 4
5A5335 03C1             ADD     EAX , ECX
5A5337 8BC8             MOV     ECX , EAX
5A5339 81E1FF00FF00     AND     ECX , # FF00FF
5A533F 81E000FF00FF     AND     EAX , # FF00FF00
5A5345 C1E808           SHR     EAX , 8
5A5348 03C1             ADD     EAX , ECX
5A534A 8BC8             MOV     ECX , EAX
5A534C 81E1FFFF0000     AND     ECX , # FFFF
5A5352 81E00000FFFF     AND     EAX , # FFFF0000
5A5358 C1E810           SHR     EAX , 10
5A535B 03C8             ADD     ECX , EAX
5A535D C7C001000000     MOV     EAX , # 1
5A5363 D3E0             SHL     EAX , CL
5A5365 48               DEC     EAX
5A5366 C3               RET     NEAR
END-CODE

475 71 71 71 71 71 71 71 71 71
72 12 12 12 12 12 12 12 12 12 \ время близкое к реальному
Ok ( [20].. 65535 65535 65535 65535 65535 )
Сообщение Добавлено: Пн апр 21, 2008 17:21
  Заголовок сообщения:   Ответить с цитатой
forther писал(а):
Идея не в том, чтоб развернуть цикл, а в том, чтоб использовать LUT. Что, всегда больше и быстрее, чем итеративные методы. Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет.

Вот подтверждение этому:
Код:
: bits-word \ word --> i
DUP 0x5555 AND SWAP 0xAAAA AND 1 RSHIFT +
DUP 0x3333 AND SWAP 0xCCCC AND 2 RSHIFT +
DUP 0x0F0F AND SWAP 0xF0F0 AND 4 RSHIFT +
DUP 0x00FF AND SWAP 0xFF00 AND 8 RSHIFT +
;

CREATE [bits-word] 0x10000 ALLOT

: gen-tbl-word
[bits-word] 0x10000 + [bits-word]
DO  I [bits-word] - bits-word I C! LOOP ;  gen-tbl-word

: transform
DUP 0xFFFF AND
[bits-word] + C@ SWAP 16 RSHIFT
[bits-word] + C@ + 1 SWAP LSHIFT 1- ;

REQUIRE IDN ~CHESS\ASSM\SP-ASSM.F

: dtC
DUP A^A CPUID DA=TSC
0xAAAAAAAA transform
DUP A^A CPUID DA=TSC ROT - .  ;

STARTLOG
CR dtC dtC dtC dtC dtC dtC dtC dtC dtC dtC CR


лог
Код:
495 155 181 181 181 77 77 77 77 77

Ok ( [10].. 65535 65535 65535 65535 65535 )

Реализовано на Форте, если сделать на ассме, будет еще быстрее. Само собой нет зависимости
от количества единичных бит в числе.
Сообщение Добавлено: Пн апр 21, 2008 12:14
  Заголовок сообщения:   Ответить с цитатой
forther писал(а):
А сколько было до повышения быстродействия? Не могли бы вы использовать для сравнения свой первый вариант?

Легко посмотреть, старый же код моего первого решения я не убирал:

Код:
REQUIRE IDN ~CHESS\ASSM\SP-ASSM.F

: transform ( U --> u )
    B^B B++
L1: C=A C=L\C $ 1 Ca 1B<< A>>
L1  J0<>
    $ -1 A=aB
;
: dt1
DUP A^A CPUID DA=TSC
0x10000000 transform
DUP A^A CPUID DA=TSC ROT - . ;

: dt2
DUP A^A CPUID DA=TSC
0xAAAAAAAA transform
DUP A^A CPUID DA=TSC ROT - . ;

: dt3
DUP A^A CPUID DA=TSC
0xFFFFFFFF transform
DUP A^A CPUID DA=TSC ROT - . ;

CR dt1 dt1 dt1 dt1 dt1 dt1 dt1 dt1 dt1 dt1
CR dt2 dt2 dt2 dt2 dt2 dt2 dt2 dt2 dt2 dt2
CR dt3 dt3 dt3 dt3 dt3 dt3 dt3 dt3 dt3 dt3

лог
Код:
122 118 73 73 73 73 73 73 73 73
274 277 249 249 249 249 249 249 249 249
467 440 426 426 426 426 426 426 426 426

При малом количестве единиц в исходном числе этот вариант самый быстрый при увеличении
числа единиц до 16 по быстродействию переходит на 2-е место при максимальном количестве единиц переходит на 3 место. Вообщем быстродействие сильно зависит от количества единиц в исходном числе. Во втором моем варианте такой сильной зависимости нет и второй вариант стабильно на 1-м месте - мне это больше нравится.
Сообщение Добавлено: Пн апр 21, 2008 07:32
  Заголовок сообщения:   Ответить с цитатой
mOleg -
Цитата:
идея понятна, но реализация медленная однозначно
:)
Цитата:
вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!!
- прошу прощения.

forther -
Цитата:
Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет. A 4 гигасловная таблица вообще за одну индексацию все решит

угу - у меня и на 256 сердце кровью то обливалось, а уж за 65К я бы себя задушил :)
Сообщение Добавлено: Пн апр 21, 2008 07:29
  Заголовок сообщения:   Ответить с цитатой
forther писал(а):
Если места хватит big-table разместить ...

а если учесть, что уже на носу CELL=64 бита ;)
все правильно сказано, но я говорил о реализации.
и быстрее оно не всегда, хотя всегда больше.
с другой стороны, время выполнения таких алгоритмов фиксированное, в отличие от циклических, количество циклов в которых равно количеству бит для данного случая 8)
вобщем мерять надо!
Сообщение Добавлено: Пн апр 21, 2008 02:17
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
Jelsay писал(а):
тут имеется ввиду что именно в run-time нет циклов и ветвлений - что касается compile- time то, в принципе, таблицы можно прошить и в ручную

идея понятна, но реализация медленная однозначно.
Во-первых, команды /MOD скушают весь выигрыш от разворачивания цикла.
Во-вторых, у вас очень много получается обращений к памяти, к тому же невыравненных,
да и общее количество команд в цикле будет меньше, чем у вас 8( хотя идея развернуть цикл хороша.

Теперь замечание: вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!!
пожалуйста будте чуточку внимательнее.
P.S. Спасибо за участие


Идея не в том, чтоб развернуть цикл, а в том, чтоб использовать LUT. Что, всегда больше и быстрее, чем итеративные методы. Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет. A 4 гигасловная таблица вообще за одну индексацию все решит:

: U ( n -- n ) big-table + @ ;

Если места хватит big-table разместить ...
Сообщение Добавлено: Пн апр 21, 2008 02:10
  Заголовок сообщения:   Ответить с цитатой
Jelsay писал(а):
тут имеется ввиду что именно в run-time нет циклов и ветвлений - что касается compile- time то, в принципе, таблицы можно прошить и в ручную

идея понятна, но реализация медленная однозначно.
Во-первых, команды /MOD скушают весь выигрыш от разворачивания цикла.
Во-вторых, у вас очень много получается обращений к памяти, к тому же невыравненных,
да и общее количество команд в цикле будет меньше, чем у вас 8( хотя идея развернуть цикл хороша.

Теперь замечание: вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!!
пожалуйста будте чуточку внимательнее.
P.S. Спасибо за участие
Сообщение Добавлено: Пн апр 21, 2008 01:11
  Заголовок сообщения:   Ответить с цитатой
Код:
\ создаём таблицу количества единиц в байте (компайле тайм)
: (ED)  256 0 DO  0 I  8 0 DO 2 /MOD SWAP ROT + SWAP LOOP DROP C, LOOP ;
CREATE ED (ED) 
\ создаём таблицу спепеней двойки (компайле тайм)
: (ST) 1 32 0 DO DUP ,  2*  LOOP DROP ;
CREATE ST (ST)

\ транслируем   (ран тайм)
: BOSS  ( N --N) 
  256 /MOD 256 /MOD 256 /MOD
  ED + C@  >R   ED + C@  >R  ED + C@  >R   ED + C@  R> R> R> + + +
  CELL *  ST + @  1 -
;

2 BASE !   
01010101010101010101 DUP  CR . BOSS  CR .
KEY DROP BYE


тут имеется ввиду что именно в run-time нет циклов и ветвлений - что касается compile- time то, в принципе, таблицы можно прошить и в ручную :)
Сообщение Добавлено: Вс апр 20, 2008 09:48
  Заголовок сообщения:   Ответить с цитатой
Код:
\ некий набросок оптимизации по быстродействию
\ сейчас уже поздно писать - глаза слипаются - поэтому  проверю идею завтра :)
\
\ создаём таблицу количества единиц в байте - таблица займёт 256 байт  и будет выглядить примерно

так:
CREATE ED   0 C, 1 C, 1 C, 2 C, 1 C, 2 C, ...  ... 7 C, 8 C,
\ таблицу легче всего сгенерить
\
\ создаём таблицу спепеней двойки - таблица займёт 32 32-х битных слова  и будет выглядить

примерно так:
CREATE ST   1 , 2 , 4 , 8 , 16 , 32 , ...  ... 2147483648 , 4294967296 ,
\ эту таблицу тоже легче всего сгенерить
\
\ далее разбиваем входное исследуемое 32-х битное число на 4 байта примерно так: 
256 /MOD 256 /MOD 256 /MOD
\ для каждого байта,  используя его значение как индекс таблицы ED,  находим
\ соответствие количеству единиц в данном байте
\ суммируя полученные четыре числа получаем  общее количество единиц в исходном числе
\  примерно так (над оптимальностью надо подумать) :
ED + C@  >R   ED + C@  >R  ED + C@  >R   ED + C@  R > R> R> + + +
\
\  далее используя полученную сумму как индекс нахождения во второй таблице
\  находим степень числа  необходимую нам для решения задачи
ST + @
\  и,  благодаря подсказки WingLion,  получаем искомое:
\  1 -
\
\
\ прошу обратить внимание что в алгоритме нет ни одного цикла и\или ветвления
Сообщение Добавлено: Вс апр 20, 2008 01:14

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


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