ZX Pilot #34 20 июля 1999

Программирование

Coding - Super-puper-быстрый алгоритм построения окружностей и кругов; быстрое деление 16/16; извлечение квадратного корня из регистровой пары; извлечение квадратного корня из трехбайтового числа; процедурка рассчета адреса в аттрибутах по координатам в знакоместах.

                C O D I N G

──────────────────────────────────────────

(C) VIRTUAL


   Super-puper-быстрый алгоритм построения
окружностей и кругов  by Virtual/BrainWave
of X-Project Association.
   Окружности  можно строить с использова-
нием синусов. Однако, придется либо созда-
вать  огромные  таблицы  синусов различных
амплитуд, либо наслаждаться  сильными тор-
мозами, умножая  на каждом шагу построения
значение  синуса  на радиус окружности. Но
самое противное в том, что неизбежно будут
появляться промежутки между  точками. Осо-
бенно  это  будет заметно  у окружностей с
большими  радиусами. При построении же ма-
леньких окружностей, некоторые точки будут
выводиться по нескольку раз в одно и то же
место, что не очень  удобно при построении
окружностей по xor.
   Другой способ - использование уравнения
окружности x^2+y^2=r^2. Однако, вычисление
на каждом шагу  квадратов и корней - дово-
льно неблагодарное занятие.
   Теперь  настало  время для моего супер-
пупер  метода. Пришло  время  обнародовать
этот алгоритм, который я столько вынашивал
Придумал  я его  в 11-ом  классе (сейчас я
закончил 1 курс). Основан он также на ура-
внении окружности, но в нем необходимо на-
личие 3d-акселератора Blizzard на Power PC
(шутка). В моем  методе не используются ни
дробные числа, ни возведения в квадрат, ни
извлечения квадратных корней.
   Итак, начнем:
   Окружность как бы разбивается на 8 сек-
торов  по 45 градусов, т.е. за каждый про-
ход  ставится на экран по 8 точек. Вот сам
алгоритм рассчета:

    1. Ставим  4 точки - нижнюю,  верхнюю,
левую  и  правую  на  расстоянии radius от
центра.
    2. y=radius
    3. x=1
    4. counter=radius-1. Я в качестве cou-
nter использовал hl.
    5. subber=1. Я использовал  в качестве
subber регистровую пару de.
    6. adder=radius*2. В качестве  adder я
юзал bc.
    7. loop:
    8. subber=subber-2
    9. counter=counter+subber
   10. if carry then goto 14
       else
       {
   11. adder=adder-2
   12. counter=counter+adder
   13. y=y-1
       }
   14. Печатаем 8 точек с координатами от-
носительно центра окружности:
       (+x,+y)
       (+x,-y)
       (-x,+y)
       (-x,-y)
       (+y,+x)
       (+y,-x)
       (-y,+x)
       (-y,-x)
   15. x=x+1
   16. if x+1<y then goto loop
   17. if x=y then exit
   18. Печатаем 4 диагональные точки отно-
сительно центра окружности:
       (+x,+x)
       (-x,+x)
       (+x,-x)
       (-x,-x)
   19. Конец.

   Поясню на примере строки 8-13:

       ...
    8. dec e
       dec de
    9. add hl,de
   10. jr c,l1
   11. dec bc
       dec c
   12. add hl,bc
       exx
   13. dec l    ;l' в роли y
       exx
l1     exx
       ...

   tmin=36 тактов на рассчет координат.
   tmax=55 тактов на рассчет координат.

   При желании можно сделать чуть быстрее,
если  юзать  однобайтовые  регистры вместо
регистровых пар, но тогда максимальный ра-
диус окружности будет равен 127 :-(
   Скорость  работы данного метода впечат-
ляет: ЗАКРАШЕННЫЕ  КРУГИ радиусами до 77 с
наложением по  or  строятся быстрее 1 инта
даже на моем wait'овом Scorpion'e с длиной
инта 69886 тактов m/ ;-)
   Такая  процедура  кругов используется в
нашей игре The Scorched Earth (наш вариант
игры Tank Wars). До  выхода  полной версии
The Scorched Earth  осталось  совсем  мало
времени.
   На данный момент это самый быстрый спо-
соб бестабличного  построения окружностей,
т.к. проще 1-2 целочисленных сложений быть
уже ничего не может.
   Будет  большой  облом, если  то, что  я
здесь набредил, окажется давным-давно изо-
бретенным :-(
   Далее  несколько  моих   математических
процедур:

------------------------------------------

   Итак, процедура  номер 1: быстрое деле-
ние 16/16. Тому, кто  сможет  ее ускорить,
можно будет  памятник  при жизни поставить
(за его счет). Ускорение путем  замены  jr
на  jp  не  рассматривается, т.к. выигрыш/
проигрыш  в скорости  зависит  от величины
аргументов.

На входе:
   de-делимое
   bc-делитель
На выходе:
   de-частное
   hl-остаток

divide ld a,b    ;меняем
       cpl       ;
       ld b,a    ;знак
       ld a,c    ;
       cpl       ;у
       ld c,a    ;
       inc bc    ;делителя   t=30

       ld hl,0   ;обнулили новое делимое
       ld a,d    ;сначала двигаем
       rla       ;старший байт делимого
                 ;t=18
       rl l      ;┐
       add hl,bc ;│
       jr c,$+4  ;│8 раз
       sbc hl,bc ;│
       rla       ;┘ t=8*45=360

       ld d,a    ;ст. байт результата
       ld a,e    ;теперь двигаем
       rla       ;младший байт  t=12

       adc hl,hl ;┐
       add hl,bc ;│
       jr c,$+4  ;│8 раз
       sbc hl,bc ;│
       rla       ;┘ t=8*52=416

       ld e,a    ;мл. байт результата
                 ;hl-остаток от деления
                 ;t=4

Итого:
30+18+360+12+416+4=840 тактов.

   Если  остаток не нужен, то конец проце-
дуры должен выглядеть так:

       adc hl,hl ;┐
       add hl,bc ;│
       jr c,$+4  ;│7 раз
       sbc hl,bc ;│
       rla       ;┘ t=7*52=364

       adc hl,hl ;
       add hl,bc ;
       rla       ;
       ld e,a    ;  t=34

Итого:
30+18+360+12+364+34=818 тактов.

   P.S. Если  будете  делить  на ноль, то,
как и следовало ожидать, частное будет ра-
вно  нулю, а  остаток - делимому,  т.е.  в
этом плане у процедуры глюков нет.

------------------------------------------

   Процедура номер 2: извлечение  квадрат-
ного корня из регистровой пары. Вот тут уж
действительно  надо памятник поставить то-
му, кто  ускорит  процедуру  хотя  бы на 1
такт. Ускорение  путм  замены  jr на jp не
рассматривается,  т.к.  выигрыш/проигрыш в
скорости зависит от величины аргумента.

На входе:
   hl-число из которого необходимо извлечь
   квадратный корень
на выходе:
   a-квадратный корень из hl

sqrhl  xor a     ;обнулили a ;-)
       ld de,64  ;этого требует алгоритм
                 ;  t=14

       sla h     ;берем два самых левых
       adc a,a   ;бита аргумента
       sla h     ;
       adc a,a   ;
       jr z,$+4  ;если они не равны
       dec a     ;нулю, то увеличиваем
       inc d     ;результат
                 ;   t=39

       sla h     ;┐далее следуем
       adc a,a   ;│алгоритму извлечения
       sla h     ;│квадратного корня
       adc a,a   ;│"столбиком", только
       sla d     ;│
       ld c,d    ;│3 раза
       sli c     ;│
       cp c      ;│
       jr c,$+4  ;│
       sub c     ;│
       inc d     ;┘  t=63*3=189

       sla l     ;┐проделываем похожую
       adc a,a   ;│операцию с
       sla l     ;│младшим байтом
       adc a,a   ;│аргумента
       sla d     ;│
       ld c,d    ;│2 раза
       sli c     ;│
       cp c      ;│
       jr c,$+4  ;│
       sub c     ;│
       inc d     ;┘  t=63*2=126

       ld h,a    ;
       or a      ;обнулили флаг переноса
                 ;  t=8

       sbc hl,de ;теперь нам не хватает
       jr nc,$+3 ;одного регистра d для
       add hl,de ;выполнения последних
       ccf       ;двух циклов, придется
       rl d      ;использовать более
       add hl,hl ;медленные операции
       add hl,hl ;с регистровыми парами
                 ;  t=67

       sbc hl,de ;и последний раз
       ccf       ;выполняем расчеты, не
       ld a,d    ;восстанавливая hl
       adc a,a   ;в a-результат
                 ;  t=27

Итого:
14+39+189+126+8+67+27=470 тактов.

------------------------------------------

   Процедура номер 3: извлечение  квадрат-
ного корня из трехбайтового числа. Ускоре-
ние путм замены jr на jp не рассматривает-
ся, т.к. выигрыш/проигрыш в скорости зави-
сит от величины аргумента.

На входе:
   dhl=d*65536+hl - само число
На выходе:
   hl - тот самый квадратный корень

sqrdhl  xor a    ;начало процедуры
        ld bc,64 ;практически аналогично
                 ;предыдущей
                 ;  t=14

        sla d    ;
        adc a,a  ;
        sla d    ;
        adc a,a  ;  t=39
        jr z,$+4 ;
        dec a    ;
        inc b    ;

        sla d    ;┐
        adc a,a  ;│
        sla d    ;│
        adc a,a  ;│
        sla b    ;│
        ld e,b   ;│3 раза
        sli e    ;│
        cp e     ;│
        jr c,$+4 ;│
        sub e    ;│
        inc b    ;┘ t=3*63=189

        sla h    ;┐
        adc a,a  ;│
        sla h    ;│
        adc a,a  ;│
        sla b    ;│
        ld e,b   ;│2 раза
        sli e    ;│
        cp e     ;│
        jr c,$+4 ;│
        sub e    ;│
        inc b    ;┘ t=63*2=126

        ld d,l   ;
        ld l,h   ;
        ld h,a   ;меняем регистры
        or a     ;  t=16

        sbc hl,bc;┐
        jr nc,$+3;│
        add hl,bc;│
        ccf      ;│2 раза
        rl b     ;│
        add hl,hl;│
        add hl,hl;┘ t=67*2=134

        ld l,h   ;есть подозрение, что
        ld h,0   ;этот блок и предыдущий
        ld c,b   ;можно немного ускорить
        ld b,h   ;
        rl h     ;
        ld a,d   ;  t=31

        rla      ;┐да и этот блок мне
        adc hl,hl;│не нравится.
        rla      ;│очень вероятно, что
        adc hl,hl;│его можно неплохо
        sla c    ;│ускорить. Но как?
        rl b     ;│
        ld d,b   ;│
        ld e c   ;│3 раза
        sli e    ;│
        rl d     ;│
        sbc hl,de;│
        jr nc,$+4;│
        add hl,de;│
        dec c    ;│
        inc c    ;┘ t=3*119=357 (!)
                 ;ужас! Думайте, как
                 ;ускорить!

        rla      ;этот блок аналогичен
        adc hl,hl;предыдущему с
        rla      ;небольшой разницей
        adc hl,hl;в конце. Это сделано
        ld d,b   ;ради повышения
        ld e,c   ;скорости вычислений
        sla e    ;
        rl d     ;
        sli e    ;
        rl d     ;
        sbc hl,de;
        ccf      ;  t=97

        ld h,b   ;
        ld l,c   ;
        adc hl,hl;в hl - результат
                 ;  t=23

Итого:
14+39+189+126+16+134+31+357+97+23=1026.

------------------------------------------

   Напоследок, моя процедурка рассчета ад-
реса  в аттрибутах по координатам в знако-
местах. Быстрее  без использования  таблиц
не бывает.

На входе:
   d-y
   e-x
На выходе:
   hl-адрес в аттрибутах

        ld a,d
        rrca
        rrca
        rrca
        ld h,a
        and #e0
        or e
        ld l,a
        xor e
        xor h
        or #58
        ld h,a

t=54 такта.

------------------------------------------

Ну, если что, то пишите:

  Post: 424004 р. Марий-Эл, г. Йошкар-Ола,
        ул.  Советская, д.91, кв.1, Малову
        Алексею.
 ZXNet: 500:8362/1.3
E-mail: intel_outside@mail.ru
        virtual_bw@mail.ru

Либо звоните (если знаете, как  халявно по
межгороду звонить):

  Tel.: (8362) 11-59-61 (20:00-23:00 Msk.)

   По E-mail летом  лучше  не связываться,
т.к. я имею к нему доступ только  в ВУЗ'е,
а летом он закрыт на каникулы.


            Virtual/Brainwave of X-Project
                      06.07.99/20:20 (Msk)