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

...
Google Search
Forth-FAQ Spy Grafic

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




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

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

Код:

\ битовое преобразование числа
: transform ( U --> u )
                 ;

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


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

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

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

\ EOF

STARTLOG

SEE transform

0x12493111 transform HEX CR . DECIMAL


лог
Код:
CODE transform
5A52FF 33DB             XOR     EBX , EBX
5A5301 43               INC     EBX
5A5302 8BC8             MOV     ECX , EAX
5A5304 0FBCC9           BSF     ECX , ECX
5A5307 8D4901           LEA     ECX , 1 [ECX]
5A530A D1E3             SHL     EBX , 1
5A530C D3E8             SHR     EAX , CL
5A530E 75F2             JNE     5A5302
5A5310 8D43FF           LEA     EAX , FF [EBX]
5A5313 C3               RET     NEAR
END-CODE

3FF
Ok

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


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

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

И на каком форте это можно проверить?
Где лежит необходимая библиотека?
Предпочтительно было бы решение на чистом форте, между прочим.

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
mOleg писал(а):
И на каком форте это можно проверить?
Где лежит необходимая библиотека?

Форт - дистрибутив 4.19(без CVS)
АССМ все там же: http://www.chess2007.nm.ru/~chess.zip

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


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

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

Код:
\ битовое преобразование числа
: transform ( U --> u )
            1 SWAP
            BEGIN DUP WHILE
                  DUP 1 AND IF SWAP 2* SWAP THEN
               1 RSHIFT
            REPEAT DROP 1 - ;

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


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

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Код:
VARIABLE A

:  COUNTED ( N -- )   BEGIN  2 /MOD  SWAP IF A @ 1+ A ! THEN DUP 0= UNTIL DROP ;
:  MAKE ( -- N)  A @ 0= IF 0 ELSE 1 A @ 1- 0 DO 2* 1+ LOOP THEN ;
: BOSS COUNTED MAKE ;

2 BASE !   001100110111 DUP .
CR  BOSS .

KEY DROP BYE


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

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Код:
VARIABLE A

:  COUNTED ( N -- )   BEGIN  2 /MOD  SWAP IF A @ 1+ A ! THEN DUP 0= UNTIL DROP ;
:  MAKE ( -- N)  A @ 0= IF 0 ELSE 1 A @ 1- 0 DO 2* 1+ LOOP THEN ;
: BOSS COUNTED MAKE ;

2 BASE !   001100110111 DUP .
CR  BOSS .

KEY DROP BYE


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

Зарегистрирован: Сб май 13, 2006 23:37
Сообщения: 380
Благодарил (а): 1 раз.
Поблагодарили: 10 раз.
Код:
: transform -1 begin over while 2* >r dup 1- and r> repeat nip invert ;


уже голова не по-сифортовски не думает, но работать должно ...
а как сравнивать будем, по скорости или по размеру?


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

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

Можно оценить и так и так.

Чтобы повысить быстродействие сделал вариант программы без медленной команды сканирования битов.
Программа JELSAY некорректно работает с граничными значениями(не учтено, что входное число беззнаковое).
Быстродействие ее около 12000 тиков, поэтому данные по ней не привожу.
По остальным программам соотношение и по времени исполнения и по объему кода одинаково и равно
примерно 3:2:1 соответственно для программ от mOlega, forthera и моей на ассме.
Здесь конечные значения времени ближе к пропускной способности, а не к латентности, так
как код работает уже в кэше.

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

: transformO ( U --> u )
            1 SWAP
            BEGIN DUP WHILE
                  DUP 1 AND IF SWAP 2* SWAP THEN
               1 RSHIFT
            REPEAT DROP 1 - ;

: transformF -1 BEGIN OVER WHILE 2* >R DUP 1- AND R> REPEAT NIP INVERT ;

L: transformC
    B^B B~ $ 0 A=#?
L1: L2 J0= 1B<< C=A A-- A&C L1 JMP
L2: B~ A=B  L;

: dtF
DUP A^A CPUID DA=TSC
0xAAAAAAAA transformF
DUP A^A CPUID DA=TSC ROT - . ;

: dtO
DUP A^A CPUID DA=TSC
0xAAAAAAAA transformO
DUP A^A CPUID DA=TSC ROT - . ;

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

STARTLOG

SEE transformO
SEE transformF
SEE transformC

CR dtO dtO dtO dtO dtO dtO dtO dtO dtO dtO CR
CR dtF dtF dtF dtF dtF dtF dtF dtF dtF dtF CR
CR dtC dtC dtC dtC dtC dtC dtC dtC dtC dtC CR
ЛОГ
Код:
CODE transformO
5A52FF C745FC01000000   MOV     FC [EBP] , # 1
5A5306 8D6DFC           LEA     EBP , FC [EBP]
5A5309 90               XCHG     EAX, EAX
5A530A 90               XCHG     EAX, EAX
5A530B 90               XCHG     EAX, EAX
5A530C 0BC0             OR      EAX , EAX
5A530E 0F8426000000     JE      5A533A  ( transformO+3B  )
5A5314 8BC8             MOV     ECX , EAX
5A5316 81E101000000     AND     ECX , # 1
5A531C 7417             JE      5A5335
5A531E 8B5500           MOV     EDX , 0 [EBP]
5A5321 894500           MOV     0 [EBP] , EAX
5A5324 8BC2             MOV     EAX , EDX
5A5326 8D044500000000   LEA     EAX , 0 [EAX*2]
5A532D 8B5500           MOV     EDX , 0 [EBP]
5A5330 894500           MOV     0 [EBP] , EAX
5A5333 8BC2             MOV     EAX , EDX
5A5335 C1E801           SHR     EAX , 1
5A5338 EBD2             JMP     5A530C
5A533A B8FFFFFFFF       MOV     EAX , # FFFFFFFF
5A533F 034500           ADD     EAX , 0 [EBP]
5A5342 8D6D04           LEA     EBP , 4 [EBP]
5A5345 C3               RET     NEAR
END-CODE

CODE transformF
5A535F 8945FC           MOV     FC [EBP] , EAX
5A5362 B8FFFFFFFF       MOV     EAX , # FFFFFFFF
5A5367 8D6DFC           LEA     EBP , FC [EBP]
5A536A 90               XCHG     EAX, EAX
5A536B 90               XCHG     EAX, EAX
5A536C 837D0000         CMP     0 [EBP] , # 0
5A5370 0F8416000000     JE      5A538C  ( transformF+2D  )
5A5376 8D044500000000   LEA     EAX , 0 [EAX*2]
5A537D 50               PUSH    EAX
5A537E 8B4500           MOV     EAX , 0 [EBP]
5A5381 8D48FF           LEA     ECX , FF [EAX]
5A5384 23C1             AND     EAX , ECX
5A5386 894500           MOV     0 [EBP] , EAX
5A5389 58               POP     EAX
5A538A EBE0             JMP     5A536C
5A538C F7D0             NOT     EAX
5A538E 8D6D04           LEA     EBP , 4 [EBP]
5A5391 C3               RET     NEAR
END-CODE

CODE transformC
5A53AB 33DB             XOR     EBX , EBX
5A53AD F7D3             NOT     EBX
5A53AF 81F800000000     CMP     EAX , # 0
5A53B5 7409             JE      5A53C0
5A53B7 D1E3             SHL     EBX , 1
5A53B9 8BC8             MOV     ECX , EAX
5A53BB 48               DEC     EAX
5A53BC 23C1             AND     EAX , ECX
5A53BE EBF5             JMP     5A53B5
5A53C0 F7D3             NOT     EBX
5A53C2 8BC3             MOV     EAX , EBX
5A53C4 C3               RET     NEAR
END-CODE

870 395 318 303 303 303 303 303 303 303

261 270 222 205 203 201 201 203 203 203

188 171 156 146 133 133 133 133 133 133

Ok ( [30].. 65535 65535 65535 65535 65535 )

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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Для сравнения работы оптимизаторов SPF и VFX приведу код для программ от forthera и mOlega
который дает транслятор VFX. Много общего. Вершина стека параметров в VFX как и в SWIFT-е
в EBX, а не в EAX (SPF). Это рациональней, так как аккумулятор свободен и с ним можно работать более короткими и быстрыми командами не затрагивая стек параметров.
А так результаты близки к тому что дает SPF.
Про быстродействие VFX-кода этих программ сказать пока ничего не могу. :(

Код:
: transformF -1 BEGIN OVER WHILE 2* >R DUP 1- AND R> REPEAT NIP INVERT ;

see transformF

TRANSFORMF
( 004ABBC0    8D6DFC )                LEA       EBP, [EBP+-04]
( 004ABBC3    895D00 )                MOV       [EBP], EBX
( 004ABBC6    BBFFFFFFFF )            MOV       EBX, FFFFFFFF
( 004ABBCB    90 )                    NOP
( 004ABBCC    90 )                    NOP
( 004ABBCD    90 )                    NOP
( 004ABBCE    90 )                    NOP
( 004ABBCF    90 )                    NOP
( 004ABBD0    837D0000 )              CMP       [EBP], 00
( 004ABBD4    0F8412000000 )          JZ/E      004ABBEC
( 004ABBDA    D1E3 )                  SHL       EBX, 1
( 004ABBDC    53 )                    PUSH      EBX
( 004ABBDD    8B5D00 )                MOV       EBX, [EBP]
( 004ABBE0    4B )                    DEC       EBX
( 004ABBE1    235D00 )                AND       EBX, [EBP]
( 004ABBE4    5A )                    POP       EDX
( 004ABBE5    895D00 )                MOV       [EBP], EBX
( 004ABBE8    8BDA )                  MOV       EBX, EDX
( 004ABBEA    EBE4 )                  JMP       004ABBD0
( 004ABBEC    F7D3 )                  NOT       EBX
( 004ABBEE    8D6D04 )                LEA       EBP, [EBP+04]
( 004ABBF1    C3 )                    NEXT,
( 50 bytes, 22 instructions )

: transformO ( U --> u )
            1 SWAP
            BEGIN DUP WHILE
                  DUP 1 AND IF SWAP 2* SWAP THEN
               1 RSHIFT
            REPEAT DROP 1 - ;

see transformO

TRANSFORMO
( 004ABC20    8D6DFC )                LEA       EBP, [EBP+-04]
( 004ABC23    C7450001000000 )        MOV       DWord Ptr [EBP], 00000001
( 004ABC2A    90 )                    NOP
( 004ABC2B    90 )                    NOP
( 004ABC2C    90 )                    NOP
( 004ABC2D    90 )                    NOP
( 004ABC2E    90 )                    NOP
( 004ABC2F    90 )                    NOP
( 004ABC30    85DB )                  TEST      EBX, EBX
( 004ABC32    0F8419000000 )          JZ/E      004ABC51
( 004ABC38    8BD3 )                  MOV       EDX, EBX
( 004ABC3A    83E301 )                AND       EBX, 01
( 004ABC3D    8BDA )                  MOV       EBX, EDX
( 004ABC3F    0F8408000000 )          JZ/E      004ABC4D
( 004ABC45    8B5500 )                MOV       EDX, [EBP]
( 004ABC48    D1E2 )                  SHL       EDX, 1
( 004ABC4A    895500 )                MOV       [EBP], EDX
( 004ABC4D    D1EB )                  SHR       EBX, 1
( 004ABC4F    EBDF )                  JMP       004ABC30
( 004ABC51    8B5D00 )                MOV       EBX, [EBP]
( 004ABC54    83C3FF )                ADD       EBX, -01
( 004ABC57    8D6D04 )                LEA       EBP, [EBP+04]
( 004ABC5A    C3 )                    NEXT,
( 59 bytes, 23 instructions
)

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


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

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

Jelsay, обратите пожалуйста свое внимание на тот факт, что главное слово задачи предопределено.
Сделано это не просто так, а чтобы было во-первых понятнее, а во-вторых легче тестировать ваше решение.
Спасибо за участие!)

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


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

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

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


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

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

А сколько было до повышения быстродействия? Не могли бы вы использовать для сравнения свой первый вариант?


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

Зарегистрирован: Сб янв 26, 2008 18:23
Сообщения: 71
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Цитата:
Программа JELSAY некорректно работает с граничными значениями(не учтено, что входное число беззнаковое

прошу прощения - в качестве оправдания прошу учесть что я написал и отладил её менее чем за минуту совершенно не думая об оптимизациях :)


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

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


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

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


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

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


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

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