Из журнала Deja Vu #05, Кемерово, 01.07.98



(C) Card!nal/PGC/BD
__________________________________________

   Привет,дорогие читатели нашего журнала!
Даниил  тут попросил  меня написать статью
по coding'у, и я вот сижу за текстовым ре-
дактором. Эта статья не имеет определенной
цели, просто я расскажу об оптимизации  и,
вообще, что у меня  накопилось  с  выпуска
четвертого номера Deja Vu.

...

   Далее поговорим об алгоритме умножения.
Простейшая  процедура  умножения на SPECCY
выглядит так: HL = A*E

        LD H,A
        LD L,0
        LD D,L
        LD B,8
LOOP    ADD HL,HL
        JR NC,$+4
        ADD HL,DE
        DJNZ LOOP
        RET

   Не трудно подсчитать количество тактов:
минимум  310, максимум 358 без  учета RET.
Конечно, если развернуть  цикл, мы получим
минимум 206, а максимум 254 такта. А можно
ли  побыстрее? Yes, of cozzz! Но для этого
нужно  вспомнить начальную алгебру. А точ-
нее  формулы сокращенного умножения:

    Квадрат суммы: (a+b)^2=a^2+2ab+b^2
    Квадрат разности: (a-b)^2=a^2-2ab+b^2

   Возьмем  эти формулы на вооружение. Для
того, чтобы  написать процедуру умножения,
нужно  сформировать табличку квадратов чи-
сел  от  0  до  255  включительно. Таблица
квадратов будет основной частью программы.
Адрес таблицы должен быть кратным 256, т.е
младший  байт  = 0. Это  делает  следующая
программка.

SET_TBL LD DE,TABL
        LD H,E
        LD L,E
        LD B,E
        LD C,E
SET_T1  LD A,L
        LD (DE),A
        INC D
        LD A,H
        LD (DE),A
        DEC D
        ADD HL,BC
        INC C
        ADD HL,BC
        INC E
        JR NZ,SET_T1
        RET
TABL    DEFS 512

   А вот и сама процедура умножения. Числа
от  0  до  255 задаются в регистрах L и E.
Ответ в HL.

MULS    LD H,'TABL
        LD C,(HL)
        INC H
        LD B,(HL)
        LD A,L
        ADD A,E
        JP NC,MUL4
        JP M,MUL1
        SUB E
        SUB E
        JP NC,MUL2
        LD A,E
        SUB L
MUL2    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        LD A,L
        CPL
        LD L,A
        LD A,H
        CPL
        LD H,A
        INC HL
        SRL H
        RR L
        RET
MUL4    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        SRL H
        RR L
        RET
MUL1    LD A,L
        SUB E
        JP NC,MUL3
        LD A,E
        SUB L
MUL3    LD L,E
        LD D,(HL)
        DEC H
        LD E,(HL)
        LD L,A
        LD A,(HL)
        INC H
        LD H,(HL)
        LD L,A
        SBC HL,BC
        OR A
        SBC HL,DE
        SRL H
        RR L
        LD A,L
        CPL
        LD L,A
        LD A,H
        CPL
        LD H,A
        INC HL
        RET

   В  итоге количество тактов минимум 141,
а максимум 207, что, согласитесь, немного.
Этот  алгоритм  был  позаимствован из игры
BATTLE  COMMAND 128. К тому же об этом пи-
салось в электронном журнале "Спектрум Эк-
сперт 1". Однако, там приводилась несколь-
ко иная программа, которая учитывала знаки
при умножении, и было ограничение чисел от
-128 до +127, что не всегда удобно.
   Теперь  давайте  поговорим о вычислении
квадратного корня. В ZX FORMATE 7 была ка-
кая-то  программка  вычисления корня, но я
прямо  скажу, что  не очень. А  все дело в
скорости. Я попробывал вычислить с помощью
той программки корень из 1024. Потрассиро-
вал  STS'ом  и  оказалось, что программа 5
(пять)  раз делает деление, а при вычисле-
нии корня из 65535 делает 10 (десять!) де-
лений. Причем процедура деления выполняет-
ся около 1000 тактов,а то и больше. Я тог-
да немного подумал и написал свою. Ее лис-
тинг  дан  ниже. Моя  программа  выполняет
всего  одно деление, если число попадает в
интервал  от 2 до 16383, и выполняется два
деления, если  число  в  интервале 16384 -
-65535. При числах 0 и 1 деления не выпол-
няются. Программа работает по  модифициро-
ванному мною алгоритму Ньютона. Попробуйте
сами  разобраться, как  все  работает. Дам
подсказку: в таблице находятся так называ-
емые  средние  корни чисел от 2^1 до 2^15.
Вычисляются по формуле:

(sqr(2^n)+sqr(2^(n+1)))/2

SQRT    LD A,H   ;HL = SQR (HL)
        OR L
        RET Z
        LD D,H
        LD E,L
        LD B,15
        ADD HL,HL
        JR C,SQRT2
        DEC B
        ADD HL,HL
        JR C,SQRT2
        DEC B
SQRTL   ADD HL,HL
        JR C,SQRT1
        DJNZ SQRTL
        LD HL,1
        RET
SQRT1   LD HL,TABL
        LD C,B
        LD B,0
        ADD HL,BC
        LD C,(HL)
SQRT_   PUSH BC
        CALL DIV
        POP BC
        ADD HL,BC
        SRL H
        RR L
        RET
SQRT2   PUSH DE
        CALL SQRT1
        POP DE
        LD B,H
        LD C,L
        JR SQRT_

DIV     PUSH BC  ;HL = DE/BC с округлением
        LD A,B   ;ответа
        CPL
        LD B,A
        LD A,C
        CPL
        LD C,A
        INC BC
        LD HL,0
        LD A,E
        ADD A,A
        RL D
DUP 16
        ADC HL,HL
        ADD HL,BC
        JR C,$+4
        SBC HL,BC
        RLA
        RL D
EDUP
        LD E,A
        POP BC
        SRL B
        RR C
        OR A
        SBC HL,BC
        EX DE,HL
        RET C
        INC HL
        RET
TABL    DEFB 1,2,2,3,5,7,10,14,19,27
        DEFB 39,55,77,109,155,219

   Время  выполнения  я  не считал, но оно
составляет, примерно, 1500  - 2500 тактов.
Программу  можно  ускорить, если использо-
вать  более  быструю процедуру деления. Но
можно  вообще  обойтись  без делений, если
использовать  другой алгоритм. У меня есть
на  примете  такой, но пока нет достаточно
свободного времени в нем хорошенько разоб-
раться и написать программу :-(