Bugs #01 30 сентября 1999

Ассемблер     Программирование

Small Coding - Процедуры возведение в квадрат и квадратный корень.

(C) The Devils Corporation 1999.
  
  
                     ВОЗВЕДЕНИЕ В КВАДРАТ.
 
    Как вы догадались из названия статьи, речь здесь пойдет как
раз о возведении в квадрат. Эта функция одна из наиболее простых
в реализации на компьютере. Я предлагаю два варианта получения 
квадрата числа.
  
1. 8-БИТОВЫЙ ВАРИАНТ. 
  
HL = A ^ 2
  
        LD H,128        ; 7  : 2
        LD L,A          ; 4  : 1
        LD A,(HL)       ; 7  : 1
        INC H           ; 4  : 1
        LD H,(HL)       ; 7  : 1
        LD L,A          ; 4  : 1
        RET             ; 10 : 1
        ------------------------
                         8 байт.
  
Время = 43 такта.
 
    Видно, что используется таблица на 512 байт, в которую зара-
нее помещены квадраты всех 256 чисел. Так сказать - ничего умнее
я не придумал и не собираюсь. Опять таки напоминаю, что подпрог-
рамму можно с-оптимизировать, если :
 
а) Получать ответ не в HL.
б) Число, которое возводится в квадрат - присылать в L.
в) Избавиться от RET, внедрив подпрограмму в тело основной.
г) Хранить число 128 еще где-нибудь.
  
Пример для BC = L^2 :
 
        LD H,D          ; 4 : 1  D = 128
        LD C,(HL)       ; 7 : 1
        INC H           ; 4 : 1
        LD B,(HL)       ; 7 : 1
        -----------------------
                       4 байта.
Время = 22 такта.
 
Да, чуть не забыл, для полноты картины привести процедуру созда-
ния таблицы квадратов 8-битовых чисел.
 
       LD HL,32768        ; адрес начала таблицы
       LD D,L
       LD E,D
       LD B,D
       LD C,1
   M1: LD (HL),E
       INC H
       LD (HL),D
       DEC H
       EX DE,HL
       ADD HL,BC
       EX DE,HL
       INC BC
       INC BC
       INC L
       JR NZ,M1
       RET
------------------
       21 байт.
 
Ну что, круто ?  Как нет ?!?
 
Ладно, а так :
 
       LD HL,32768   ; адрес начала таблицы
       LD D,L
       LD E,D
       LD B,D
       LD C,D
   M1: LD (HL),E
       INC H
       LD (HL),D
       DEC H
       INC BC
       EX DE,HL
       ADD HL,BC
       EX DE,HL
       INC BC
       INC L
       JR NZ,M1
       RET
------------------
       20 байт.
 
Что - опять лажа ?
Согласен, можно короче - мой предел был 18 байт.
 
 
2. 16-БИТОВЫЙ ВАРИАНТ.
 
    Надо возвести в квадрат BC. Еще со школы всем нам (может и
не всем) хорошо известно, что:
  
         ( A + B ) ^ 2 = A ^ 2 + 2 * A * B + B ^ 2
 
Так вот, если взять регистровую пару BC и разложить ее на 'A'
и 'B' , то мы получим следующее :  ( B*256 + L )^2.
На этом и основано возведение в квадрат в моем варианте:
 
A) Для начала создадим таблицу квадратов 8-БИТОВЫХ ЧИСЕЛ.(выше)
Б) А теперь сама процедура:
 
   Принцип такой: DE:HL = BC ^ 2
 
        LD H,128
        LD L,C
        LD E,L
        LD A,(HL)
        LD (M1+1),A
        INC H
        LD C,(HL)
        LD L,B
        LD A,(HL)
        DEC H
        LD B,(HL)
        LD HX,A
        LD H,L
        LD D,0
        LD L,D
; Теперь 8 раз следующие три строки - это умножение !
        ADD HL,HL
        JR NC,$+3
        ADD HL,DE
; ----------------------------------
        LD D,HX
        ADD HL,HL
        JR NC,$+3
        INC D
        ADD HL,BC
        LD E,H
        LD H,L
M1:     LD L,0
        RET NC
        INC D
        RET
-------------------
        66 байт.
 
Время = примерно 400 тактов.
 
Написано сходу и не оптимизировано. Так что дерзайте !!!
А для начала попробуйте понять - что собственно произошло ?
 
 
 
 
                                    Тут, чисто тут, чисто тут,
                                    Ты поймешь, что ТЫ НЕ КРУТ !
   
                         КВАДPАТHЫЙ КОPЕHЬ.

   В этой статье я pасскажу вам о том, как гpамотные паpни вычи-
сляют квадpатный коpень. Сpазу хочу пояснить, что коpень я вычи-
сляю без дpобной части и ответ получается окpугленным до ближай-
шего меньшего целого. Hу, так уж повелось у меня, т.е.:
 SQR (16384) = 128, а не 127 или 129.
 SQR (17000) = 130, а не 129 и конечно не 130.3840484619141.
Hадо заметить, что меня устpаивает такое окpугление до некотоpой
степени только из-за скоpости вычисления.
 
Все пpоцедуpы pаботают по пpинципу A = SQR (HL)
 
 
1. Тоpмоз которого никто не видел !
 
      LD DE,1      ; 10   : 3 
      XOR A        ; 4    : 1 
  M1: SBC HL,DE    ; 15   : 2
      RET C        ; 11/5 : 1 
      INC DE       ; 6    : 1 
      INC DE       ; 6    : 1
      INC A        ; 4    : 1
      JR M1        ; 12   : 2
      ---------------------
                     12 байт.
 
Мин. вpемя = 14 + 26 = 40 тактов  
Макс.вpемя = 14 + 255 * 48 = 12254 такта.
 
Hу, скажем так, - это pаботает основываясь на том, что количес-
тво ответов с каждым следующим целым ответом возpастает на 2.
Hаписана мною впеpвые была в 1994 году.
 
 
2. Убыстpение тоpмоза...
 
      LD DE,65535  ; 10   : 3
      XOR A        ; 4    : 1
  M1: ADD HL,DE    ; 11   : 1
      RET NC       ; 11/5 : 1
      DEC DE       ; 6    : 1
      DEC DE       ; 6    : 1
      INC A        ; 4    : 1
      JP M1        ; 10   : 3   Поставьте JR - будет короче !
    ---------------------
                     12 байт.
 
Мин. вpемя = 14 + 22 = 36 тактов
Макс.вpемя = 14 + 255 * 42 = 10724 такта.
 
Из убыстpения становится видно только одно , тоpмоз - он и убы-
стpенный все pавно остается тоpмозом.
Единственный плюс этих пpоцедуp - они весьма коpотки.
 
3. Наиболее подходящий по размеру и скорости.
 
      LD DE,64  ; 10   : 3
      LD A,L    ; 4    : 1
      LD L,H    ; 4    : 1
      LD H,D    ; 4    : 1
      LD B,8    ; 7    : 2
  M1: SBC HL,DE ; 15   : 2
      JP NC,M2  ; 10   : 3 ( ИЛИ JR NC,M2 )
      ADD HL,DE ; 11   : 1
  M2: CCF       ; 4    : 1
      RL D      ; 8    : 2
      RLCA      ; 4    : 1
      ADC HL,HL ; 15   : 2
      RLCA      ; 4    : 1
      ADC HL,HL ; 15   : 2
      DJNZ M1   ; 13/8 : 2
      LD A,D    ; 4    : 1
      RET       ; 10   : 1
    -----------------------
                  27 байт.
 
Время выполнения = 838 тактов.
 
Сразу скажу - JR или JP значения не имеет.
Сам метод вычисления был взят, как мне помнится, из ПЗУ 48.
 
4. Неявное табличное вычисление. ( Осторожно - взрыв мозгов ! )
 
      LD A,H    ; 4   : 1
      CP 16     ; 7   : 2
      JR NC,M1  ; 12/7: 2
      OR 128    ; 7   : 2
      LD H,A    ; 4   : 1
      LD A,(HL) ; 7   : 1 
      RET       ; 10  : 1
  M1: LD L,H    ; 4   : 1
      LD H,127  ; 7   : 2
      LD H,(HL) ; 7   : 1
      LD L,A    ; 4   : 1
      ADD A,(HL); 7   : 1
      RET       ; 10  : 1
    ----------------------
                   17 байт.
 
Пpи HL = от    0 до 4095,  Вpемя = 46 тактов.
Пpи HL = от 4096 до 65535, Вpемя = 62 такта.
 
Pазмеp таблицы 5120 . ( адрес в памяти 32768 )
Таблица состоит:
0000-4095 - ответы для HL           от     0-4095
4096-4351 - интерполирование диапазона  4096-19199
4352-4607 - интерполирование диапазона 19200-33791
4608-4863 - интерполирование диапазона 33792-34815
4864-5119 - интерполирование диапазона 34816-65535
 
Почему именно так - можете и не спрашивать.
Дополнительная 256-байтная таблица с адреса 32512.
Состав:
        DS 75 ,144
        DS 57 ,145
        DS 4  ,146
        DS 120,147
 
 ===== НУ, ЧТО - БАШНЮ ОТОРВАЛО ??? =====
 
Сейчас отпустит, когда расскажу о точности вычисления:
 
Абсолютно точно = 50046 чисел.  77%
Ошибка на -1    = 10321 число.  15%
Ошибка на +1    = 5199  чисел.  8%
 
Ну, что сказать в свое оправдание - надо лучше интерполировать !
( Но так впадлу ... да и времени нет совсем ... )
 
Дальше, в принципе, можно не читать ничего до пункта 5. !!!!!!!
---------------------------------------------------------------
Можно избавиться от 4096 байт таблицы если изменить программу.
 
       LD A,H      ; 4    : 1
       CP 16       ; 7    : 2
       JR NC,M1    ; 12/7 : 2
 
       LD DE,65535 ; 10   : 3 
       XOR A       ; 4    : 1 
   M2: ADD HL,DE   ; 11   : 1
       RET NC      ; 11/5 : 1 
       DEC DE      ; 6    : 1
       DEC DE      ; 6    : 1
       INC A       ; 4    : 1
       JP M2       ; 10   : 3
 
   M1: LD L,H      ; 4    : 1
       LD H,127    ; 7    : 2
       LD H,(HL)   ; 7    : 1
       LD L,A      ; 4    : 1
       ADD A,(HL)  ; 7    : 1
       RET         ; 10   : 1
       ----------------------
                    24 байта.
 
Вы, конечно, догадались, что я поместил способ 2 во внутрь.
Таблица стала всего 1024 байта.
Все HL , которые больше 4096 считаются по таблице, а вот
остальные за :
Мин.время  = 32 + 22 = 54 такта.
Макс.время = 32 + 42 * 63 = 2678 тактов.
 
Ну, пожалуй стоит добавить для особо умных - считающих себя
крутыми оптимизаторами. Только дурак не увидит, что здесь можно
развернуть цикл, избавиться от двух DEC DE и одного JP и полу-
чить нечто такое:
 
; Первые три строки процедуры смотрите выше
 
       LD DE,65535   ; 10   : 1
       XOR A         ; 4    : 1
       ADD HL,DE     ; 11   : 1
       RET NC        ; 11/5 : 1
  
       DUP 63
       LD DE,65533   ; Короче,  DE = предыдущее DE - 2
       INC A
       ADD HL,DE
       RET NC
       EDUP
  
; Последние 6 строк смотри выше
 
DUP 63 - Означает повторить 63 раза блок кода.
Теперь о времени:
Мин. время = 18 ( начальная CP-шка ) + 36 = 54 такта.
Макс.время = 18 ( ------ // ------ ) + 30 * 64 = 1938 тактов.
 
Кое-как 740 тактов урвали у самого большого ответа.
Развернутый цикл занимает: 6 * 64 = 384 байта.
 
При таких делах мне бы хотелось напомнить о процедуре 3, кото-
рая считала любой корень за 838 тактов. Таким образом, если
ее использовать для нахождения этих несчастных 4096 корней
можно выиграть по времени следующим образом:
1. (838-18) / 30 = 27. ...
2. 28 ^ 2 = 784
 
То есть,на промежутке от 0 до 784 процедура 2 "делает" процедуру
3, а вот дальше ... облом .
---------------------------------------------------------------
 
5. Явное табличное вычисление.
 
Заранее создается таблица ответов на SQR(HL), а затем можно
использовать что-то вроде этого.
Пример для корней от 0 до 16383 ( таблица на 1 сегмент.)
 
        LD A,H     ; 4  : 1
        OR 192     ; 7  : 2
        LD H,A     ; 4  : 1
        LD A,(HL)  ; 7  : 1
        RET        ; 10 : 1
        -------------------
                    6 байт.
Время = 32 такта.
 
или
        ADD HL,BC  ;BC = 49152
        LD A,(HL)
        RET
        -----------------
        3 байта, 28 тактов.
 
    В принципе, такой способ нельзя использовать в таком виде.
Число 192 надо хранить в каком-нибудь регистре (Например в С)
а про RET надо вообще забыть, так как делать CALL на 6 байт это
полный маразм. Для тех кто не понял - подпрограмму надо встро-
ить в тело основной программы ! Вот тогда-то мы и получим почти
полную скорость - 19 тактов.
    И это еще не предел. Так как если таблицу немного приподнять
байтов так на 16384, то подпрограмма может стать такой:
 
        SET 7,H   ; 8  : 2
        LD A,(HL) ; 7  : 1
        RET       ; 10 : 1
        ------------------
                  4 байта.
 
Время = 25 тактов.  ( без RET  - 15 тактов.)
 
    Но и это еще не предел. Так как на многих компьютерах есть
возможность подключать вместо ПЗУ свою страницу,то если Вы смо-
жете отдать под эту таблицу этот участок памяти то вычисление
квадратного корня займет всего 7 тактов ( LD A,(HL) ).
С математической точки зрения это полная лажа. Зато это слишком
быстро работает. 
  
Ладно - пока хватит заниматься ерундой. На самом деле, способ 3,
в принципе может устроить злостных нелюбителей таблиц ( я что-то
не понял - неужели до сих пор есть такие ДАУНЫ и ОТМОРОЗКИ).
Или что - таблица на 512 байт или на 16384 - это - все - хана ?
Ребята, я понимаю, что все вы, как-будто бы программисты, типа -
хакеры , и все такое, но, опуститесь на ЗЕМЛЮ, ведь скорость
ZX SPECTRUMa не велика, и тратить время на пересчет какой-нибудь
формулы - это непозволительная роскошь.
   Не помню где, была приведена процедура извлечения квадратного
корня из HL. Там применялось умножение. Я не понимаю - что там
потребовалось умножать и зачем ?  При всем при том, что процеДУ-
РА умножения была не фонтан. Что за бредня ?  Вам, что жалко 
опубликовывать нормальные (я не говорю сверхклассные) алгоритмы?
Или ума хватает только на то,чтобы написать тормозные процеДУРЫ?
Пацаны, пора уже кончать использовать старые формулы - ПИФАГОРА,
ГЕРОНА, НЬЮТОНА-ЛЕЙБНИЦА (квадратный корень) и прочих стариков.
Сейчас уже почти 2000 год. Придумайте что-нибудь свое !!!
 
PS: Надеюсь, что вы люди умные и на критику не обижаетесь, а 
    принимаете к сведению. Обидеть никого не хотел и не пытался.
    Вы правы только в том, что как бы не были плохи ваши алго-
    ритмы - они все-таки работают в реальных программах - и это
    пожалуй единственный их плюс.
 
    Если кто-то хочет высказать свое мнение по поводу и без...
    Принимаю вызов от кого угодно в плане написания самой корот-
    кой процедуры или программы на ваш выбор (обломаю почти каж-
    дого !!! )
 
    Мой E-Mail: devils@ellink.ru  
 
  
PPS:  Предлагаю написать более короткую процедуру вычисления
      кубического корня из HL в целых числах.
      A = HL ^ (1/3)
 
Вот мой вариант:
 
        LD DE,65535
        LD BC,0
M1:     ADD HL,DE
        RET NC
        INC A
        EX DE,HL
        DEC BC
        DEC BC
        DEC BC
        DEC BC
        DEC BC
        DEC BC
        ADD HL,BC
        EX DE,HL
        JR M1
        ----------
        20 байт.
  
________________________________(C) The Devils Corporation 1999.