Воробьёвы

(-:

№29.6. Экстрим программированние для дZенствующих. Результаты COMPO

############################################

C()MP()#01

###################################################

Результаты

# В п()исках степени 01b

Кто знает, рок судьбы или нет, но только видимо Edmond, выбирая название COMPO, зло подшутил над самим собой. Сперва очень просто обнаружилась ошибка знакового переполнения, принадлежащая С-программе. А методом последовательного приближения (в народе: «тыка») было, установлено исходное число. Все праздновали победу, когда вдруг, «неожиданно» оказалось, что хитрый алгоритм не хочет уложиться в пределы 32-х бит. Таким образом, степень 01b, оказалась по-серьёзному затерянной в неизвестности высших разрядов. Её долго искали при помощи фонариков и других инструментов подобного характера. Причём искали все, как авторы COMPO, так и участники.

В конце концов, авторы, скрипя сердцем, и хлопая дверью, договорились считать предположение об отсутствии переполнения. Но даже, несмотря на все «блины» вышедшие комом, COMPO состоялось, И теперь мы станем свидетелями Великой победы человека над глупостью машины, и даже над Глупостью человека, например, такого как Edmond ? :)).

#П()БЕДИТЕЛИ

По главному критерию COMPO – перед нами один абсолютный победитель, ему удалось обогнать соперников не на один байт, или даже десяток. Это рыцарь Дзена – xBlackCat, который смог отрубить голову дракону, укоротив его до 109 байт.
  • xBlackCat - 109 bytes

Второе почётное место досталось почтенному Shur, заметим, который замахнулся, мечём на 145 байт. (Что лучше тестового примера Edmondа, не удержавшегося вспомнить чёрный экран DOS, пусть и под заклятиями NTVDM).

  • Shur - 123 bytes

WASM.RU поёт отважным песню славы, и приглашает всех желающих испить чашу вина, и насладится кодом победителей.

#C()DE LISTING

Исходник Shur ( с его комментариями)

;       by Shur


; 123 bytes
; корректно работает для n из диапазона 0 < n < 159'487

  .model tiny
     .code
.386 org 100h start:
call _read_number ;Читаем первое число. mov edi,ecx ;его в edi, т.к. в ecx будем читать второе call _read_number ;Читаем второе число. ;---------------------------------------------------------------- ;в edi - нижняя граница, в ecx - верхняя граница ;начнем с верхней ;в ax будет текущий максимум итераций ;он в ax, потому что его потом придется выводить, сконвертировав в ;десятичнаю форму, а делить можно только ax ;посему, чтобы потом его не перемещать, сразу поместим его в ax xor ax,ax _go: mov edx,ecx ;Берем очередное число. ;прямо с ecx работать нельзя, надо запомнить, ;какое последнее число обрабатывали xor si,si ;это счетчик итераций ;--------------------------------------------------------------- ;в случае четного n => n=n/2; it++; ( то бишь n=n>>1 ) ;в случае нечетного => n=(3*n+1)/2; n+=2; ( то бишь n=(n>>1)+n+1 ) ;--------------------------------------------------------------- _inc: inc si ;it++ в любом случае mov ebx,edx ;сохраняем n на случай нечетного shr edx,1 ;тут одной командой происходит как тестирование ;n на 1, так и на четность !!! ;правда, я не сам до этого додумался, а подсмотрел в TESTASM.EXE :))) ;Edmond: ;Ну вот, прокололся ещё раз :))) ;Хотя а что ж это за асмовец, который не подсмотрит код в exe. ;Мы так не любим смотреть исходники друг друга, зато обожаем копатся в битах. jz short _end ;это если edx был 1 jnc _inc ;это случай четного n ;а это в случае нечетного. здесь CF=1, ebx=n, edx=n>>1 adc edx,ebx inc si jmp _inc ;достигли n=1, si содержит количество итераций. _end: cmp si,ax ;обновляем текущий максимум jb short _no_new_maximum xchg ax,si ;реально нужен mov, но xchg короче _no_new_maximum: dec ecx ;готовимся обработать следующее число cmp ecx,edi jnb _go ;------------------------------------------------------------ ;теперь в ax - максимум итераций для текущего диапазона ;конвертируем в десятичный вид и выводим. ;в ecx - количество циферок. xor cx,cx mov bl,0ah ;перед делением проверки нет, т.к. ax гарантировано отлично от 0 ;т.е. хоть одна цифра обязательно будет выведена. ;вообще это тоже не моё - это из статьм Serrgio - Программирование под ДОС ;но ничего короче я не придумал - только заменил команды на более короткие ;Edmond: ;Человек не придумывает новое, он просто открывает существующее. ; (с)... _nz: inc cx cwd div bx push dx test ax,ax jnz _nz _out_cipher: pop dx add dl,30h call _out_byte loop _out_cipher ;а это вывод 0ah mov dl,0ah call _out_byte jmp start ;ну и все - пара обработана ;----------------------------------------------------------------- ;Процедура чтения числа из входного потока ;1.Пытается прочитать число ;2.Сразу выводит его ;3.Выводит после него пробел ;4.Завершает программу, когда при чтении первого числа достигнут конец потока. _read_number: ;число будем собирать в ecx xor ecx,ecx _read_digit: ;читаем следующий символ ;я пользовался функцией 06h, просто потому, что ей можно как ввести байт, ;так и вывести. ;а может просто, потому что она первой на глаза попалась. mov dl,0ffh call _in_byte ;переход выполняется 2 раза. Первый раз на второй вызов _read_number, когда ;в ecx назодится второе число последней строки. ;но программу пока завершить нельзя, т.к. эта пара значений еще не обработана ;второй раз уже после обработки последней пары jz short _put_space ;0ah мы просто игнорируем, а по пробелу или 0dh - заканчиваем ввод cmp al,0ah jz _read_digit ;здесь в al либо цифра, либо пробел, либо 0dh ;цифра - это 0011xxxxb, ;пробел - 00100000b, ; 0dh - 00001101b, ;10h - 00010000b. ;этот test позволяет отделить цифру от остальных случаев одним сравнением test al,10h ;Если не цифра - то на выход, печатать пробел ;В ecx в этом случае точно не ноль ;правда, ничего страшного не будет, если написать jz short _put_space jz short _put_space_1 ;Прочитали цифру. сразу её выводим. mov dl,al int 21h ;теперь добавляем её к читаемому числу movzx eax,dl sub al,30h imul ecx,0ah add ecx,eax ;-------------------------------------------------------------------------- ;P.S. - тут я несколько стормозил. на кой было гнать цифру в eax, ;когда значитеьно проще и короче на 2 байта: ; and edx,0fh ; imul ecx,0ah ; add ecx,edx ;Вообще-тот до вызова int 21h в al тот-же символ, что и в dl, ;но после почему-то уже нет. ;-------------------------------------------------------------------------- ;И идем читать следующий символ jmp _read_digit _put_space: ;Входной поток кончился. Возможно, придется выйти. mov ah,4ch ;Если в ecx ноль - тогда остается только выйти. ;т.е. либо входной файл совсем пустой, либо последнее число уже было считано ;предыдущим вызовом jecxz _int_21h ;вот чтобы воспользоваться jecxz, я и собирал число именно в ecx ;если-бы последняя строка тоже заканчивалась 0dh,0ah - тогда по отсутствию ;символа во входном потоке можно было-бы сразу закончить программу. _put_space_1: ;Если-же в ecx не ноль, то значит мы прочитали число, и уже вывели его. ;Теперь выводим за ним пробел. mov dl,20h _in_byte: _out_byte: ;Конец процедуры будет использован как самостоятельная процедура. ;Для ввода символа, и для вывода mov ah,06h _int_21h: int 21h ret end start ;-------------------------------------------------------------------------- ;Ну и еще одно - 0ah после максимума можно было вывести проще - затолкнув ;его в стек перед преобразованием, а затем выведя вместе с цифрами одним циклом. ;Сэкономили бы еще 2 байта: ; ; push 0ah-30h ;потом 30h прибавится ; mov cx,1 ;а это вместо xor cx,cx ; mov bl,0ah ; ... далее преобразование и вывод ; ;В-общем, можно было уложиться в 119 байт. как меньше - я пока не знаю ;-------------------------------------------------------------------------- ;кстати, версия, корректно работающая с n из 0 < n < 1'000'000, ;у меня "уложилась" в 129 байт ;--------------------------------------------------------------------------
Исходник победителя XBlackCat

   ;By xBlackCat

  p386
ideal
model tiny
CODESEG
        org     100h
Start:
        mov     bl,10
StartCikl:
        xor     edi,edi
        mov     ah,06h
CiklRN:
        mov     dx,0FFh
        int     21h
        mov     dl,al
        test    al,10h
        jz      short ExitRN

        imul    edi,edi,5
        lea     edi,[edx+2*edi-30h]
        int     21h

        jmp     CiklRN

ExitRN:
        cmp     al,20h
        jne     short NumbersReaded

        int     21h
        mov     esi,edi
        jmp     StartCikl

NumbersReaded:
        xor     bp,bp

CiklMain:
        xor     ax,ax
        mov     ecx,esi
        inc     esi

CiklFunc:
        inc     ax
        shr     ecx,1
        jnc     CiklFunc
        jz      short EndCiklFunc

        inc     ax
        lea     ecx,[ecx+2*ecx+2]
        jmp     CiklFunc

EndCiklFunc:
        cmp     bp,ax
        jae     short NextStepCiklFunc

        xchg    ax,bp

NextStepCiklFunc:
        cmp     edi,esi
        ja      CiklMain

        xchg    ax,bp

        mov     cl,3
        db      6Ah     ; push 0FFh
        db      0FFh    ; -=\*/=-
        push    bx

Cikl:
        inc     cx
        cwd
        div     bx
        add     dl,30h
        push    dx
        or      ax,ax
        jnz     Cikl

        push    20h
        mov     ah,06h
CiklOutNumber:
        pop     dx
        int     21h
        loop    CiklOutNumber
        jnz     StartCikl

        ret
        END     Start

#Ан()нс

В преддверии нового года WASM.RU желает приятно встретить новый, и проводить старый год. И повторить процедуру минимум два раза для закрепления эффекта.

Пусть в новый год войдут ваши лучшие идеи, оставляя позади (но, не забывая) ошибки прежнего года.

Мне хочется верить, что там, за границей двенадцати ударов часов и двенадцати ударов хрустальных фужеров кроется несколько приятных сюрпризов, новых ошибок (ибо они - путь к совершенству), и новых творений, что украсят сказочную жизнь представителя низкоуровневого мира asm.

Как всегда мы ждём предложения и необычные идеи COMPO сюда: compo@wasm.ru

###################################################

© Edmond :: HI-TECH group

© wasm.ru 2002

###########################################################