Страница Ивана Рощина > Статьи >

© Иван Рощин, Москва

ZXNet: 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW: http://www.ivr.da.ru

Ещё о программировании арифметических операций

Радиолюбитель. Ваш компьютер» 12/2000, 1—4/2001)
Исправленная и дополненная версия. Дата последнего редактирования: 5.02.2003.

Введение
Сложение и вычитание. Сравнения.
Умножение
Деление
Квадратные и другие корни. Возведение в любую степень.
Тригонометрия
Вычисления с плавающей точкой
Ввод-вывод чисел
Общие вопросы
Дополнительная информация

Введение

Прочитав статью [1], я решил продолжить на страницах журнала «Радиолюбитель. Ваш компьютер» рассказ о программировании арифметических операций на ассемблере. Так была написана эта статья, в которой рассмотрены некоторые, на мой взгляд, интересные алгоритмы и приёмы оптимизации. Статья адресована в первую очередь тем, кто пишет программы на ассемблере Z80, но описанные алгоритмы могут оказаться полезными независимо от используемой компьютерной платформы и языка программирования.

Итак, то, что получилось, — перед вами!

Сложение и вычитание. Сравнения.

Казалось бы, простейшие арифметические операции. Но и тут есть несколько интересных приёмов, позволяющих в ряде случаев оптимизировать программу.

Когда надо увеличить или уменьшить содержимое регистра, регистровой пары или ячейки памяти на небольшую величину, стоит посмотреть: а не окажется ли более выгодным использование для этого нескольких команд INC/DEC (увеличения/уменьшения на 1)? Пусть надо, скажем, увеличить значение HL на 3. Вариант с использованием команды ADD будет таким:

LD  DE,3  ;3 байта, 10 тактов
ADD HL,DE ;1 байт,  11 тактов
-----------------------------
Итого:     4 байта, 21 такт

В то же время три команды INC HL займут 3 байта/18 тактов, что и короче, и быстрее, да и не меняет содержимое DE.

Ещё несколько полезных приёмов (вместо HL может быть и другая регистровая пара):

HL:=HL+256 — INC H
HL:=HL–256 — DEC H
HL:=HL+255 — INC H: DEC HL
HL:=HL–255 — DEC H: INC HL

Реальный пример: в HL задана длина файла в байтах, в A надо получить его длину в секторах (1 сектор = 256 байтов):

INC H
DEC HL
LD  A,H

Преимущество команд INC/DEC ещё и в том, что их операнд может находиться в любом регистре, регистровой паре или в ячейке памяти, адресуемой (HL), (IX+s), (IY+s). При использовании же команд ADD/SUB один из операндов должен находиться в регистре A или в регистровой паре HL, IX, IY — а значит, могут потребоваться дополнительные команды, пересылающие его туда, а затем — пересылающие результат.

При использовании INC/DEC не забывайте, что они изменяют флаги не так, как ADD/SUB: INC/DEC 8-битного операнда не влияет на флаг CY, а INC/DEC 16-битного операнда вообще не влияет на флаги!

Теперь обратим внимание на то, что вычисления ведутся по модулю 256 для регистров и по модулю 65536 для регистровых пар. Это тоже можно использовать при оптимизации.

Бывает, что нужно прибавить или вычесть какое-то число, а оказывается, что в каком-то регистре уже есть его дополнение. Тогда можно заменить сложение на вычитание дополнительного числа и наоборот. Например, если надо прибавить к значению аккумулятора 4, а в регистре B находится 252 (т.е. 256–4), можно сэкономить 1 байт/3 такта, написав SUB B вместо ADD A,4. Только не забывайте, что такая замена влияет на значение флага CY после операции.

Вычитание 16-битной константы можно заменить на сложение с дополнением этой константы до 65536, выиграв при этом 2 байта/8 тактов:

 Было:  AND A         ;1 байт,    4 такта
        LD  DE,#7352  ;3 байта,  10 тактов
        SBC HL,DE     ;2 байта,  15 тактов
        ----------------------------------
        Итого:         6 байтов, 29 тактов

Стало:  LD  DE,-#7352 ;3 байта,  10 тактов
        ADD HL,DE     ;1 байт,   11 тактов
        ----------------------------------
        Итого:         4 байта,  21 такт

Увы, команда ADD HL,DE не действует на флаг Z, что может иметь в некоторых случаях (например, когда нужно проверить, равен ли результат нулю) решающее значение. Тогда приходится использовать «медленную» команду SBC. Замечу, что если точно известно значение флага CY перед вычитанием, команда AND A становится ненужной — достаточно лишь в случае CY=1 уменьшить вычитаемую константу на единицу.

При сложении или вычитании знаковых операндов, один из которых 16-битный, а другой 8-битный, требуется расширить 8-битный операнд до 16-битного. В процессоре Z80, к сожалению, нет специальной команды расширения знака (в отличие от, скажем, процессоров семейства 680X0), и приходится делать это с помощью нескольких команд. Вот наиболее быстрый способ (A — преобразуемое число, HL — результат):

    LD  L,A ;Младший байт будет таким же.
    ADD A,A ;Выдвинули бит знака во флаг CY.
    SBC A,A ;Если число отрицательное (бит знака=1), получим #FF,
            ;для положительного числа получим 0.
    LD  H,A ;Это и будет старшим байтом.

Теперь рассмотрим несколько известных (и не очень) приёмов, позволяющих оптимизировать различные виды сравнений.

Вместо команды CP 0 (2 байта/7 тактов) для сравнения знаковых или беззнаковых чисел с нулём выгоднее использовать одну из команд AND A или OR A (1 байт/4 такта), которые точно так же устанавливают флаги CY, Z и S. Вообще говоря, после арифметических и логических операций с аккумулятором в большинстве случаев (это зависит от конкретной операции) флаги устанавливаются в соответствии с его содержимым, так что специальная команда проверки на равенство нулю может оказаться ненужной.

Проверить, равно ли нулю содержимое одного из регистров B, C, D, E, H, L, удобно с помощью пары команд INC reg: DEC reg. Это эквивалентно командам LD A,reg: AND A, но не меняет значение аккумулятора.

Быстро проверить, равно ли содержимое одного из регистров A, B, C, D, E, H, L числу #FF или 1, можно с помощью, соответственно, команды INC reg или DEC reg. Аналогично выполняется и проверка на равенство B, C, D, E, H, L числу #FE или 2 — для этого потребуются две команды INC или DEC (для аккумулятора такой способ уже невыгоден: команда CP работает быстрее). Учтите, что содержимое проверяемого регистра при этом изменяется.

Вспомним, что в процессоре Z80 есть команда DJNZ — она уменьшает содержимое регистра B на единицу, и если в результате получился не ноль, осуществляет относительный переход по заданному адресу. Изначально эта команда предназначалась для организации циклов, но кто мешает нам использовать её для других целей? С её помощью можно, например, осуществлять быструю проверку регистра B на неравенство числам 1, 2 или 3:

    Переход в случае B<>1:  DJNZ LABEL
    Переход в случае B<>2:  DEC B: DJNZ LABEL
    Переход в случае B<>3:  DEC B: DEC B: DJNZ LABEL

Этот способ применим, правда, лишь когда расстояние от DJNZ до адреса перехода не превосходит 128 байтов. К тому же значение регистра B при подобном сравнении изменяется (впрочем, при сравнении B с единицей этот способ останется быстрее всех других даже и с учётом последующего восстановления значения B командой INC B).

Рассмотрим ещё такую задачу, довольно часто встречающуюся на практике: в аккумуляторе задано число от 1 до n (скажем, условный номер нажатой клавиши), и требуется в зависимости от этого числа выполнить те или иные действия. Вот простейший способ это сделать:

    CP   1
    JR   NZ,m1
    .......... ;действия при нажатии клавиши 1
    RET
м1  CP   2
    JR   NZ,m2
    .......... ;действия при нажатии клавиши 2
    RET
m2  CP   3
    JR   NZ,m3
    ..........

Немного подумав, можно найти лучший вариант:

    DEC  A
    JR   NZ,m1
    .......... ;действия при нажатии клавиши 1
    RET
м1  DEC  A
    JR   NZ,m2
    .......... ;действия при нажатии клавиши 2
    RET
m2  DEC  A
    JR   NZ,m3
    ..........

Но наиболее изящный способ — с использованием DJNZ!

    LD   B,A
    DJNZ m1
    .......... ;действия при нажатии клавиши 1
    RET
м1  DJNZ m2
    .......... ;действия при нажатии клавиши 2
    RET
m2  DJNZ m3
    ..........

Ну что ж, закончим с командой DJNZ и поговорим о другом. Если в аккумуляторе — число со знаком (–128..127), и нужно определить, отрицательное ли оно, то вместо такого:

    AND A
    JP  P,M1 ;Переход, если A<0.

часто лучше написать так:

    ADD A,A  ;Бит знака выдвигается во флаг CY.
    JR  C,M1

Чем это лучше? Во-первых, так на один байт короче: ведь мы заменили команду абсолютного перехода JP P (3 байта) на команду относительного перехода JR C (2 байта). Увы, в наборе команд Z80 нет команды JR P, поэтому и приходится прибегать к такой замене. Во-вторых, JP выполняется за 10 тактов, а JR — за 12 тактов при выполнении условия и за 7 — при невыполнении, и если условие будет чаще не выполняться, чем выполняться, то мы выиграем во времени выполнения программы (а если наоборот — проиграем).

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

Аналогичную замену можно производить и для условия A>=0. Для этого вместо такого фрагмента:

    AND A
    JP  M,M1 ;Переход, если A>=0.

напишите так:

    ADD A,A
    JR  NC,M1

Если нужно выполнить переход в зависимости от знака числа, находящегося в каком-либо другом регистре, удобно использовать команду BIT 7,reg (2 байта/8 тактов) — при этом флаг Z установится в зависимости от значения седьмого (знакового) бита регистра.

Для регистра H такую проверку можно сделать командой ADD HL,HL (1 байт/11 тактов), при этом 7-й бит H выдвинется во флаг CY. Это займёт больше времени, чем при использовании команды BIT 7,H, и к тому же изменит содержимое HL, но зато будет на байт короче.

В процессоре Z80 имеются лишь четыре возможности условной передачи управления после сравнения двух операндов — в зависимости от того, выполнилось ли одно из условий A=s, A<>s, A<s или A>=s. Этого не всегда хватает. Если нужно выполнить переход на метку М по условию A>s (для беззнаковых чисел), то вместо команд

    CP  s
    JR  Z,M1 ;Если A=s, то обходим следующую команду.
    JR  NC,M ;Переход, если A>=s, но случай A=s мы исключили.
М1  ...

в случае, когда сравнение происходит с константой, удобнее написать так:

    CP  s+1
    JR  NC,M ;Переход, если A>=s+1, т.е. если A>s.

а если сравнение происходит со значением регистра или ячейки памяти, то так:

    DEC A
    CP  s
    JR  NC,M ;Переход, если A–1>=s, т.е. если A>s.

Точно так же, если требуется выполнить переход по условию A<=s, то вместо такого:

    CP  s
    JR  Z,M  ;Переход, если A=s.
    JR  C,M  ;Переход, если A<s.

лучше использовать такой фрагмент (при сравнении с константой):

    CP  s+1
    JR  C,M  ;Переход, если A<s+1, т.е. если A<=s.

или такой (при сравнении со значением регистра или ячейки памяти):

    DEC A
    CP  s
    JR  C,M  ;Переход, если A–1<s, т.е. если A<=s.

Для сравнения регистровых пар, к сожалению, команда CP не приспособлена, и приходится либо использовать вычитание, либо (что часто бывает быстрее) работать с отдельными байтами. Рассмотрим для примера проверку содержимого двух регистровых пар (HL и DE) на неравенство. Вот способ с использованием вычитания:

    AND A
    SBC HL,DE
    JR  NZ,label

А вот — со сравнением отдельно младших и старших байтов:

    LD  A,H
    CP  D
    JR  NZ,label
    LD  A,L
    CP  E
    JR  NZ,label

Первый фрагмент занимает 5 байтов, второй — 8. Но первый фрагмент выполняется за 31 такт при выполнении условия и за 26 тактов при невыполнении, а второй — за 20 или 35 тактов при выполнении условия и за 30 тактов при невыполнении. Таким образом, если заранее известно, что условие чаще будет выполняться, чем не выполняться, то выгоднее использовать второй способ. При этом, если известно, что числа будут с большей вероятностью различаться в старших байтах, чем в младших, то и сравнение надо начинать со старших байтов, и наоборот.

Для сравнения с помощью команды SBC один из операндов должен находиться в HL, IX или IY, а другой — в BC или DE. Если это не так, то обычно выгоднее не тратить время на пересылку операндов, а использовать побайтное сравнение.

Посмотреть на практическое применение побайтного сравнения регистровых пар вы можете на примере процедуры извлечения корня (см. раздел «Квадратные и другие корни. Возведение в любую степень»).

Если же надо сравнить содержимое регистровой пары с нулём, то самый короткий и быстрый способ это сделать таков (на примере HL): LD A,H: OR L.

Кстати говоря, обычно команда перехода ставится сразу же после сравнения. Но между ними могут быть ещё команды, если они не влияют на значение используемого при переходе флага, — это позволяет иногда сократить программу. Вот конкретный пример — несколько последних команд из процедуры построения таблицы квадратов (см. раздел «Умножение»):

    INC E      ;Если получили E=0, флаг Z установится.
    ADD HL,DE  ;Эта команда не влияет на флаг Z.
    JR  NZ,M1  ;Переход в зависимости от значения флага Z.

Умножение

Рассмотрим сначала умножение аккумулятора на небольшую константу, когда результат операции умещается в том же аккумуляторе. Как отмечалось в [1], это удобно делать с помощью комбинации умножений на два и сложений. Я хочу обратить ваше внимание на то, что обычно это можно сделать несколькими способами. Пусть нам надо умножить аккумулятор, например, на шесть:

Первый способ: 6A=2(2A+A)

       LD  B,A
       ADD A,A
       ADD A,B
       ADD A,A

Второй способ: 6A=2A+4A

       ADD A,A
       LD  B,A
       ADD A,A
       ADD A,B

Казалось бы, оба варианта совершенно одинаковы как по количеству занимаемых байтов, так и по тактам. Сами по себе — да. Но представим такую ситуацию, когда множимое перед началом операции загружается в регистр A из какого-либо другого регистра (например, из регистра H). Тогда первый способ можно оптимизировать: ADD A,A: ADD A,H: ADD A,A — и мы выиграем 1 байт/4 такта, да к тому же не будем использовать регистр B.

Бывает, что константа, на которую требуется умножить значение аккумулятора, «неудобна» для применения описанного выше способа. Разумеется, всегда можно использовать универсальную подпрограмму умножения. Но есть более быстрые или короткие способы — о них я и расскажу.

Самый быстрый способ — с использованием таблицы, начинающейся с адреса, кратного 256. В этом случае умножение выполняется всего лишь за 18 тактов:

LD H,TABL/256
LD L,A
LD A,(HL)

Если нужно выполнить несколько умножений подряд, команда LD H,TABL/256 понадобится лишь перед первым умножением, а каждое последующее будет выполняться за 11 тактов.

Медленный, но занимающий мало места способ умножения — простое сложение в цикле:

    LD   B,A
    XOR  A
M1  ADD  A,константа
    DJNZ M1

Сразу же виден недостаток: если в аккумуляторе был ноль, то цикл выполнится 256 раз. Правильный результат мы всё же получим, но сколько времени будет при этом потеряно! Можно, конечно, ввести дополнительную проверку на ноль, но это увеличит длину программы.

А этот вариант, занимая те же шесть байтов, обеспечивает одинаковое время выполнения для любых значений A на входе:

    LD   C,A
    LD   B,константа–1
M1  ADD  A,C
    DJNZ M1

Правда, при этом используется дополнительный регистр.

Перейдём к умножению произвольных чисел. Как делать это быстро?

В [4] приводится процедура умножения двух 8-битных чисел «в столбик» — почти такая же, как описанная в [1], но все циклы в ней раскрыты. За счёт этого получается порядочный выигрыш в быстродействии: процедура выполняется за 218—275 тактов при длине 43 байта.

В [24] также приводятся процедуры умножения «в столбик» с раскрытыми циклами для операндов различной разрядности (8*8, 8*16).

А ещё быстрее? Первое, что приходит на ум, — использовать таблицу умножения. Правда, получается она что-то уж слишком большой: когда оба сомножителя 8-битные, в таблице должно быть 65536 двухбайтных произведений, а это 128 килобайтов!

А если уменьшить разрядность сомножителей? При их суммарной длине 14 битов размер таблицы сократится до 32 килобайтов. Ниже приведён пример выполнения умножения для случая, когда первый сомножитель 6-битный, второй — 8-битный, а таблица начинается с адреса #8000. Для достижения наивысшего быстродействия таблица устроена так, что по адресам #8000—#BFFF располагаются младшие байты произведений, а по адресам #C000—#FFFF — старшие байты.

Вход : H - первый сомножитель (0-63),
       L - второй сомножитель (0-255).
Выход: DE - произведение.
Длина: 6 байтов.
Время: 30 тактов.

           SET  7,H    ;HL := 10xxxxxx yyyyyyyy
           LD   E,(HL) ;Прочитали младший байт произведения.
           SET  6,H    ;HL := 11xxxxxx yyyyyyyy
           LD   D,(HL) ;Прочитали старший байт произведения.

Преимущество этого способа в том, что он самый быстрый (а если суммарная длина сомножителей не превосходит 8 битов, он может быть ещё быстрее за счёт того, что произведение будет умещаться в одном байте). Если суммарная длина сомножителей больше 14 битов, можно пожертвовать точностью ради быстроты, отбросив их младшие разряды.

Недостаток тоже очевиден — огромная таблица (впрочем, при уменьшении суммарной длины сомножителей она может быть гораздо меньшей). Но если не хватает памяти или если надо точно перемножать большие числа, этот способ не подойдёт.

Более экономным с точки зрения занимаемой памяти и почти таким же быстрым является логарифмический способ умножения, основанный на следующей формуле (x, y — сомножители, A — основание логарифмов):

xy = A(log x+log y).

Для перемножения 8-битных чисел потребуются две таблицы, расположенные в памяти друг за другом, начиная с кратного 256 адреса. Первая, длиной 256 байтов, содержит логарифмы чисел от 1 до 255, умноженные на некоторый коэффициент k (так, чтобы k*log 255 = 127, — это нужно, чтобы результат сложения уместился в байте). Вторая, длиной 512 байтов, содержит результаты возведения основания логарифмов A в степень от 0 до 254/k: в первой половине таблицы — младшие байты результатов, во второй — старшие. Основание логарифмов может быть любым, таблицы от этого не изменятся. Так, в приведённой ниже программе расчёта таблиц на Бейсике используются натуральные логарифмы.

    10 CLEAR 32767
    20 LET K=127/LN 255
    30 FOR I=1 TO 255
    40 POKE (32768+I),INT (.5+K*LN I)
    50 NEXT I
    60 FOR I=0 TO 254
    70 LET E=INT (.5+EXP(I/K))
    80 LET H=INT (E/256): LET L=E-H*256
    90 POKE (32768+256+I),L: POKE (32768+512+I),H
   100 NEXT I
   110 RANDOMIZE USR 15619: REM: SAVE "TABL_LOG" CODE
       32768,256+512

Пример выполнения умножения:

Вход : B - первый сомножитель, L - второй сомножитель.
Выход: DE - произведение.
Длина: 10 байтов.
Время: 51 такт.

           LD   H,TABL/256
           LD   A,(HL)
           LD   L,B
           ADD  A,(HL)
           INC  H
           LD   L,A
           LD   E,(HL)
           INC  H
           LD   D,(HL)

У этого способа свои недостатки: во-первых, он не годится для случая, когда один из сомножителей равен нулю, а во-вторых, он не является абсолютно точным (для приведённой выше процедуры максимальная относительная погрешность составляет 4,4%). Точность, впрочем, можно повысить, увеличив размеры таблиц.

В [20] вы сможете найти процедуры быстрого логарифмического умножения 8-битных операндов (как со знаком, так и беззнаковых), вычисляющие старший байт 16-битного произведения. Там же указан способ решения проблемы нулевого сомножителя, не требующий дополнительных проверок. Также там приведена процедура, быстро вычисляющая x sin y, — она может оказаться полезной, например, при работе с трёхмерной графикой.

Теперь рассмотрим способ точного и достаточно быстрого умножения с помощью таблицы квадратов по формулам, взятым из [2]:

xy =  1 ((x+y)2x2y2),

2
(1)
xy =  1 ((x+y)2–(xy)2).

4
(2)

Вычисление по первой формуле включает одно сложение, три обращения к таблице, два вычитания и один сдвиг вправо; по второй — сложение, два вычитания, два обращения к таблице и два сдвига вправо. Но при использовании второй формулы придётся либо вычислять модуль разности xy, либо хранить в таблице и квадраты отрицательных чисел, либо ограничиться случаями, когда заранее известно, что x>y (или x<y).

Ниже приведена процедура, использующая формулу (2) для умножения 8-битных чисел, сумма которых не превосходит 256. С адреса TABL_SQR, кратного 256, должна быть помещена таблица квадратов чисел от 0 до 255 (в первой половине таблицы — младшие байты квадратов, во второй половине — старшие).

Вход : D - первый сомножитель, E - второй сомножитель.
Выход: DE - произведение.
Длина: 28 байтов - сама процедура + 512 байтов - таблица
       квадратов.
Время: 125 или 128 тактов - в зависимости от того, первый
       сомножитель больше второго или наоборот (если заранее
       известно, что один всегда больше другого, процедуру можно
       упростить).

MUL        LD   H,TABL_SQR/256
           LD   B,H

           LD   A,D
           ADD  A,E
           LD   C,A    ;C=x+y

           LD   A,D
           SUB  E
           JR   NC,M1                         ;!
           NEG                                ;!
M1         LD   L,A    ;L=|x-y|

           LD   A,(BC)
           SUB  (HL)
           LD   E,A
           INC  H
           INC  B
           LD   A,(BC)
           SBC  A,(HL) ;CY сбрасывается.

           RRCA                               ;!!
           RR   E      ;В CY выдвинулся 0!    ;!!
           RRCA                               ;!!
           RR   E                             ;!!

           LD   D,A    ;DE=x*y
           RET

Если добавить дополнительное ограничение «сумма сомножителей не превосходит 127» (в этом случае и модуль их разности не будет превосходить 127) и хранить в первых 128 элементах таблицы квадраты чисел от 0 до 127, а в последних 127 элементах — квадраты чисел от –127 до –1, то из вышеприведённой процедуры можно исключить команды, помеченные «!». Это приведёт к сокращению длины процедуры на 4 байта и к уменьшению времени её работы на 12 (или 15) тактов, т.е. до 113 тактов.

Чтобы избавиться от деления на 2 в первой формуле и от деления на 4 во второй, достаточно хранить в таблице квадратов уже поделенные на 2 или на 4 значения (т.е. целые части этих значений):

xy ~= [ (x+y)2 ] – [ x2 ] – [ y2 ],



2 2 2
(3)
xy = [ (x+y)2 ] – [ (xy)2 ].


4 4
(4)

Умножение будет выполняться быстрее, но в случае использования формулы (3) станет неточным (можно доказать, что оно будет неточным, только если x и y нечётны; результат в этом случае будет на 1 больше истинного). Умножение по формуле (4), как отмечено в [23], является точным за счёт того, что дробные части (x+y)2/4 и (xy)2/4 равны (действительно, произведение целых чисел x и y — также целое число, а разность двух чисел (x+y)2/4 и (xy)2/4 может быть целой, только когда их дробные части равны).

Кстати, в [23] упоминается, что формула (4) вместе с таблицей значений функции [z2/4] при натуральных значениях z использовалась для облегчения умножения многозначных чисел ещё до изобретения таблиц логарифмов.

Чтобы перейти от использования формулы (2) к формуле (4), достаточно убрать из приведённой выше процедуры команды деления результата на 4 (они помечены комментарием «!!»). При этом длина процедуры сократится на 6 байтов, а время выполнения уменьшится на 24 такта (это около 20% по сравнению с исходным вариантом процедуры).

О других реализациях быстрого умножения с помощью таблицы квадратов.

В [3] приводится процедура умножения двух 8-битных чисел, свободная от ограничения «сумма сомножителей меньше 256», но она гораздо длиннее, да и выполняется медленнее: за 141—207 тактов.

Что касается 8-битных знаковых чисел (–128..127), то аналогичную процедуру их умножения можно найти в [10]. Там же приведена и процедура быстрого неточного умножения с использованием формулы xy = (y+(x/2–y/2))2–(x/2–y/2)2.

В [24] также приведены процедуры умножения для 8-битных и 6-битных знаковых чисел.

Таблица квадратов чисел разрядности n содержит 2n значений, каждое из которых занимает n/4 байтов. Для 8-разрядных чисел размер таблицы равен 512 байтам, а для 16-разрядных чисел получится уже 65536*4 = 262144 байта! Такая таблица, очевидно, в памяти не уместится. Как же быть? В этом случае можно представить произведение чисел разрядности n в виде суммы произведений чисел разрядности n/2.

Пусть нам надо перемножить два 16-разрядных числа x и y. Разобьём их на 8-разрядные части: x1 — старшая часть x, x2 — младшая; y1 и y2 — аналогично. Получим:

xy = (256x1+x2)(256y1+y2) = 65536x1x2+256(x1y2+x2y1)+x2y2.

Если нужно пожертвовать точностью для повышения скорости, последним слагаемым можно пренебречь: при больших значениях сомножителей его влияние на результат незначительно. Тогда умножение двух 16-разрядных чисел сведётся к сложению трёх произведений 8-разрядных чисел.

Формирование таблицы квадратов чисел от 0 до 255, необходимой для умножения, — отдельный интересный вопрос. Можно заранее посчитать таблицу на Бейсике и включить её в программу, но это очень неэкономно. Гораздо выгоднее создать таблицу непосредственно на ассемблере. При этом следует стремиться к тому, чтобы процедура её создания была как можно короче. Время её работы не так важно, ведь обычно она вызывается лишь один раз за всё время работы программы (кстати, тогда вовсе не обязательно оформлять отдельную процедуру и вызывать её с помощью CALL — выгоднее непосредственно вставить её в текст программы, сэкономив на этом четыре байта).

При создании таблицы используется следующее свойство: квадрат числа n равен сумме n последовательно взятых нечётных чисел: так, например, 42 = 1+3+5+7 = 16. Таким образом, прибавляя очередное нечётное число, мы получим очередное значение квадрата.

В [9] приводится 16-байтный фрагмент программы, очень быстро создающий таблицу квадратов, но при этом производятся манипуляции со стеком, таблица получается перевёрнутой, а двухбайтные значения квадратов размещаются в ней подряд, в то время как для быстрого доступа к таблице необходимо, чтобы младшие байты квадратов находились в первых 256 байтах таблицы, а старшие — в следующих 256 (или наоборот).

В [3] приведена занимающая 20 байтов процедура, создающая как раз такую таблицу, какую надо. Немного поразмыслив, я сократил её ещё на два байта (а для 20-байтной процедуры два байта — это много!). К тому же мой вариант процедуры, в отличие от оригинального, не использует регистровую пару BC. Итак, вот:

MK_SQ_TAB  XOR  A
           LD   H,A
           LD   L,A
           LD   E,A

M2         LD   D,TABL_SQR/256
           EX   DE,HL
           LD   (HL),E
           INC  H
           LD   (HL),D
           EX   DE,HL
           LD   D,A    ;=LD D,0.
           ADD  HL,DE
           INC  E
           ADD  HL,DE  ;На флаг Z не влияет.
           JR   NZ,M2

           RET

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

Если нужно построить таблицу квадратов, делённых на 2 или 4, в процедуру надо добавить команды, сдвигающие результат соответственно на один или два разряда вправо:

MK_SQ_TAB2 XOR  A
           LD   H,A
           LD   L,A
           LD   E,A

M2         LD   D,TABL_SQR/256+1
           EX   DE,HL
           LD   (HL),D
           LD   A,E

;Делим результат на 2:

           SRL  (HL)
           RRA

;Ещё раз делим на 2 (если надо получить значения,
;делённые на 4):

           SRL  (HL)
           RRA

           DEC  H
           LD   (HL),A
           EX   DE,HL
           LD   D,0
           ADD  HL,DE
           INC  E
           ADD  HL,DE  ;На флаг Z не влияет.
           JR   NZ,M2

           RET

Поговорим теперь ещё об одном способе быстрого умножения, описанном в [2]. Этот довольно экзотический способ основан на специальной форме представления чисел — записи в остатках.

Пусть нам надо производить вычисления с числами в диапазоне от 0 до N–1. Выберем несколько взаимно простых чисел s1, s2,…, sm с таким расчётом, чтобы их произведение было не меньше N:

s1s2sm >= N.

Тогда каждое число можно однозначно записать остатками от деления на s1, s2,…, sm. Рассмотрим это на примере: пусть N=30, а в качестве взаимно простых чисел s1, s2,… выбраны 2, 3 и 5 (при этом условие s1s2s3>=N, как видим, выполняется).

Запись всех 30 чисел в остатках от деления на 2, 3 и 5 приведена ниже. Первая цифра в записи — остаток от деления на 5, вторая — на 3, третья — на 2 (впрочем, можно было бы выбрать и любой другой порядок записи).

Табл. 1
Число Запись в остатках Число Запись в остатках
000015001
111116110
222017221
330118300
441019411
502120020
610021101
721122210
832023321
940124400
1001025011
1112126120
1220027201
1331128310
1442029421

Важное достоинство такого способа представления чисел состоит в том, что сложение, вычитание и умножение оказываются простыми поразрядными операциями. Чтобы сложить (вычесть, умножить) два числа, достаточно сложить (вычесть, умножить) значения в каждом из разрядов по модулю этого разряда.

Пусть нам, например, надо умножить 9 на 3:

9 в остатках — 401,
3 в остатках — 301.

Выполняем умножение для каждого разряда:

4*3=12, берём по модулю 5 — получаем 2,
0*0=0,
1*1=1.

Получили значение 201, смотрим в таблицу — как и ожидалось, это соответствует числу 27. Как видим, всё довольно просто.

Чтобы работать с числами в диапазоне 0—255, удобно выбрать три простых числа 2, 11 и 13. Почему я выбрал именно эти три числа? Число 2 — потому что операцию умножения остатков 0, 1 по модулю 2 можно осуществлять непосредственно командой AND, ну а числа 11 и 13 выбраны как наименьшие, при которых произведение всех трёх чисел больше 256 (2*11*13=286).

Нижеследующая процедура служит для того, чтобы представить число в остатках. Для увеличения скорости работы она использует две 256-байтные таблицы, располагающиеся в памяти одна за другой и начинающиеся с адреса TMOD, кратного 256. В первой таблице приведены остатки от деления чисел 0—255 на 11, во второй — остатки от деления на 13. Формируются эти таблицы весьма просто: первая циклически заполняется числами 0, 1, 2,…, 10, а вторая — числами 0, 1, 2,…, 12.

Вход : A - преобразуемое число.
Выход: A,D,E - остатки от деления этого числа на 2, 11, 13.
Длина: 9 байтов - сама процедура + 512 байтов - таблицы.
Время: 46 тактов.

    LD  H,TMOD/256 ;Старший байт адреса первой таблицы.
    LD  L,A        ;Число служит индексом в таблице.
    LD  D,(HL)     ;D - остаток от деления на 11.
    INC H          ;Перешли ко второй таблице.
    LD  E,(HL)     ;E - остаток от деления на 13.
    AND 1          ;A - остаток от деления на 2.
    RET            ;Выход.

Следующая процедура выполняет обратную задачу — восстанавливает число A по остаткам от деления на 2, 11 и 13 (обозначим их A mod 2, A mod 11 и A mod 13). Для этого используется 512-байтная таблица TABL_CR, начинающаяся с кратного 256 адреса, в которой по смещению (A mod 2)*256+(A mod 11)*16+(A mod 13) находится число A. Для быстрого умножения на 16 используется таблица TABL_M16, также начинающаяся с кратного 256 адреса.

Вход : B,L,A - остатки от деления на 2, 11, 13.
Выход: A - число.
Длина: 10 байтов - сама процедура + 768 байтов - таблицы.
Время: 50 тактов.

    LD  H,TABL_M16/256 ;Старший байт адреса таблицы TABL_M16.
    ADD A,(HL)         ;В (HL) находится (A mod 11)*16.
    LD  L,A            ;L:=(A mod 11)*16+(A mod 13).
    LD  A,TABL_CR/256  ;Прибавляем к старшему байту адреса
    ADD A,B            ;таблицы TABL_CR значение (A mod 2).
    LD  H,A            ;Теперь HL - адрес в таблице.
    LD  A,(HL)         ;Берём из таблицы число.
    RET                ;Выход.

Ну а вот то, для чего всё это и затевалось, — процедура умножения двух чисел в остатках. С адреса, кратного 256, находится уже рассмотренная ранее таблица TABL_M16; с адреса, на 256 большего, располагается таблица для быстрого умножения чисел по модулю 11, в которой по смещениям 16x+y находятся значения xy mod 11; с адреса, большего ещё на 256 байтов, располагается аналогичная таблица для умножения по модулю 13.

Вход : B,D,E - остатки от деления 1-го множителя на 2, 11, 13;
       A,C,L - остатки от деления 2-го множителя на 2, 11, 13.
Выход: B,D,E - остатки от деления произведения на 2, 11, 13.
Длина: 17 байтов - сама процедура + 768 байтов - таблицы.
Время: 85 тактов.

    AND B      ;Вычислили остаток от деления произведения на 2
    LD  B,A    ;и поместили в B.

    LD  H,TABL_M16/256
    LD  A,E
    OR  (HL)
    LD  E,A    ;В E теперь находятся остатки от деления
               ;сомножителей на 13 (в упакованной форме).
    LD  L,D
    LD  A,C
    OR  (HL)
    LD  L,A    ;Аналогично, в L - остатки от деления на 11
               ;в упакованной форме.
    INC H
    LD  D,(HL) ;Умножили остатки от деления на 11 с помощью
               ;таблицы.
    LD  L,E
    INC H
    LD  E,(HL) ;Так же поступаем и с остатками от деления на 13.

    RET        ;Выход.

Для выполнения единичного умножения, по-видимому, такой метод не годится: на преобразования чисел в остатки и обратно уйдёт больше времени, чем на само умножение. А вот если надо произвести длинную цепочку вычислений, преобразовав результат лишь в конце, экономия времени может быть весьма значительной.

Деление

Начнём с деления на степень двойки (2, 4, 8…). В [1] упоминалось, что такое деление удобно выполнять с помощью команд логического сдвига: когда делимое находится в аккумуляторе — SRL A; когда делимое находится в регистровой паре HL — SRL H: RR L, и так далее. Во многих случаях, однако, эти способы можно существенно оптимизировать. За счёт чего?

В системе команд Z80 имеются четыре команды ротации (т.е. циклического сдвига) числа, находящегося в аккумуляторе: RLCA, RLA, RRCA и RRA. Эти команды производят ротацию вправо/влево, простую или через флаг CY. Их особенность в том, что они занимают один байт памяти и выполняются за четыре такта, в то время как все остальные команды сдвига и ротации регистров (в том числе и SRL) занимают два байта памяти и выполняются за восемь тактов. Так вот, во многих случаях удаётся использовать эти быстрые и короткие команды вместо медленных и длинных, за счёт чего и получается выигрыш в объёме и/или быстродействии программы.

Пусть делимое находится в аккумуляторе. Для деления на два используется команда SRL A (2 байта/8 тактов), и в общем случае тут ничего не сэкономишь. Но если известно, что флаг CY сброшен, достаточно применить команду RRA (1 байт/4 такта). Если состояние CY не известно, но мы знаем, что делимое чётно, можно использовать для деления команду RRCA (те же 1 байт/4 такта).

Никогда не ставьте несколько команд SRL A подряд, чтобы разделить значение аккумулятора на 4, 8, 16… — это невыгодно! Для деления на 4, 8 и 16 используйте команды RRCA, а для деления на 32, 64 и 128 сдвигайте аккумулятор в обратном направлении командами RLCA, так как общее число сдвигов при этом будет меньше. Затем командой AND обнулите старшие биты результата.

Пример: деление аккумулятора на четыре.

 Было:  SRL A         ;2 байта, 8 тактов
        SRL A         ;2 байта, 8 тактов
        ---------------------------------
        Итого:         4 байта, 16 тактов

Стало:  RRCA          ;1 байт,  4 такта
        RRCA          ;1 байт,  4 такта
        AND %00111111 ;2 байта, 7 тактов
        ---------------------------------
        Итого:         4 байта, 15 тактов

В этом примере выигрыш составил лишь один такт. Но при делении на 8, 16 и т.д. мы выиграем и в длине программы, и в скорости её выполнения. Если нужно выполнить больше трёх делений подряд, можно заранее записать второй операнд команды AND в регистр и затем экономить на каждой AND 1 байт/3 такта. Ну а если известно, что деление будет нацело, команда AND вообще не нужна.

Пусть делимое находится не в аккумуляторе, а в каком-либо другом регистре или ячейке памяти. Иногда бывает выгодно сначала переслать его в аккумулятор, выполнить деление, а затем переслать результат обратно.

Пример: деление регистра E на 32.

 Было:  SRL E         ;2 байта,  8 тактов
        SRL E         ;2 байта,  8 тактов
        SRL E         ;2 байта,  8 тактов
        SRL E         ;2 байта,  8 тактов
        SRL E         ;2 байта,  8 тактов
        ----------------------------------
        Итого:        10 байтов, 40 тактов

Стало:  LD  A,E       ;1 байт,   4 такта
        RLCA          ;1 байт,   4 такта
        RLCA          ;1 байт,   4 такта
        RLCA          ;1 байт,   4 такта
        AND %00000111 ;2 байта,  7 тактов
        LD  E,A       ;1 байт,   4 такта
        ----------------------------------
        Итого:         7 байтов, 27 тактов

Впрочем, если для деления 8-битного операнда на два команды ротации или сдвига — вне конкуренции, то уже деление на четыре может быть выполнено быстрее с помощью табличного способа.

Рассмотрим теперь возможный вариант оптимизации для случая, когда делимое располагается в регистровой паре. При делении на 8, 16, 32… выгодно поступить так: сначала переслать младший байт делимого в аккумулятор, а затем сдвигать старший байт командой SRL, а младший — быстрой командой RRA. После окончания деления младший байт пересылается из аккумулятора обратно.

Пример: деление HL на 8.

 Было:  SRL H   ;2 байта,  8 тактов
        RR  L   ;2 байта,  8 тактов
        SRL H   ;2 байта,  8 тактов
        RR  L   ;2 байта,  8 тактов
        SRL H   ;2 байта,  8 тактов
        RR  L   ;2 байта,  8 тактов
        ----------------------------
        Итого:  12 байтов, 48 тактов

Стало:  LD A,L  ;1 байт,   4 такта
        SRL H   ;2 байта,  8 тактов
        RRA     ;1 байт,   4 такта
        SRL H   ;2 байта,  8 тактов
        RRA     ;1 байт,   4 такта
        SRL H   ;2 байта,  8 тактов
        RRA     ;1 байт,   4 такта
        LD L,A  ;1 байт,   4 такта
        ---------------------------
        Итого:  11 байтов, 44 такта

Чтобы найти остаток от деления на 2n, достаточно оставить командой AND младшие n битов делимого. Например, остаток от деления аккумулятора на 8 (8=23) вычисляется командой AND %111.

Несколько слов о знаковом делении на степень двойки. Для деления 8-битного операнда используется команда арифметического сдвига вправо SRA, и приспособить быстрые команды ротации тут, к сожалению, не получится (хотя, если знак операнда известен…). Для 16-битного операнда можно использовать тот же приём оптимизации, что и при беззнаковом делении (см. пример выше), только вместо команды SRL будет SRA.

Кстати, о сдвигах. Допустим, нам надо разделить беззнаковое число, находящееся в ячейке памяти по адресу (IX+7), на два, а затем загрузить результат в аккумулятор. Можно сделать так:

SRL (IX+7)    ;4 байта,  23 такта
LD  A,(IX+7)  ;3 байта,  19 тактов
----------------------------------
Итого:         7 байтов, 42 такта

Но гораздо выгоднее сделать это одной командой:

SRL A,(IX+7)  ;4 байта, 23 такта

«Что-то не припомню такой команды» — скажет кто-то, и будет по-своему прав. Действительно, в описании системы команд Z80 вы её не найдёте: она не документирована. Ниже приведён полный список недокументированных команд, позволяющих выполнить сдвиг или ротацию числа в ячейке памяти, адресуемой (IX+s) или (IY+s), а потом загрузить результат в один из регистров A, B, C, D, E, H, L.

Табл. 2
Мнемоника Машинные коды
RLC reg,(IX+s)#DD #CB s %00000reg
RLC reg,(IY+s)#FD #CB s %00000reg
RRC reg,(IX+s)#DD #CB s %00001reg
RRC reg,(IY+s)#FD #CB s %00001reg
RL reg,(IX+s)#DD #CB s %00010reg
RL reg,(IY+s)#FD #CB s %00010reg
RR reg,(IX+s)#DD #CB s %00011reg
RR reg,(IY+s)#FD #CB s %00011reg
SLA reg,(IX+s)#DD #CB s %00100reg
SLA reg,(IY+s)#FD #CB s %00100reg
SRA reg,(IX+s)#DD #CB s %00101reg
SRA reg,(IY+s)#FD #CB s %00101reg
SLI reg,(IX+s)#DD #CB s %00110reg
SLI reg,(IY+s)#FD #CB s %00110reg
SRL reg,(IX+s)#DD #CB s %00111reg
SRL reg,(IY+s)#FD #CB s %00111reg

Все указанные в таблице команды выполняются за 23 такта. В машинных кодах вместо reg подставляются три бита 111, 000, 001, 010, 011, 100 и 101 соответственно для регистров A, B, C, D, E, H, L. Если же подставить три бита 110 — получится обычная, документированная разновидность команды. Как это можно объяснить? При выполнении команды сдвига или ротации содержимого ячейки памяти Z80 считывает оттуда байт в какой-либо регистр, выполняет нужные действия (сдвиг или ротацию), а затем записывает результат в ту же ячейку памяти. При этом в регистре результат остаётся. Так вот, три бита 110 соответствуют специальному «служебному», скрытому от пользователя регистру Z80, поэтому нам и кажется, что команда действует на находящееся в памяти число, не меняя содержимого регистров. Ну а если в качестве «служебного» использовать один из обычных регистров, побочным действием команды будет изменение содержимого этого регистра.

Для чего я указал в таблице машинные коды команд? Дело в том, что большинство ассемблеров (если не все) не понимают таких мнемоник, и приходится записывать нужную команду с помощью директивы DB (define byte). Вот, например, как будет записана уже упоминавшаяся команда SRL A,(IX+7):

DB #DD,#CB,7,%00111111

Монитор-отладчик STS при дизассемблировании выводит мнемоники этих недокументированных команд, однако не позволяет их ввести.

Да, вы, наверное, заметили в таблице незнакомую мнемонику — SLI. Эта команда сама по себе является недокументированной и осуществляет сдвиг влево с записью 1 в младший разряд (иначе говоря, умножает операнд на два с одновременным прибавлением единицы). Иногда она может оказаться полезной. Мнемоника SLI поддерживается большинством ассемблеров и отладчиком STS. (Иногда для обозначения этой команды используют мнемонику SLL или SLIA.)

Поговорим теперь о быстром делении аккумулятора на константу, не являющуюся степенью двойки. Вот один из способов такого деления, о котором я узнал из эхоконференции DEMO.DESIGN.

Пусть надо выполнить деление, скажем, на три. Приближённо можно считать, что три — это 8/3 (фактически же 8/3 = 2,66…). Тогда A/3 ~= 3A/8, и деление будет выглядеть так:

    LD  B,A
    ADD A,A
    ADD A,B
    RRCA
    RRCA
    RRCA
    AND %00011111

31 такт — быстрее, чем по универсальной подпрограмме, но зато менее точно. Впрочем, относительная погрешность при этом постоянна, и её можно уменьшить, взяв более точное приближение — скажем, 3 ~= 16/5.

Если цель — выполнить деление как можно быстрее, а расход памяти не столь важен, можно использовать табличный способ. Он позволяет осуществлять деление на любую константу с помощью 256-байтной таблицы, размещённой с адреса, кратного 256. При этом, если заранее поместить старший байт адреса таблицы в регистр H, деление будет осуществляться всего за 11 тактов:

    LD L,A
    LD A,(HL)

Аналогично для случая, когда делимое находится в другом регистре (например, в C):

    LD L,C
    LD C,(HL)

Перейдём к делению произвольных чисел. Различные процедуры деления «в столбик» уже приводились в [1]. Более быструю, чем описанная там, процедуру деления 16-разрядных чисел вы можете найти в [22] (вычисляется частное и остаток, максимальное время выполнения — 840 тактов без учета RET; если остаток не нужен — 818 тактов). Процедуры деления «в столбик» операндов различной разрядности приведены также в [24].

А более быстрые способы? По сравнению с умножением, их не так уж и много (по крайней мере, такое у меня сложилось впечатление). Здесь я кратко расскажу о трёх из них.

Первый — деление по таблице, в которой находятся уже вычисленные заранее результаты деления x/y для всех возможных x и y. Реализуется аналогично умножению по таблице (см. предыдущий раздел). Достоинства и недостатки — те же самые.

Второй — замена деления умножением на взятую из таблицы обратную величину: x/y = x(1/y). От точности обратной величины будет зависеть и точность деления. Между прочим, этим способом пользовались ещё в древнем Вавилоне (начало 2-го тыс. до н.э.).

Если размер свободной памяти ограничен, и значения в таблице нельзя представить с необходимой точностью, можно использовать рассмотренный в [2] способ итеративного вычисления обратной величины. Пусть имеется некоторое начальное приближение (скажем, взятое из таблицы): k1 ~= 1/y. Тогда следующее приближение будет таким: k2 = k1(2–yk1), и так далее. Если относительная погрешность приближения достаточно мала по сравнению с единицей, то при каждой итерации количество верных знаков будет удваиваться: так, если требуется точность в 32 двоичных разряда, а первое приближение находится по таблице с 8 верными двоичными знаками, то потребуется всего две итерации.

Существуют и более сложные формулы итераций. Ниже приведены две из них: каждая итерация по первой формуле утраивает количество верных знаков, а по второй формуле — учетверяет.

ki+1 = ki(3(1–yki)+(yki)2)
ki+1 = ki(6(4–yki)+(yki)2(4–yki)–20)

Кстати, ранее рассмотренный способ приближённого деления на константу — не что иное, как умножение на обратную величину, только размер этой обратной величины ограничен несколькими битами.

Третий способ — логарифмическое деление, основанное на следующей формуле (A — основание системы логарифмов):

x/y = A(log x–log y).

Пример процедуры, осуществляющей такое деление, можно найти в [10].

Как видим, использование логарифмов позволяет значительно упростить и ускорить вычисления за счёт того, что умножение и деление сводятся к сложению и вычитанию, а возведение в степень и извлечение корня (см. следующий раздел) — к умножению и делению.

Кто-то из великих сказал: «Изобретение логарифмов позволило в считанные дни производить те вычисления, которые раньше делались месяцами». Ну а в наше время логарифмы позволяют за сотню тактов производить те вычисления, которые раньше делались за тысячу.

Квадратные и другие корни. Возведение в любую степень.

В [1] рассказывалось о методе вычисления целой части квадратного корня путём последовательного вычитания нечётных чисел и об итерационном методе вычисления квадратного корня. Что ещё можно к этому добавить?

Классический алгоритм вычисления квадратного корня «в столбик» подробно описан в [2].

Процедуру, вычисляющую квадратный корень по модифицированному алгоритму Ньютона за 1500—2500 тактов, можно найти в [3].

Достаточно быстрая процедура вычисления квадратного корня приведена в [14]. Время её работы (без учёта команды RET) — от 294 до 318 тактов при значении аргумента 0—255 и от 581 до 629 тактов при значении аргумента 256—65535.

Это не предел: используя ранее описанную в разделе «Умножение» таблицу квадратов чисел от 0 до 255, можно вычислить значение корня в среднем в 1,3 раза быстрее. Вот соответствующий алгоритм (x — аргумент функции, sq_tab — таблица квадратов):

    1. i:=#80, n:=#40.
    2. Если x < sq_tab(i), то i:=i–n, иначе i:=i+n.
    3. n:=[n/2]; если n<>0, то идти к пункту 2.
    4. Если x < sq_tab(i), то i:=i–1.
    5. i — искомое значение корня.

Здесь мы пользуемся тем, что функция y = x2 монотонно возрастает при изменении аргумента от нуля до бесконечности, а значит, таблица квадратов представляет собой упорядоченный по возрастанию массив чисел.

Вот текст процедуры:

Вход : DE - аргумент.
Выход: L - целая часть квадратного корня.
Длина: 56 байтов - сама процедура + 512 байтов - таблица квадратов.
Время: в среднем 470 тактов, если значения аргумента равномерно
       распределены в интервале 0-65535.

        LD   B,#40           ;В регистре B разместим n (#40),
        LD   HL,SQ_TAB+#180  ;а в регистре L - i (#80).

;Сравниваем x и sq_tab(i), начиная со старшего байта, т.к.
;больше вероятность, что значения будут различны в старшем
;байте, чем в младшем:

M4      LD   A,D
        CP   (HL)
        JR   C,M2   ;Вероятности выполнения и невыполнения
                    ;условия одинаковы - ставим JR (в среднем
                    ;(7+12)/2 = 9,5 тактов).
        JP   NZ,M1  ;А вот тут условие будет выполняться почти
                    ;всегда - ставим JP (10 тактов).

;Если старшие байты равны, сравниваем младшие байты:

        DEC  H
        LD   A,E
        CP   (HL)
        INC  H      ;INC на флаг CY не влияет.
        JR   C,M2   ;Вероятности одинаковы - ставим JR.

;x >= sq_tab(i):

M1      LD   A,L    ;i:=i+n
        ADD  A,B
        LD   L,A

        SRL  B      ;n:=[n/2]
        JP   NZ,M4  ;Условие будет выполняться в шести случаях
                    ;из семи - ставим JP.

        LD   A,D    ;Четвёртый пункт алгоритма -
        CP   (HL)   ;сравниваем старшие байты...
        JR   C,M5
        RET  NZ

        LD   A,E    ;...и младшие.
        DEC  H
        CP   (HL)
        RET  NC

M5      DEC  L      ;i:=i-1
        RET

;x < sq_tab(i):

M2      LD   A,L    ;i:=i-n
        SUB  B
        LD   L,A

;Далее аналогично уже рассмотренному...

        SRL  B      ;n:=[n/2]
        JP   NZ,M4

;Тут можно было бы поставить команду перехода (JP) на такой же
;фрагмент программы, встречавшийся выше, но мы потеряли бы на
;этой команде десять тактов...

        LD   A,D
        CP   (HL)
        JR   C,M3
        RET  NZ

        LD   A,E
        DEC  H
        CP   (HL)
        RET  NC

M3      DEC  L
        RET

В [22] приведены процедуры извлечения корня из 16-битного и 24-битного операндов без использования таблиц. Максимальное время их работы — соответственно 470 и 1026 тактов (без учёта RET).

В [21] подробно описан очень быстрый способ извлечения корня, основанный на следующей формуле: если x представить в виде m*2n (где n чётно), то sqrt(x)=sqrt(m)*2n/2. В приведённой там же процедуре извлечения корня из 16-битного операнда все вычисления производятся с помощью таблиц общим объёмом 3 КБ, и тратится на это, без учёта команды RET, всего 76 тактов! Там же показано, как сократить время вычислений ещё на 3 такта за счет увеличения места под таблицы на 2 КБ.

Ну а самый быстрый способ, конечно, — взять значение корня из предварительно рассчитанной и помещённой в дополнительную память ZX Spectrum 128 полной 64-килобайтной таблицы квадратных корней. Пусть в 4 банках ОЗУ хранятся значения корней для чисел 0—#3FFF, #4000—#7FFF, #8000—#BFFF и #C000—#FFFF. Тогда, чтобы взять из таблицы значение корня, можно использовать такой фрагмент программы:

Вход : DE - аргумент.
Выход: A - целая часть квадратного корня.
Длина: 12 байтов - сам фрагмент, 256 байтов - таблица tab_bank
       (чтобы определять по двум старшим битам аргумента число,
       которое надо вывести в порт #7FFD для подключения банка
       ОЗУ, в котором находится значение корня для данного
       аргумента), 256 байтов - таблица для быстрой установки в 1
       двух старших битов аргумента (эта таблица должна идти
       сразу за предыдущей, и они должны начинаться с адресов,
       кратных 256), 64 КБ - таблица корней.
Время: 58 тактов.

        LD   BC,#7FFD
        LD   H,tab_bank/256 ;Определяем по двум старшим битам DE
        LD   L,D            ;банк ОЗУ, где находится значение
        LD   A,(HL)         ;корня.
        OUT  (C),A          ;Подключили нужный банк.
        INC  H              ;Устанавливаем старшие 2 бита DE
        LD   D,(HL)         ;в 1, чтобы получить нужный адрес.
        LD   A,(DE)         ;Прочитали значение корня.

В [8] описан итерационный способ нахождения корня любой степени, а в качестве примера приведена процедура вычисления кубического корня.

Ну и, наконец, корень любой степени можно вычислить с помощью логарифмов, пользуясь следующей формулой (A — основание логарифмов):

x1/n = A(log x)/n.

Теперь несколько слов о возведении в степень. Если степень целая, то можно воспользоваться сведениями, взятыми из [8]. Там описаны два способа возведения в степень: первый основан на последовательном умножении (например, x4 = xxxx), а второй, более быстрый, использует разложение показателя степени на множители, кратные двум (например, x5 = ((x2)2)x). Там же можно найти и тексты соответствующих процедур.

Если степень не целая, удобной окажется следующая формула (опять-таки с использованием логарифмов):

xn = A(n log x).

Если скорость вычислений по этой формуле покажется вам недостаточной, можно использовать таблицу с уже вычисленными заранее значениями xn для всех возможных x и n — лишь бы для неё хватило памяти.

Тригонометрия

В [1] предлагается для вычисления синуса и косинуса использовать таблицу синусов углов от 0° до 90° в сотых долях, с шагом в один градус. Но для быстрых вычислений (например, при реализации какого-либо графического эффекта) обычно используют немного другую таблицу — 256-байтную. В ней представлены значения синуса или косинуса в 128-х долях (со знаком) для углов от 0 до 2*Pi с шагом в 2*Pi/256. (Обратите внимание: в последнем элементе таблицы хранится значение функции не для угла 2*Pi, а для угла 2*Pi*255/256; угол 2*Pi — то же самое, что угол 0, и значение функции для него находится в первом элементе таблицы.)

Почему использование такой таблицы более удобно? Значение угла обычно хранят в 8-разрядной переменной: углам от 0 до 2*Pi*255/256 соответствуют значения переменной от 0 до 255. При этом для вычисления синуса или косинуса достаточно использовать значение переменной в качестве индекса в таблице. При циклическом изменении значения угла нет необходимости в отслеживании ситуаций, когда он выходит из диапазона 0—2*Pi: так как вычисления ведутся по модулю 256, значение угла автоматически преобразуется к этому диапазону. Да и значения функции представлены в таблице чуть более точно (в 128-х долях, а не в сотых).

Особенно удобно работать с таблицей, если она начинается с адреса, кратного 256, — тогда значение угла будет одновременно и значением младшего байта адреса, по которому находится синус или косинус этого угла.

Так как график синуса отличается от графика косинуса только сдвигом на четверть периода, в программах обычно используют одну и ту же таблицу для вычисления и синуса, и косинуса. Например, если в таблице приведены значения синуса, то для вычисления косинуса требуется лишь прибавить к индексу число 256/4=64 (и это вместо использования громоздких формул приведения — оцените удобство!).

Когда стоит задача уменьшения размера программы (например, при написании intro), имеет смысл вместо непосредственного хранения таблицы создавать её на ассемблере. Фрагмент программы, создающий таблицу, должен быть как можно короче (и уж, во всяком случае, короче самой таблицы), а время его работы большого значения не имеет — ведь таблицу надо создать всего один раз.

В [15] приводятся две процедуры формирования таблицы синусов, причём при их вызове имеется возможность задать нужную амплитуду и смещение по оси y (т.е. фактически создаётся таблица значений функции y = a sin x + b). Первая процедура занимает всего 39 байтов (и ещё 6 байтов на задание входных параметров), но работает неприлично долго — около пятнадцати секунд. Что поделать, такова плата за использование калькулятора ПЗУ. Вторая процедура — гораздо более быстрая, но и более длинная: 119 байтов (и ещё 6 байтов на задание параметров). Из них 64 байта занимает таблица, соответствующая четверти периода синуса. Как видим, реально синус не вычисляется — отсюда и высокая скорость работы.

Более короткую процедуру, создающую таблицу синусов без использования калькулятора ПЗУ, можно найти в [16]. Её длина — 75 байтов, из них 31 байт (а не 64, как в рассмотренной выше процедуре!) занимает информация о четверти периода синуса (приращения, упакованные методом RLE).

Получаемая в результате таблица обладает некоторыми особенностями. Фактически в ней приведены значения функции y = |sin x|, так что знак при расчётах вам придётся учитывать самим (для первого полупериода — «+», для второго — «–»). Это позволило повысить точность значений синуса: они представлены в 256-х долях, а не в 128-х.

Интересная процедура построения таблицы косинусов приводится в [10]. Посмотрим на график функции y = cos x (рис. 1). Видно, что его часть, лежащая ниже оси x, по форме напоминает параболу, а часть, лежащая выше оси x, легко получается путём симметричного отражения. Параболическая интерполяция и используется при создании таблицы.

Рис. 1

Конечно, такое приближение не является абсолютно точным (рис. 2), но для графических эффектов точность вполне достаточна. Зато длина процедуры — всего 43 байта! А с помощью несложной доработки становится возможным и получение 16-битных значений.

Рис. 2

Нелегко было сократить эту процедуру хотя бы на байт. Но мне удалось, применив другой способ вычисления квадратов, уменьшить её длину на целых три байта! При этом ещё и время построения таблицы сократилось в 3,3 раза. К тому же удалось обойтись без использования недокументированной команды SLI, что может иметь решающее значение в случае, когда вы пишете программу для процессора, совместимого с Z80 лишь по документированным командам.

Итак, вот оптимизированный вариант:

GEN_COS    LD   HL,#FF01 ;127^2+#C000
           LD   D,H
           LD   E,L
           LD   BC,COS_TABL+#40
           PUSH BC

           EXX
           POP  DE
           LD   BC,COS_TABL+#C0
           LD   H,B
           LD   L,C

GEN_LOOP   DEC  E
           DEC  L
           EXX

           LD   A,L
           ADD  A,A
           LD   A,H
           ADC  A,A

           INC  E
           INC  E
           ADD  HL,DE
           INC  E
           INC  E
           ADD  HL,DE

           LD   (BC),A
           INC  C
           EXX
           LD   (HL),A
           CPL
           LD   (DE),A
           LD   (BC),A
           INC  C
           JR   NZ,GEN_LOOP

           RET

А если вставить эту процедуру в программу непосредственно, без CALL/RET (как чаще всего и делают для сокращения размера), выигрыш составит уже пять байтов! Действительно, при отбрасывании команды RET мы получим 39-байтный фрагмент программы, а в исходной процедуре RET (условный) находится в середине, и придётся заменить его на условный JR — в результате получится 44-байтный фрагмент.

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

GEN_COS_2  LD   HL,SQ_TAB+#1FE
           LD   BC,COS_TABL+#40
           LD   D,B
           LD   E,C

GEN_LOOP   DEC  E

           LD   A,(HL)
           SCF
           RRA

           RES  7,C
           LD   (BC),A
           SET  7,E
           LD   (DE),A
           CPL
           SET  7,C
           LD   (BC),A
           RES  7,E
           LD   (DE),A

           DEC  L
           DEC  L
           DEC  L
           DEC  L

           INC  C
           JR   NZ,GEN_LOOP

           RET

Оригинальный способ приближённого построения таблицы синусов описывается в [19]. Сущность его в следующем: очередное значение вычисляется путем прибавления к предыдущему значению некоторого приращения, которое, в свою очередь, постепенно уменьшается по определённому закону. Приведённый в [19] фрагмент программы, строящий этим способом 128-байтную беззнаковую таблицу первого полупериода синуса, занимает всего 24 байта! А насчёт похожести на настоящий синус — взгляните на рис. 3. Сплошной линией показан график функции y = sin x, точками — генерируемые приближённые значения (соответственно масштабированные). Как видите, сходство весьма велико!

Рис. 3

А какая же процедура точного построения таблицы синусов/косинусов самая-самая короткая? Вот написанная мной процедура рекордно малой длины: всего 36 байтов. Она использует калькулятор ПЗУ и выполняется довольно долго, около двенадцати секунд. Впрочем, это меньше, чем время выполнения процедуры, приведённой в [15].

C_TO_STACK EQU  #2D29 ;Помещает число из регистра C на стек
                      ;калькулятора.
FROM_STACK EQU  #2DD5 ;Снимает число со стека и помещает в A.

;Используемые команды калькулятора:

multiply   EQU  #04   ;умножение
add_       EQU  #0F   ;сложение
sin        EQU  #1F   ;синус
cos        EQU  #20   ;косинус
stk_data   EQU  #34   ;поместить число на стек
end_calc   EQU  #38   ;выход из калькулятора
stk_one    EQU  #A1   ;поместить единицу на стек

           LD   BC,TABL

LOOP       PUSH BC
           CALL C_TO_STACK

;Вычисление
;int ((1+sin((2*Pi/255)*COUNTER))*127):

           RST  #28
           DB   stk_data ;2*Pi/255
           DB   #EB,#49,#D9,#B4,#56
           DB   multiply
           DB   sin      ;или cos
           DB   stk_one
           DB   add_
           DB   stk_data ;127
           DB   #40,#B0,#00,#7F
           DB   multiply
           DB   end_calc

           CALL FROM_STACK
           POP  BC
           SUB  #7F
           LD   (BC),A
           INC  C
           JR   NZ,LOOP

           RET

А теперь — несколько возможностей дальнейшей оптимизации этой процедуры.

Если перед её выполнением оказывается, что в регистровой паре BC находится адрес, подходящий для размещения таблицы (младший байт должен быть равен нулю), то команду LD BC,TABL, естественно, можно убрать и сэкономить три байта. Если же подходящий адрес находится в HL или DE, экономия окажется не такой большой — всего два байта. Казалось бы, какая разница, какую регистровую пару использовать в процедуре — BC, DE или HL? Но в ПЗУ по адресу C_TO_STACK находится команда LD A,C, и за счёт этого использование регистровой пары BC более выгодно. Если же мы перепишем программу для использования DE или HL, то вместо одной команды CALL C_TO_STACK придётся писать две — скажем, LD A,E: CALL C_TO_STACK+1, что займёт на байт больше.

Если таблица располагается с адреса #7F00, то после команды PUSH BC добавляем ещё LD A,B: CALL C_TO_STACK+1 (занесение числа #7F на стек калькулятора), а строку, помеченную комментарием «127», и следующую за ней убираем; команду SUB #7F заменяем на SUB B — в результате получаем экономию в два байта!

Если таблица располагается с адреса #8100, можно заменить команду SUB #7F на ADD A,B, при этом длина процедуры уменьшится на один байт.

Если вам безразлична погрешность в 1/128 на отрицательных значениях функции, можно убрать команды stk_one, add_ и SUB #7F, а вместо них записать после CALL FROM_STACK следующее: JR Z,$+3: CPL. На этом экономится один байт.

Наконец, если вас устроит таблица со значениями функции в диапазоне не от –1 до 1, а от 0 до 2 (каждое значение представляет собой беззнаковое число с фиксированной запятой: старший бит — целая часть, младшие биты — дробная часть в 128-х долях), то команду SUB #7F можно убрать совсем, и процедура станет на два байта короче. Сформированную таким образом таблицу можно использовать при реализации таких графических эффектов (скажем, «плазмы»), для которых требуется лишь, чтобы значения в ней изменялись от 0 до 255 по синусоиде.

Вычисления с плавающей точкой

Часто удаётся преобразовать алгоритм так, что вычисления с плавающей точкой сводятся к целочисленным, выполняющимся гораздо быстрее. Но всё же бывает, что без вычислений с плавающей точкой не обойтись…

Если требуется оптимизировать программу по объёму (скажем, вы решили написать 512-bytes intro), не пренебрегайте возможностью использования калькулятора ПЗУ. Описание его функций можно найти, например, в [17]. Если же для вас более важно быстродействие, могу порекомендовать библиотеку процедур для работы с 32-битными вещественными числами, приведённую в [13]. В ней реализованы наиболее употребительные операции: сложение, вычитание, умножение, деление, перевод в формат int и обратно, выделение целой части, вычисление синуса и косинуса, возведение в квадрат.

Ещё одна библиотека процедур для вычислений с плавающей точкой приведена в DEMO.DESIGN FAQ OnLine (http://www.enlight.ru/demo/faq/).

Ввод-вывод чисел

В [11] приведена процедура быстрой печати 32-битных целых чисел в десятичном виде (её написал в 1983 году Тим Патерсон из Microsoft). В [12] вы можете найти используемую при вводе таких чисел с клавиатуры процедуру преобразования из ASCII-кодов.

Полезная библиотека процедур для печати чисел в различных системах счисления приводится в [18].

Процедура преобразования 16-разрядного целого числа в строку приводится в [24].

Для ввода/вывода чисел (в том числе вещественных) можно использовать и процедуры ПЗУ. Об этом рассказывается, например, в [17].

В эхоконференции ZX.SPECTRUM мне попалось интересное сообщение (его автор — Ilya Aniskovets), в котором описывается фрагмент программы, преобразующий шестнадцатеричную цифру (0, 1,…, F) в соответствующий ASCII-код. Этот фрагмент настолько оригинален и мал, что я не смог удержаться, чтобы не поместить его здесь. Попробуйте на досуге разобраться, за счёт чего он работает.

Вход : в аккумуляторе число #00-#0F.
Выход: в аккумуляторе соответствующий ASCII-код: "0"-"F".
Длина: 5 байтов.
Время: 18 тактов.

        CP      #0A
        SBC     A,#69
        DAA

В девятом номере электронного журнала «Adventurer» был опубликован мой фрагмент для решения обратной задачи (преобразование ASCII-кода в число). Его текст приведён ниже.

Вход : в аккумуляторе код символа "0..9", "a..f" или "A..F".
Выход: в аккумуляторе - соответствующее число: #00-#0F.
Длина: 10 байтов.
Время: 35 или 37 тактов.

        RES     5,A    ;Преобразовали "a..f" к "A..F", а если в
                       ;A была цифра - ее код уменьшится на #20.
        BIT     6,A    ;Проверяем: цифра или буква?
        JR      NZ,$+4 ;Если буква, следующую команду пропускаем.
        ADD     A,#27  ;Если цифра - добавляем #27.
        SUB     #37    ;В A число от #37 до #46, и после
                       ;вычитания как раз получим #00-#0F.

Тогда мне казалось, что при длине в десять байтов подобный фрагмент может быть реализован несколькими способами, но уменьшить его длину уже нельзя. Но оказалось, что можно! Из девятого номера электронного журнала «Deja Vu» я узнал, что Max/CBX/BDA сумел сократить его ещё на два байта!

Вход : в аккумуляторе код символа "0..9", "a..f" или "A..F".
Выход: в аккумуляторе - соответствующее число: #00-#0F.
Длина: 8 байтов.
Время: 26 или 28 тактов.

        AND     #1F
        SUB     #10
        JR      NC,$+4
        ADD     A,#19

Я пробовал ещё сильнее сократить этот фрагмент с помощью команды DAA (как в рассмотренном выше примере), но, к сожалению, сделать это не удалось…

Что ещё посоветовать насчёт ввода/вывода, основываясь на собственном опыте? Если нужно быстро печатать какие-то числа, храните их в уже подготовленной для вывода форме. Так, например, сделано в моей программе BestView: при сдвиге файловой панели вправо/влево (а этот сдвиг, чтобы быть плавным, должен уложиться в 1/50 секунды), когда выводятся параметры файлов (стартовый адрес, длина и т.д.), они хранятся в памяти именно в текстовом виде. Если бы их надо было каждый раз преобразовывать, ни о какой плавности скроллинга не было бы и речи. Точно так же удалось добиться плавного скроллинга и при просмотре шестнадцатеричного дампа файла: перед просмотром он заранее преобразуется в текстовый формат.

И ещё один немаловажный вопрос: довольно часто в программе возникает необходимость вывода надписи типа «отмечено N файлов». Так вот, при этом необходимо учитывать падеж и число выводимого существительного! К сожалению, часто про это забывают, и приходится пользователю читать уродливые сообщения вроде «отмечено 21 файлов»…

Для английского языка всё просто: печатай «file», когда файл один, и «files», когда их несколько. И ведь всё равно иногда встречаешь универсальное «selected N file(s)» — лишние байты на этом экономят, что ли… В русском языке ситуация посложнее, но ненамного. Попробую пояснить это на примере.

Пусть нам надо вывести надпись «N файлов». Для этого сначала выводим само число N, а затем применяем следующие правила в указанном порядке, пока одно из них не подойдёт: если последние две цифры N — это 11, 12,…, 19, или последняя цифра N — это 0, 5, 6, 7, 8, 9, то выводим «файлов»; если последняя цифра N — это 1, то выводим «файл»; наконец, если последняя цифра N — это 2, 3, 4, то выводим «файла». Не так уж сложно, не правда ли?

Общие вопросы

Здесь я постараюсь рассказать о ряде вопросов, которые несомненно возникнут у вас при написании программы, выполняющей арифметические вычисления, особенно если от неё требуется максимальное быстродействие или минимальный объём.

Какую выбрать форму представления чисел? Ответ на этот вопрос зависит от диапазона величин, с которыми имеет дело ваша программа, от требуемой точности, а также от того, скорость выполнения каких операций нужно увеличить. Числа могут быть представлены как целые (со знаком или без знака), в формате с фиксированной или плавающей запятой, в логарифмическом виде, в остатках, в ASCII-кодах, в BCD-форме… Возможно даже, что вы придумаете свою, наиболее подходящую для конкретной задачи форму представления чисел.

Какими способами выполнять те или иные арифметические операции? Это зависит от выбранной формы представления чисел, от того, как вы хотите оптимизировать программу (по скорости или по объёму), от требуемой точности вычислений (так, иногда приходится предпочесть медленный, но точный способ быстрому, но неточному), и, наконец, от самих вычисляемых выражений (если известно, например, что половину всех операций составляет умножение, то оптимизировать надо именно его).

Как преобразовать вычисляемые выражения к наиболее оптимальному виду? Чтобы ответить на этот вопрос, необходимо знать скорости выполнения различных операций. Tогда можно, скажем, уменьшить количество «медленных» операций за счёт увеличения количества «быстрых» так, что общее время выполнения программы уменьшится. Если нужно оптимизировать программу по объёму, можно для этого сократить общее число операций, или же избавиться от какого-то типа операций (скажем, от деления — тогда подпрограмма деления станет ненужной и объём программы уменьшится). Также обратите внимание на то, что если какие-то величины вычисляются лишь для их последующего сравнения, часто вычисления можно сильно упростить: так, если надо сравнить расстояния между точками на плоскости (вычисляемые по формуле R = sqrt ((x1x2)2+(y1y2)2)), гораздо удобнее сравнивать квадраты этих расстояний, так как при этом не нужно выполнять операцию извлечения корня.

Все приведённые выше вопросы связаны между собой, и указать какой-либо порядок их решения весьма затруднительно — всё зависит от конкретной ситуации. Для максимальной оптимизации программы, скорее всего, вам придётся рассмотреть множество различных вариантов и выбрать наилучший.

Дополнительная информация

Здесь вы найдёте список использованных мной источников с кратким описанием их содержания. В основном это различные статьи, опубликованные в спектрумовских электронных газетах и журналах. Их можно попробовать найти в Интернете на любом крупном спектрумовском сайте — например, Virtual TR-DOS (http://zx.da.ru), в разделе «Press». Посмотреть их на PC можно с помощью какого-либо эмулятора, который можно найти там же.

Также рекомендую к изучению DEMO.DESIGN FAQ OnLine, размещённый в Интернете по адресу http://www.enlight.ru/demo/faq/. Там имеется раздел «Математика» с описаниями различных алгоритмов.

Итак, вот что я использовал при написании этой статьи:

  1. В.Ильичев. «Программирование арифметических операций на ассемблере». «Радиолюбитель. Ваш компьютер» 6—9/2000.
  2. М.А.Карцев. «Арифметика цифровых машин». Москва, изд-во «Наука», 1969.

    Рассмотрены различные способы представления чисел, алгоритмы выполнения сложения, вычитания, умножения, деления, извлечения корня, перевода чисел из одной системы счисления в другую и других операций.

    И пусть вас не смущает год издания этой книги — арифметика не стареет! :–)

  3. Card!nal/PGC/BD. «Кодить хочу!». Deja Vu #5.

    Процедура умножения 8*8–>16 (так я буду обозначать разрядность операндов и результата; они подразумеваются целыми и беззнаковыми, если явно не указано другое) с использованием таблицы квадратов. Процедура вычисления квадратного корня sqrt(16)–>16 по модифицированному алгоритму Ньютона.

  4. PSV/Dream Team. «Оптимизация программ по времени исполнения». Miracle #3.

    Процедура умножения 8*8–>16 «в столбик» с раскрытыми циклами.

  5. М.Спицын. «Ассемблер для чайников». ZX Format #2.

    В доступной форме рассказывается о простейших способах выполнения основных арифметических операций.

  6. Creator product. «О кодинге для начинающих». ZX Format #7.

    Библиотека процедур: деление 16/16–>16, возведение в квадрат 162–>16, умножение 16*16–>16 и 16*8–>16, извлечение квадратного корня sqrt(16)–>16, вычисление факториала (8!–>16), возведение в степень (168–>16), перевод радианы<–>градусы, вычисление синуса и косинуса.

  7. GreenFort. «Быстрые вычисления в ассемблере». ZX Format #7.

    Деление: 8/8–>8+8, 8/8–>8,8, 24/24–>24 (здесь и далее запись результата деления в виде x+y обозначает, что получается x-разрядное частное и y-разрядный остаток; запись результата деления в виде x,y обозначает, что получается x-разрядная целая часть и y-разрядная дробная часть). Умножение: 8*8–>16, 24*24–>24.

  8. GreenFort. «Арифметика II». ZX Format #8.

    Возведение в любую степень и извлечение любого корня — алгоритмы и примеры процедур.

  9. ra!d. «Генератор таблицы квадратов». Demo or Die #2.

    16-байтный фрагмент программы, быстро строящий таблицу квадратов чисел от 0 до 255.

  10. Dark/X-Trade, STS/VolgaSoft. «Спектрум+3D #1». Spectrum Expert #1.

    Обычное умножение: 8*8–>16, 16*16–>32. Быстрое умножение с помощью таблицы квадратов (знаковое): 8*8–>16; 8*8–>8 (неточное, результат — старший байт 16-битного произведения). Обычное деление: 8/8–>8+8, 15/8–>8+8, 16/16–>16+16, 31/16–>16+16. Логарифмическое деление: 8/8–>8,8; то же, но с масштабированием и когда делимое со знаком: 12/12–>8,8 (частное тоже со знаком). Генерация на ассемблере таблиц y=2(x/256)–1, y=log2x, y~=cos x.

  11. STARSOFT. “HELPFUL SUBROUTINES”. Voyager #3.

    Быстрая печать 32-битного числа в десятичном виде. Умножение: 32*16–>32, 16*16–>32. Деление: 32/16–>32, 16/16–>32.

  12. Maximum/INTEGER. «LONG??? Что это такое?». Adventurer #8.

    Работа с 32-битными числами: сложение, вычитание, печать и преобразование из ASCII-кодов.

  13. Maximum/INTEGER. «Работа с IEEE числами». Adventurer #10.

    Библиотека процедур для работы с вещественными 32-битными числами.

  14. SerzhSoft. «Пара слов о наболевшем». Adventurer #9.

    Быстрая процедура извлечения квадратного корня: sqrt(16)–>16.

  15. SerzhSoft. «Як синус забабахать». Adventurer #9.

    Две процедуры генерации таблицы y = a sin x + b на ассемблере.

  16. ALK/XTM. «Как кодить оптимально». BornDead #0A.

    Процедура генерации таблицы y=|sin x|.

  17. Стив Кремер. «Операционная система ZX Spectrum. Руководство хаккера». Island, Москва, 1994.

    Среди прочего, подробно рассмотрены команды калькулятора и процедуры ПЗУ для ввода/вывода чисел.

  18. С.Колотов. «Печать чисел в разных системах счисления». Deja Vu #4.

    Библиотека процедур, позволяющих печатать числа различных диапазонов в десятичной, шестнадцатеричной, двоичной и устанавливаемой пользователем системах счисления. Дополнительно предусмотрена печать в системе римских чисел.

  19. Cryss/Razzlers. «Секреты DAINGY». Scenergy #2.

    Очень короткая процедура генерации таблицы y~=sin x.

  20. Baze/3SC. “Fast exponential multiply”. Scenergy #2.

    Процедуры быстрого логарифмического умножения 8*8–>8 (результат — старший байт 16-битного произведения) для беззнаковых (0..255) и знаковых (–127..127) операндов. Процедура быстрого вычисления x sin y.

  21. Baze/3SC. “Fast 16-bit square root”. Scenergy #2.

    Быстрая процедура извлечения квадратного корня: sqrt(16)–>8.

  22. Aleksey Malov. «Математические процедуры». Письмо в конференции CODE.ZX от 4 Apr 2000. (Я прочитал это письмо в конференции REAL.SPECCY, где 31 Mar 2001 его процитировал Mihail Zharov.)

    Деление: 16/16–>16+16, 16/16–>16. Извлечение квадратного корня: sqrt(16)–>8, sqrt(24)–>16.

  23. А.П.Доморяд. «Математические игры и развлечения». Москва, Государственное издательство физико-математической литературы, 1961.

    Среди прочего, рассказывается о быстром умножении целых чисел с помощью таблицы значений функции [z2/4].

  24. Milos “baze” Bazelides. “Z80 Bits” (http://zilog.sh.cvut.cz/~baze/misc/z80bits.html).

    Обычное умножение: 8*8–>16, 8*16–>24; быстрое умножение с помощью таблицы квадратов: 8*8–>16 (со знаком), 6*6–>16 (со знаком); обычное деление: 8/8–>8+8, 16/8–>16+8, 16/16–>16+16, 24/8–>24+8, 24/16–>24+16, 32/8->32+8; процедуры получения 8- и 16-разрядных псевдослучайных чисел, процедура преобразования 16-разрядного числа в строку, процедура вычисления 16-bit CRC-CCITT. Как можно понять из статьи, в дальнейшем автор планирует добавить и другие процедуры.

    Обратите внимание на то, что в этой статье (по крайней мере, в её версии от 7 Jan 2003) используется нестандартный синтаксис: $ обозначает не адрес первого байта текущей команды, а адрес операнда этой команды. Поэтому, например, команда JR NC,$+2 должна быть заменена на JR NC,$+3, и так далее.

P.S. Математические процедуры на ассемблере Z80 также можно найти в Интернете на следующих сайтах и страницах: Macross Software (http://www.macross2000.org), GameBoy Dev'rs - Asm Code (http://www.devrs.com/gb/asmcode.php).

Другие мои статьи о различных приёмах оптимизации при программировании на ассемблере Z80:

1. 

«По поводу релоцируемых программ». «ZX-Ревю» 5—6/1997.

2. 

«Z80: оптимизация загрузки констант в регистры». «Радиолюбитель. Ваш компьютер» 9/2000, 2/2001 (под псевдонимом BV_Creator).

3. 

«Влияние команды OUTD на флаг переноса». «Радиолюбитель. Ваш компьютер» 5/2001, «Радиомир. Ваш компьютер» 8/2003 (под псевдонимом BV_Creator).

4. 

«Оптимизация на примере intro „Start“». «Радиомир. Ваш компьютер» 7—10/2001.

5. 

«Менеджер вызова подпрограмм из различных банков памяти». «Радиомир. Ваш компьютер» 12/2001, 2/2002, 4/2002.

6. 

«Улучшение сжатия программ на ассемблере Z80». «Радиомир. Ваш компьютер» 4/2003.

7. 

«Процедура сравнения строк на ассемблере Z80». «Радиомир. Ваш компьютер» 6/2003.

Страница Ивана Рощина > Статьи >