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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Сб апр 19, 2008 19:32 
Не в сети

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

то получите степень двойки


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

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

p.s. долго пытался въехать в условие, и понял, что слова "значащие биты" в условии надо заменить на "единичные биты", а то дикая путаница в терминах, т.к. значащими считаются все биты, что справа от первой единицы, встретившейся в записи числа, и они изначально все вправо "прижаты".

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


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

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

спасибо за ценное замечание! учтем при создании следующего задания.

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


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

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Код:
\ некий набросок оптимизации по быстродействию
\ сейчас уже поздно писать - глаза слипаются - поэтому  проверю идею завтра :)
\
\ создаём таблицу количества единиц в байте - таблица займёт 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 09:48 
Не в сети

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Код:
\ создаём таблицу количества единиц в байте (компайле тайм)
: (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 то, в принципе, таблицы можно прошить и в ручную :)


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

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

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

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

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


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
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:17 
Не в сети
Moderator
Moderator
Аватара пользователя

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

а если учесть, что уже на носу CELL=64 бита ;)
все правильно сказано, но я говорил о реализации.
и быстрее оно не всегда, хотя всегда больше.
с другой стороны, время выполнения таких алгоритмов фиксированное, в отличие от циклических, количество циклов в которых равно количеству бит для данного случая 8)
вобщем мерять надо!

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


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

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
mOleg -
Цитата:
идея понятна, но реализация медленная однозначно
:)
Цитата:
вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!!
- прошу прощения.

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

угу - у меня и на 256 сердце кровью то обливалось, а уж за 65К я бы себя задушил :)


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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-м месте - мне это больше нравится.

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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 )

Реализовано на Форте, если сделать на ассме, будет еще быстрее. Само собой нет зависимости
от количества единичных бит в числе.

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Еще один быстрый нетабличный вариант на ассме
(примерно одинаковый по быстродействию с табличным - при таблице в 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 )

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


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

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

Код:
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


Все-таки чуть быстрее нетабличных вариантов и по объему кода меньше,
а память для таблицы можно взять из хипа-там ее много.

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


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

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

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


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

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

С этим вообще говоря не согласен. Лучший вариант выбирается взависимости от ситуации.

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


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

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


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

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


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

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