Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
вопрос писал(а): Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах
не верно, так как обычно к более простым решениям.
А более простые решения, как раз чаще алгоритмические.
А вообще форт не гнушается ни одним из подходов
[quote="вопрос"]Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах[/quote]
не верно, так как обычно к более простым решениям.
А более простые решения, как раз чаще алгоритмические.
А вообще форт не гнушается ни одним из подходов
|
|
|
|
Добавлено: Ср апр 23, 2008 13:39 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
кто склоняется, а кто нет. если памяти мало особо не посклоняешься
кто склоняется, а кто нет. если памяти мало особо не посклоняешься
|
|
|
|
Добавлено: Вт апр 22, 2008 20:34 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
вопрос - Цитата: Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах
просто Форт - это эффективность - основанная на понимании задачи и анализе её решений.. не более..
[b]вопрос[/b] - [quote]Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах[/quote]
просто Форт - это эффективность - основанная на понимании задачи и анализе её решений.. не более..
|
|
|
|
Добавлено: Вт апр 22, 2008 16:13 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
вопрос писал(а): Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах
С этим вообще говоря не согласен. Лучший вариант выбирается взависимости от ситуации.
[quote="вопрос"]Форт- сообщество постоянно склоняется к табличным решениям почти во всех задачах[/quote]
С этим вообще говоря не согласен. Лучший вариант выбирается взависимости от ситуации.
|
|
|
|
Добавлено: Вт апр 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
Все-таки чуть быстрее нетабличных вариантов и по объему кода меньше,
а память для таблицы можно взять из хипа-там ее много.
Для коллекции еще асмовский вариант табличного решения
[code]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] лог [code]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[/code]
Все-таки чуть быстрее нетабличных вариантов и по объему кода меньше,
а память для таблицы можно взять из хипа-там ее много.
|
|
|
|
Добавлено: Вт апр 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 )
Еще один быстрый нетабличный вариант на ассме
(примерно одинаковый по быстродействию с табличным - при таблице в 64кбайт)
[code]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]лог [code]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 )[/code]
|
|
|
|
Добавлено: Пн апр 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 )
Реализовано на Форте, если сделать на ассме, будет еще быстрее. Само собой нет зависимости
от количества единичных бит в числе.
[quote="forther"]Идея не в том, чтоб развернуть цикл, а в том, чтоб использовать LUT. Что, всегда больше и быстрее, чем итеративные методы. Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет. [/quote]
Вот подтверждение этому:
[code]: 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[/code]
лог [code]495 155 181 181 181 77 77 77 77 77
Ok ( [10].. 65535 65535 65535 65535 65535 )[/code]
Реализовано на Форте, если сделать на ассме, будет еще быстрее. Само собой нет зависимости
от количества единичных бит в числе.
|
|
|
|
Добавлено: Пн апр 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-м месте - мне это больше нравится.
[quote="forther"]А сколько было до повышения быстродействия? Не могли бы вы использовать для сравнения свой первый вариант?[/quote]
Легко посмотреть, старый же код моего первого решения я не убирал:
[code]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[/code] лог [code]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[/code]
При малом количестве единиц в исходном числе этот вариант самый быстрый при увеличении
числа единиц до 16 по быстродействию переходит на 2-е место при максимальном количестве единиц переходит на 3 место. Вообщем быстродействие сильно зависит от количества единиц в исходном числе. Во втором моем варианте такой сильной зависимости нет и второй вариант стабильно на 1-м месте - мне это больше нравится.
|
|
|
|
Добавлено: Пн апр 21, 2008 07:32 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
mOleg - Цитата: идея понятна, но реализация медленная однозначно Цитата: вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!! - прошу прощения. forther - Цитата: Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет. A 4 гигасловная таблица вообще за одну индексацию все решит
угу - у меня и на 256 сердце кровью то обливалось, а уж за 65К я бы себя задушил
[b]mOleg[/b] - [quote]идея понятна, но реализация медленная однозначно[/quote] :) [quote]вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!![/quote] - прошу прощения.
[b]forther[/b] - [quote]Если вместо 256 байтной таблицы использовать 64К словную, то еще быстрее будет. A 4 гигасловная таблица вообще за одну индексацию все решит[/quote]
угу - у меня и на 256 сердце кровью то обливалось, а уж за 65К я бы себя задушил :)
|
|
|
|
Добавлено: Пн апр 21, 2008 07:29 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
forther писал(а): Если места хватит big-table разместить ...
а если учесть, что уже на носу CELL=64 бита
все правильно сказано, но я говорил о реализации.
и быстрее оно не всегда, хотя всегда больше.
с другой стороны, время выполнения таких алгоритмов фиксированное, в отличие от циклических, количество циклов в которых равно количеству бит для данного случая
вобщем мерять надо!
[quote="forther"]Если места хватит big-table разместить ...[/quote]
а если учесть, что уже на носу 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 разместить ...
[quote="mOleg"][quote="Jelsay"]тут имеется ввиду что именно в run-time нет циклов и ветвлений - что касается compile- time то, в принципе, таблицы можно прошить и в ручную[/quote] идея понятна, но реализация медленная однозначно. Во-первых, команды /MOD скушают весь выигрыш от разворачивания цикла. Во-вторых, у вас очень много получается обращений к памяти, к тому же невыравненных, да и общее количество команд в цикле будет меньше, чем у вас 8( хотя идея развернуть цикл хороша.
Теперь замечание: вы опять не обратили внимания, что имя конечного слова, а так же стековая картинка заданы в ТЗ!! пожалуйста будте чуточку внимательнее. P.S. Спасибо за участие[/quote]
Идея не в том, чтоб развернуть цикл, а в том, чтоб использовать 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. Спасибо за участие
[quote="Jelsay"]тут имеется ввиду что именно в run-time нет циклов и ветвлений - что касается compile- time то, в принципе, таблицы можно прошить и в ручную[/quote]
идея понятна, но реализация медленная однозначно.
Во-первых, команды /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 то, в принципе, таблицы можно прошить и в ручную
[code]\ создаём таблицу количества единиц в байте (компайле тайм) : (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 [/code]
тут имеется ввиду что именно в 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 - \ \ \ прошу обратить внимание что в алгоритме нет ни одного цикла и\или ветвления
[code]\ некий набросок оптимизации по быстродействию \ сейчас уже поздно писать - глаза слипаются - поэтому проверю идею завтра :) \ \ создаём таблицу количества единиц в байте - таблица займёт 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 - \ \ \ прошу обратить внимание что в алгоритме нет ни одного цикла и\или ветвления [/code]
|
|
|
|
Добавлено: Вс апр 20, 2008 01:14 |
|
|
|
|