ZXNet эхоконференция «code.zx»

Hello, All!

═══════════════════ part_4 .T ══════════════════

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

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 раз. Правильный результат мы все же получим,
но сколько времени будет при этом потеряно! Можно, конечно,
ввести дополнительную проверку на ноль, но это увеличит длину
программы.

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

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

Перейдем к умножению произвольных чисел. Как делать это
быстро?
В [4] приводится процедура умножения двух 8-битных чисел "в
столбик" - почти такая же, как описанная в [1], но все циклы в
ней раскрыты. За счет этого получается порядочный выигрыш в
быстродействии - процедура выполняется за 218-275 тактов при
длине 43 байта.
А еще быстрее? Первое, что приходит на ум - использовать
таблицу умножения. Правда, получается она что-то уж слишком
большой: когда оба сомножителя 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) ;прочитали старший байт произведения


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_5 .T ══════════════════


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

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

(log x + log y)
xy = A

Для перемножения 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/2 [(x+y)^2 - x^2 - y^2]

или

xy = 1/4 [(x+y)^2 - (x-y)^2]

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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_6 .T ══════════════════


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

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 (HL) ;CY сбрасывается

RRCA
RR E ;в CY выдвинулся 0!
RRCA
RR E
LD D,A ;DE=x*y
RET

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

Из приведенных выше формул видно, что для умножения чисел
разрядностью n необходима таблица квадратов, содержащая 2^n
значений, каждое из которых занимает n/4 байт. Для 8-разрядных
чисел размер таблицы равен 512 байт, а для 16-разрядных - уже
65536*4=262144 байта! Такая таблица, очевидно, в памяти не
уместится. Как же быть? В этом случае можно представить
произведение чисел разрядностью n в виде суммы произведений
чисел разрядности n/2. Пусть нам надо перемножить два
16-разрядных числа x и y. Разобьем их на части: x1 - старшая
часть x, x2 - младшая; y1 и y2 - аналогично. Получим:

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

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

Формирование таблицы квадратов чисел от 0 до 255, необходи-
мой для умножения, - отдельный интересный вопрос. Можно заранее
посчитать таблицу на Бейсике и включить ее в программу, но это
очень неэкономно. Гораздо выгоднее создать таблицу непосред-
ственно на ассемблере. При этом следует стремиться к тому, чтобы
процедура ее создания была как можно короче. Время ее работы не
так важно, ведь обычно она вызывается лишь один раз за все время
работы программы (кстати, тогда вовсе не обязательно оформлять
отдельную процедуру и вызывать ее с помощью CALL - выгоднее
непосредственно вставить ее в текст программы, сэкономив на этом
четыре байта).
При создании таблицы используется следующее свойство:
квадрат числа n равен сумме n последовательно взятых нечетных
чисел: так, например, 4^2 = 1+3+5+7 = 16. Таким образом,
прибавляя очередное нечетное число, мы получим очередное
значение квадрата.
В [9] приводится 16-байтный фрагмент программы, очень быстро
создающий таблицу квадратов, но при этом производятся манипуля-
ции со стеком, таблица получается перевернутой, а двухбайтные
значения квадратов размещаются в ней подряд, в то время как для
быстрого доступа к таблице необходимо, чтобы младшие байты
квадратов находились в первых 256 байтах таблицы, а старшие - в
следующих 256.
В [3] приведена занимающая 20 байт процедура, создающая как
раз такую таблицу, какую надо. Немного поразмыслив, я сократил
ее еще на два байта (а для 20-байтной процедуры два байта - это
много!). К тому же мой вариант процедуры, в отличие от
оригинального, не использует регистровую пару BC. Итак, вот:

XOR A
LD H,A
LD L,A
LD E,A
M1 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,M1
RET

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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_7 .T ══════════════════

Поговорим теперь еще об одном способе быстрого умножения,
описанном в [2]. Этот довольно экзотический способ основан на
специальной форме представления чисел - записи в остатках.
Пусть нам надо производить вычисления с числами в диапазоне
от 0 до N-1. Выберем несколько взаимно простых чисел s1, s2,...,
sm с таким расчетом, чтобы их произведение было не меньше N:

s1*s2*...*sm >= N.

Тогда каждое число можно однозначно записать остатками от
деления на s1, s2,..., sm. Рассмотрим это на примере: пусть
N=30, а в качестве взаимно простых чисел s1, s2,... выбраны 2, 3
и 5 (при этом условие s1*s2*s3>=N, как видим, выполняется).
Запись всех 30 чисел в остатках от деления на 2, 3 и 5
приведена ниже. Первая цифра в записи - остаток от деления на 5,
вторая - на 3, третья - на 2 (впрочем, можно было бы выбрать и
любой другой порядок записи).

┌───────┬───────────────────╥───────┬───────────────────┐
│ Число │ Запись в остатках ║ Число │ Запись в остатках │
├───────┼───────────────────╫───────┼───────────────────┤
│ 0 │ 000 ║ 15 │ 001 │
│ 1 │ 111 ║ 16 │ 110 │
│ 2 │ 220 ║ 17 │ 221 │
│ 3 │ 301 ║ 18 │ 300 │
│ 4 │ 410 ║ 19 │ 411 │
│ 5 │ 021 ║ 20 │ 020 │
│ 6 │ 100 ║ 21 │ 101 │
│ 7 │ 211 ║ 22 │ 210 │
│ 8 │ 320 ║ 23 │ 321 │
│ 9 │ 401 ║ 24 │ 400 │
│ 10 │ 010 ║ 25 │ 011 │
│ 11 │ 121 ║ 26 │ 120 │
│ 12 │ 200 ║ 27 │ 201 │
│ 13 │ 311 ║ 28 │ 310 │
│ 14 │ 420 ║ 29 │ 421 │
└───────┴───────────────────╨───────┴───────────────────┘

Важное достоинство такого способа представления чисел
состоит в том, что сложение, вычитание и умножение оказываются
простыми поразрядными операциями. Чтобы сложить (вычесть,
умножить) два числа, достаточно сложить (вычесть, умножить)
значения в каждом из разрядов по модулю этого разряда. Пусть
нам, например, надо умножить 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 находятся
значения (x*y) mod 11; с адреса, большего еще на 256 байт,
располагается аналогичная таблица для умножения по модулю 13.


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_8 .T ══════════════════


Вход : 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-битного операнда на два команды
ротации или сдвига - вне конкуренции, то уже деление на четыре
может быть выполнено быстрее с помощью табличного способа.


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_9 .T ══════════════════


Рассмотрим теперь возможный вариант оптимизации для случая,
когда делимое располагается в регистровой паре. При делении на
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 такта

Чтобы найти остаток от деления на 2^n, достаточно оставить
командой AND младшие n битов делимого. Например, остаток от
деления аккумулятора на 8 (8=2^3) вычисляется командой 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.

┌────────────────┬─────────────────────┐
│ Мнемоника │ Машинные коды │
├────────────────┼─────────────────────┤
│ 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.


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_10 .T ══════════════════


Поговорим теперь о быстром делении аккумулятора на
константу, не являющуюся степенью двойки. Вот один из способов
такого деления, о котором я узнал из эхоконференции 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 тактов).

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

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

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

k = k [3(1-y*k ) + (y*k )^2]
i+1 i i i

k = k [6(4-y*k ) + (y*k )^2(4-y*k ) - 20]
i+1 i i i i

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

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

(log x - log y)
x/y = A

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

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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_11 .T ══════════════════


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

В [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=x^2 монотонно
возрастает при изменении аргумента от нуля до бесконечности, а
значит, таблица квадратов представляет собой упорядоченный по
возрастанию массив чисел.

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

Вход : 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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_12 .T ══════════════════


В [22] приведены процедуры извлечения корня из 16-битного
и 24-битного операндов без использования таблиц. Максимальное
время их работы - соответственно 470 и 1026 тактов (без учета
RET).
В [21] подробно описан очень быстрый способ извлечения
корня, основанный на следующей формуле: если x представить в
виде m*2^n (где n четно), то sqr(x)=sqr(m)*2^(n/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 - основание
логарифмов):

n -- (logx/n)
/x = A

Теперь несколько слов о возведении в степень. Если степень
целая, то можно воспользоваться сведениями, взятыми из [8]. Там
описаны два способа возведения в степень: первый основан на
последовательном умножении (например, x^4=x*x*x*x), а второй,
более быстрый, использует разложение показателя степени на
множители, кратные двум (например, x^5=((x^2)^2)*x). Там же
можно найти и тексты соответствующих процедур.
Если степень не целая, удобной окажется следующая формула
(опять-таки с использованием логарифмов):

n (logx*n)
x = A

Если скорость вычислений по этой формуле покажется вам
недостаточной, можно использовать таблицу с уже вычисленными
заранее значениями x^n для всех возможных 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 (и
это вместо использования громоздких формул приведения - оцените
удобство!).


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_13 .T ══════════════════

Когда стоит задача уменьшения размера программы (например,
при написании 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, легко получается путем симметричного
отражения. Параболическая интерполяция и используется при
создании таблицы.

┌────────────────────────────┐
│ Здесь должна быть картинка │
│ из файла 'pic_1.scr' │
│ │
│ │
│ │
│ │
│ │
│ │
└────────────────────────────┘

Рис. 1

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

┌────────────────────────────┐
│ Здесь должна быть картинка │
│ из файла 'pic_2.scr' │
│ │
│ │
│ │
│ │
│ │
│ │
└────────────────────────────┘

Рис. 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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_14 .T ══════════════════


А если вставить эту процедуру в программу непосредственно,
без 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, точками - генерируемые приближенные
значения (соответственно масштабированные). Как видите, сходство
весьма велико!

┌────────────────────────────┐
│ Здесь должна быть картинка │
│ из файла 'pic_3.scr' │
│ │
│ │
│ │
│ │
│ │
│ │
└────────────────────────────┘

Рис. 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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_15 .T ══════════════════


А теперь - несколько возможностей дальнейшей оптимизации
этой процедуры.
Если перед ее выполнением оказывается, что в регистровой
паре 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 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 и
обратно, выделение целой части, вычисление синуса и косинуса,
возведение в квадрат.


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

В [11] приведена процедура быстрой печати 32-битных целых
чисел в десятичном виде (ее написал в 1983 году Тим Патерсон из
Microsoft). В [12] вы можете найти используемую при вводе таких
чисел с клавиатуры процедуру преобразования из ASCII-кодов.
Полезная библиотека процедур для печати чисел в различных
системах счисления приводится в [18].
Для ввода/вывода чисел (в том числе вещественных) можно
использовать и процедуры ПЗУ. Об этом рассказывается, например,
в [17].
В эхоконференции ZX.SPECTRUM мне попалось интересное
сообщение (его автор - Ilya Aniskovets), в котором описывается
фрагмент программы, преобразующий шестнадцатеричную цифру
(0,1,...,F) в соответствующий ASCII-код. Этот фрагмент настолько
оригинален и мал, что я не смог удержаться, чтобы не поместить
его здесь. Попробуйте на досуге разобраться, за счет чего он
работает.

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

CP #0A
SBC A,#69
DAA


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_16 .T ══════════════════


В девятом номере электронного журнала "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, то
выводим "файла". Не так уж сложно, не правда ли?


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_17 .T ══════════════════


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

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


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

Здесь вы найдете список использованных мной источников с
кратким описанием их содержания. В основном это различные
статьи, опубликованные в спектрумовских электронных газетах и
журналах. Их можно попробовать найти в Интернете на любом
крупном спектрумовском сайте - www.zx.ru, zx.da.ru (в разделе
"press"), www.chaosite.com. Посмотреть их на PC можно с помощью
какого-либо эмулятора, который можно найти там же.
Также рекомендую к изучению DEMO.DESIGN FAQ OnLine,
размещенный в Интернете по адресу http://www.enlight.ru/demo/
faq. Там имеется раздел "Математика" с описаниями различных
алгоритмов.
Ну а если вас интересуют наиболее оптимальные процедуры для
Z80, возможно, полезной окажется следующая информация:
Faster^TNL объявил о создании сайта "High Technologies"
(предположительный адрес http://HighTech.da.ru), где будут,
среди прочего, размещены исходные тексты различных процедур,
оптимизированные по длине и быстродействию.

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

1. В.Ильичев. "Программирование арифметических операций на
ассемблере". "Радиолюбитель. Ваш компьютер" 6-9/2000.

2. М.А.Карцев. "Арифметика цифровых машин". Москва, изд-во
"Наука", 1969.

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

3. Card!nal/PGC/BD. "Кодить хочу!". DEJA VU #5.

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

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

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

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

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


════════════════════════════════════════════════

С уважением, Иван Рощин.

Hello, All!

═══════════════════ part_18 .T ══════════════════


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

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

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

Деление 8/8->8+8 (частное и остаток); 8/8->8,8 (целая
часть, дробная часть); 24/24->24. Умножение 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=log2(x),
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.

Быстрая процедура извлечения квадратного корня sqr(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.

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

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.

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

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

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


════════════════════════════════════════════════

С уважением, Иван Рощин.