Суботняя головоломка от Розыча

← →
Rouse_ © (2015-08-22 12:24) [0]

Кстати вот вам еще одна задачка, автор не я:

"Для первого класса церковно-приходской школы.
Написать алгоритм, сравнивающий строку из двух символов на равенство "MZ" или "ZM", используя не более одного if (т.е. else if использовать нельзя)."

К примеру, перефразируя, пусть это будет функция в которую передается 2 симфола, которая должна вернуть True в случае если один из символов равен "M" а второй "Z" (порядок не важен).

function Check_IsMZorZM(A, B: AnsiChar): Boolean; begin //код писать здесь... end;

Мой вариант решения был в 9 строчек ASM кода, впрочем не обязательно писать на ассемблере :)

ЗЫ: поясню, вот написать нельзя:

function Check_IsMZorZM2(A, B: AnsiChar): Boolean; begin Result := ((A = "M") and (B = "Z") ) or ((A = "Z") and (B = "M")); end;

ибо тут будет 4 сравнения:

cmp al, $4D jnz 5 cmp dl, $5A Jz $C cmp al, $5A jnz 5 cmp dl, $4D jz 3 xor eax, eax ret mov al, 1 ret

← →
palva © (2015-08-22 13:56) [1]

{$APPTYPE CONSOLE} function Check_IsMZorZM(A, B: AnsiChar): Boolean; var x,y,t: Integer; begin //код писать здесь... x := ord(A); y := ord(B); t := (x+y)*256 + abs(x-y); Result := t = 42765; end; begin WriteLn(Check_IsMZorZM("M","Z")); WriteLn(Check_IsMZorZM("Z","M")); WriteLn(Check_IsMZorZM("N","Y")); end.

← →
Rouse_ © (2015-08-22 14:02) [2]

> palva © (22.08.15 13:56) [1]

Правильно, можно немного подоптимизировать, но правильно.

← →
DayGaykin © (2015-08-22 15:42) [3]

Не интересно. Давай-те вообще без сравнений!

← →
Sha © (2015-08-22 15:43) [4]

> Rouse_ © (22.08.15 12:24)

Их море, не считая банальной a*a+b*b.
Например, среди таких (a op1 c) op2 (b op1 c),
где c - константа, а (op1, op2) = (*, xor), (*, or), (+, *), (xor, *).

← →
Rouse_ © (2015-08-22 15:57) [5]

> DayGaykin © (22.08.15 15:42) [3]
> Не интересно. Давай-те вообще без сравнений!

Напиши

← →
Rouse_ © (2015-08-22 16:00) [6]

> Sha © (22.08.15 15:43) [4]

IMUl + SUB - будут коллизии

← →
Rouse_ © (2015-08-22 16:01) [7]

ЗЫ: хоть решение уже и показано - но оно не самое эффективное.
Можно проще.

← →
DayGaykin © (2015-08-22 16:01) [8]

Я ASM не знаю. Дай мне немного времени.

← →
Sha © (2015-08-22 16:02) [9]

Вот это мне нравится

(4*a+b+115) or (4*b+a+115)=553

← →
Sha © (2015-08-22 16:04) [10]

> Rouse_ © (22.08.15 16:00) [6]
> IMUl + SUB - будут коллизии

Не всегда.
Если сюда писать начну все те, что без коллизий, места не хватит )

← →
DayGaykin © (2015-08-22 16:10) [11]

> Sha © (22.08.15 16:02) [9]

Я короче нашел. (X+101) * (Y+101) = 33998

← →
Sha © (2015-08-22 16:15) [12]

> DayGaykin © (22.08.15 16:10) [11]

В [4] еще куча таких коротких. Но и там, и у тебя есть умножение.
А в [9] умножения нет )

← →
DayGaykin © (2015-08-22 16:20) [13]

function Check_IsMZorZM2(A, B: Byte): Boolean; asm add al, $65 add dl, $65 mul dl xor ax, $84CE jz @x mov ax, 1 @x: not ax and eax, 1 end;

> Sha © (22.08.15 16:15) [12]

Умножение так страшно?

← →
Sha © (2015-08-22 16:21) [14]

> DayGaykin © (22.08.15 16:10) [11]

Кстати, там есть константы и поменьше, например (X+77) * (Y+77) = 25718

← →
Sha © (2015-08-22 16:24) [15]

> DayGaykin © (22.08.15 16:20) [13]
> Умножение так страшно?

Нет, сейчас не страшно уже. Это раньше было.

← →
DayGaykin © (2015-08-22 16:29) [16]

> Кстати, там есть константы и поменьше, например (X+77) *
> (Y+77) = 25718

Я подобрал методом "тыка". Мне сразу повезло со 101 :)

Как в EAX положить значение флагового регистра?

← →
Sha © (2015-08-22 16:36) [17]

Result:=((X+101) * (Y+101) = 33998)

← →
Rouse_ © (2015-08-22 16:40) [18]

> DayGaykin © (22.08.15 16:20) [13]

Вах, даже красивее чем у меня :)
Правда чутка помедленней (разучились процессоры эффективно с 8-битными L/H работать, просадочка будет небольшая, но красивее)

Вот мой вариант:

> function Check_IsMZorZM(A, B: AnsiChar): Boolean;
> asm
> and eax, $FF
> and edx, $FF
> mov ecx, eax
> xor ecx, edx
> sub ecx, $17
> imul edx
> lea ecx, [eax + ecx - $1B12]
> cmp ecx, 0
> setz al
> end;

зы:

> Как в EAX положить значение флагового регистра?

Через setz после компарации.

← →
DayGaykin © (2015-08-22 16:42) [19]

Про SETZ не нашел. Нашел LAHF. Получилось вот так:

function Check_IsMZorZM2(A, B: Byte): Boolean;
asm
add al, $65
add dl, $65
mul dl
xor ax, $84CE
lahf
and eax, $4000 // ZF
shr eax, 14
end;

Сравнение, конечно, все-равно осталось.

← →
Rouse_ © (2015-08-22 16:43) [20]

> Sha © (22.08.15 16:02) [9]
> Вот это мне нравится
>
> (4*a+b+115) or (4*b+a+115)=553

Да, естественно это тоже верно (кто бы сомневался :)

← →
DayGaykin © (2015-08-22 16:44) [21]

С твоими задачами я скоро ASM начну понимать :)

← →
Rouse_ © (2015-08-22 16:44) [22]

> DayGaykin © (22.08.15 16:42) [19]

Мдя, пошел пить коньяк и посыпать голову пеплом - молоток :)

← →
Rouse_ © (2015-08-22 16:50) [23]

> DayGaykin © (22.08.15 16:44) [21]

Блин, этож Дима :))
Я то думаю кто это такой хитрый на форуме появился :)))

← →
DayGaykin © (2015-08-22 17:06) [24]

С SETZ интереснее, да:
function Check_IsMZorZM2(A, B: AnsiChar): boolean; asm add al, $65 add dl, $65 mul dl xor ax, $84CE setz al end;

> Блин, этож Дима :))
> Я то думаю кто это такой хитрый на форуме появился :)))

С тем ником, видимо, покончено :)

← →
Rouse_ © (2015-08-22 17:14) [25]

> DayGaykin © (22.08.15 17:06) [24]

Ты победил :))

← →
Sha © (2015-08-22 17:17) [26]

> Rouse_ © (22.08.15 17:14) [25]

и не он один, см. [4] )

← →
Rouse_ © (2015-08-22 17:35) [27]

Саш, ну я тебя никогда не считал - бо с твоей квалификацией... :)

← →
SergP © (2015-08-24 19:06) [28]

Попробовал обойтись без умножения... Правда кол-во инструкций на 1 больше чем [24]

function Check_IsMZorZM_SergP(A, B: AnsiChar): boolean; asm mov ah,dl sub ax,$53d4 sbb dx,dx xor ax,dx cmp ax,$679 setz al end;

← →
Rouse_ © (2015-08-24 19:29) [29]

> SergP © (24.08.15 19:06) [28]

Угу, оно

← →
Sha © (2015-08-24 19:46) [30]

не совсем "угу"

← →
SergP © (2015-08-24 19:51) [31]

> DayGaykin © (22.08.15 16:29) [16]
>
>
> > Кстати, там есть константы и поменьше, например (X+77)
> *
> > (Y+77) = 25718
>
> Я подобрал методом "тыка". Мне сразу повезло со 101 :)

для подбора константы ИМХО чисто теоретически достаточно чтобы t+$4d или t+$5a было простым числом, большим чем 128
ближайшее к 128 и большее него простое число 131, так что похоже что минимальная константа будет 131-$5a=41

← →
Rouse_ © (2015-08-24 19:51) [32]

> Sha © (24.08.15 19:46) [30]
> не совсем "угу"

На моих тестах от нуля до 255 прошла по обоим чарам, что я упустил?

← →
SergP © (2015-08-24 19:52) [33]

> Sha © (24.08.15 19:46) [30]
>
> не совсем "угу"

что там не то?

← →
Sha © (2015-08-24 19:54) [34]

хотя нет, наверно, "угу", надо проверить...

← →
SergP © (2015-08-24 20:00) [35]

Я проверял:

procedure TForm1.Button1Click(Sender: TObject); var x,y:byte; begin for x:=0 to 255 do for y:=0 to 255 do if Check_IsMZorZM_Sergp(ansichar(x),ansichar(y)) then Memo1. Lines.Add(IntToHex(y*256+x,4)); end;

ИМХО единственное " не совсем" может заключатся в том что результат
setz al
возможно не совсем соответствует boolean

← →
Rouse_ © (2015-08-24 20:03) [36]

> возможно не совсем соответствует boolean

Соответствует.

← →
SergP © (2015-08-24 20:11) [37]

> Rouse_ © (24.08.15 20:03) [36]
>
>
> > возможно не совсем соответствует boolean
>
> Соответствует.

хз. я ассемблера не знаю. Просто в инете полазил и прочитал что setz al делает al=1 если установлен флаг нуля, но по идее для boolean оно должно быть не 1, а $FF , хотя мож я чего-то и забыл уже...

← →
Rouse_ © (2015-08-24 20:14) [38]

> SergP © (24.08.15 20:11) [37]

Три разных нотации BOOL, Boolean и первый бит.

← →
SergP © (2015-08-24 20:47) [39]

кстати, вопрос по ассемблеру:
можно ли использовать старшие слова регистров EAX, EBX, ECX, EDX в качестве операндов? если да, то как?

← →
Игорь Шевченко © (2015-08-24 21:08) [40]

> можно ли использовать старшие слова регистров EAX, EBX,
> ECX, EDX в качестве операндов?

нет

← →
Sha © (2015-08-24 22:48) [41]

> SergP © (24.08.15 19:06) [28]

Честно скажу, функция меня обескуражила, т.к. я в той области уже потоптался.
Проверил все еще раз, ошибок не нашел, зато нашел это:

function Check_IsMZorZM_Sha(A, B: AnsiChar): boolean; asm add al, 56 sbb dl, 0 and al, dl setz al end;

← →
Sha © (2015-08-24 22:54) [42]

> Sha © (24.08.15 22:48) [41]

Также годятся константы: 88, 183, 185, 215, 217.

← →
Sha © (2015-08-24 22:58) [43]

> Sha © (24.08.15 22:48) [41]

Сорри sbb там не нужно, хоть и не мешает:

function Check_IsMZorZM_Sha(A, B: AnsiChar): boolean;
asm
add al, 56
and al, dl
setz al
end;

← →
Sha © (2015-08-24 23:15) [44]

Еще раз сорри.
Оказалось, что не то тестировал.
Просьба [41, 42, 43] считать бредом.

← →
Sha © (2015-08-24 23:50) [45]

> SergP © (24.08.15 19:06) [28]
> Правда кол-во инструкций на 1 больше чем [24]

На самом деле меньше, если учитывать передачу параметров.
В exe-файле эти символы стоят рядом.
И вызывать удобнее и быстрее такую функцию:

function Check_IsMZorZM_SergP2(MZ: word): boolean;
asm
sub ax,$53d4
sbb dx,dx
xor ax,dx
cmp ax,$679
setz al
end;

← →
SergP © (2015-08-25 00:16) [46]

> На самом деле меньше, если учитывать передачу параметров.
>
> В exe-файле эти символы стоят рядом.
> И вызывать удобнее и быстрее такую функцию:

да, это я видел, но просто следовал условию [0]:

> function Check_IsMZorZM(A, B: AnsiChar): Boolean;
> begin
> //код писать здесь...
> end;

ибо если менять описание функции, то тогда и в коде

> DayGaykin © (22.08.15 17:06) [24]
>
> function Check_IsMZorZM2(A, B: AnsiChar): boolean;
> asm
> add al, $65
> add dl, $65
> mul dl
> xor ax, $84CE
> setz al
> end;
>

тоже похоже что возможно первые 2 инструкции можно поменять на одну. (хотя не проверял, не скажется ли возможный перенос из младшего байта в случае с add ax, $6565)

← →
SergP © (2015-08-25 00:36) [47]

> тоже похоже что возможно первые 2 инструкции можно поменять
> на одну. (хотя не проверял, не скажется ли возможный перенос
> из младшего байта в случае с add ax, $6565)

в крайнем случае вместо этой инструкции можно поставить ror ax,1 (правда константа там другая будет $19ae) - то точно будет работать, проверял еще перед тем как пришла мысль варианта без умножения.

← →
Sha © (2015-08-25 00:37) [48]

> SergP © (25.08.15 00:16) [46]

Точно. Проверил, не скажется.

← →
Mystic © (2015-08-26 10:33) [49]

int magic[256]; void init() { magic["M"] = 2; magic["Z"] = 3; } int isMZ(int ch1, int ch2) { return !(magic[ch1] * magic[ch2] - 6); }

Вместо умножения можно использовать xor, наверное... Тогда magic["M"] = 1; magic["Z"] = 2; вычитать надо троечку.

Метод легко расширить на произвольное количество букв и повторений. Например, если надо детектить MMZ, MZM, ZMM, то получим

int isMZ(int ch1, int ch2, int ch3) { return !(magic[ch1] * magic[ch2] * magic[ch3] - 12); }

← →
manaka © (2015-08-26 14:35) [50]

Не знаю как написать точно, но идея такая:
можно составить переменную С=А+В, в результате должна вернуться "истина", если С="MZ" или С="ZM"
Result=(вхождение Z в С)*(вхождение M в C)
Если память не изменяет, то "истина" вернется только при умножении двух "истин"

← →
Masterucs © (2015-08-26 14:52) [51]

> можно составить переменную С=А+В

ты решила только заглавное сообщение прочитать? )

← →
SergP © (2015-08-26 22:03) [52]

> SergP © (24.08.15 19:06) [28]
>
> Попробовал обойтись без умножения... Правда кол-во инструкций
> на 1 больше чем [24]
>
> function Check_IsMZorZM_SergP(A, B: AnsiChar): boolean;
> asm
> mov ah,dl
> sub ax,$53d4
> sbb dx,dx
> xor ax,dx
> cmp ax,$679
> setz al
> end;

На одну инструкцию улучшил результат, теперь получилось сравняться по количеству инструкций с

> DayGaykin © (22.08.15 17:06) [24]

но по прежнему не используя умножение (mul, imul):

function Check_IsMZorZM_SergP(A, B: AnsiChar): boolean; asm mov ah,dl lea ecx,eax*8 ror ax,cl xor ax, $4d5a setz al end;

Чёт я забыл - в системе команд x86 нет обмена старшего и млажшего слов 16 бит в 32 бит регистрах? Если нет, значит не надо оно, с учётом того, что есть много всякой другой вспомогательной фигни.

> Чёт я забыл - в системе команд x86 нет обмена старшего и
> млажшего слов 16 бит в 32 бит регистрах?

Нормального обмена нет, но вроде как есть команда, которая меняет порядок байтов в 32 битном регистре на противоположный.
типа допустим было $01020304 , а стало $04030201

> зачем ещё что-то.

Чтобы быстро менять порядок байт little endian - big endian

> [59] Игорь Шевченко © (27.08.15 10:23)

Это ты имел ввиду из поста на один выше мной отцитированного?
> [55] SergP © (27.08.15 09:30)

> DayGaykin © (27.08.15 09:58) [58]
>
>
> > SergP © (26.08.15 22:03) [52]
>
> Очень клево!
> Спасибо, теперь я буду знать про инструкцию LEA)

Я сам про нее только вчера узнал )))

> SergP © (27.08.15 18:26) [61]
> Я сам про нее только вчера узнал )))

Самый эффективный однотактовый метод умножения:
на два: lea eax, [eax + eax]
на три: lea eax, [eax * 2 + eax]
на четыре: lea eax, [eax * 4]
на пять: lea eax, [eax * 4 + eax]
на восемь: lea eax, [eax * 8]
на девять: lea eax, [eax * 8 + eax]

хотя 2, 4 и 8 обычно заменяют на shl

> Самый эффективный однотактовый метод умножения:

угу. И причем ее достоинства на этом далеко не заканчиваются.

> SergP © (28.08.15 19:52) [63]
>
> > Самый эффективный однотактовый метод умножения:
>
>
> угу. И причем ее достоинства на этом далеко не заканчиваются.
>

Угу, работа с массивами - просто шикарна, к примеру :)

Для чего именно создавался множитель в этой инструкции?

> Sha © (28.08.15 20:29) [65]
> > Rouse_ © (28.08.15 19:13) [62]
>
> на 2 лучше все-таки add eax, eax

Не согласен и мы спорили :)
Все зависит от того какая инструкция пойдет дальше :)

> Sha © (28.08.15 20:50) [69]
> > Rouse_ © (28.08.15 20:36) [67]
>
> последнее время у меня такое ощущение, что уже не зависит
> )

Да я там сам умылся, ес чесно :)

> DayGaykin © (28.08.15 20:34) [66]
>
> Для чего именно создавался множитель в этой инструкции?

то не множитель, то сдвиг.

а для чего... наверное потому что эта команда называется "вычисление эффективного адреса" и для ее работы используется не АЛУ а блок адресации, и возможно поэтому ИМХО команда LEA реализовывает не новые возможности, а просто делает доступными программисту те возможности, которым уже и так обладает блок адресации. А урезать их смысла нет.

Кстати, почему нет новых задачек\головоломок ?

> SergP © (29.08.15 09:08) [73]
> Кстати, почему нет новых задачек\головоломок ?

Накинул следующую: http://delphimaster.net/view/15-1441385083/
Дам подсказку - учитывай ошибки округления в FPU

Суботняя головоломка от Розыча Найти похожие ветки