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

Hello, All!

═══════════════════ mult .t ══════════════════

(c) Иван Рощин, Москва

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

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

В [1], рассматривая различные способы быстрого умножения
целых чисел, я приводил две формулы, взятые из [2]:

1 2 2 2
xy = ─ ((x+y) - x - y ), (1)
2

1 2 2
xy = ─ ((x+y) - (x-y) ). (2)
4

Далее я утверждал: "Чтобы избавиться от деления на 2 в
первой формуле и от деления на 4 во второй, достаточно хранить
в таблице квадратов уже поделенные на 2 или на 4 значения.
Умножение будет выполняться быстрее, но станет неточным,
особенно при малых значениях сомножителей". Иначе говоря,
имелось в виду следующее:

┌ 2┐ ┌ 2┐ ┌ 2┐
│(x+y) │ │ x │ │ y │
xy ~= │───── │ - │ ─ │ - │ ─ │, (3)
└ 2 ┘ └ 2 ┘ └ 2 ┘

┌ 2┐ ┌ 2┐
│(x+y) │ │(x-y) │
xy ~= │───── │ - │───── │. (4)
└ 4 ┘ └ 4 ┘

Из чего следовали мои выводы о неточности умножения по этим
формулам? Так как при хранении в таблице уже поделенных на 2
(или 4) значений (т.е. целых частей этих значений) происходит
потеря точности, логично предположить, что вычисления будут
происходить с погрешностью. Так как абсолютный размер
погрешности ограничен, при умножении больших значений
относительная погрешность будет невелика, а при уменьшении
сомножителей она будет увеличиваться.
Вроде бы всё очевидно, да? Мне тоже так казалось. :-) В
действительности даже очевидные на первый взгляд утверждения
нуждаются в тщательной проверке.
Просматривая [3], я обнаружил формулу, эквивалентную
следующей:

┌ 2┐ ┌ 2┐
│(x+y) │ │(x-y) │
xy = │───── │ - │───── │. (5)
└ 4 ┘ └ 4 ┘

Это то же самое, что и формула (4), только равенство
оказалось не приближённым (как я считал), а точным. Почему?
В [3] утверждается, что дробные части (x+y)^2/4 и (x-y)^2/4
равны. Действительно, произведение целых чисел x и y - также
целое число, а разность двух чисел (x+y)^2/4 и (x-y)^2/4 может
быть целой, только когда их дробные части равны. Таким образом,
отбрасывание дробных частей в данном случае не влияет на
получаемый результат, и умножение по формуле (5) действительно
будет точным.
Кстати, в [3] также упоминается, что эта формула вместе с
таблицей значений функции [z^2/4] при натуральных значениях z
использовалась для облегчения умножения многозначных чисел ещё
до изобретения таблиц логарифмов.

Может быть, и формула (3) обеспечивает точное умножение?
Проверим это. Так как x и y могут быть чётными или нечётными,
возможны четыре различных случая.
1. x чётно, y чётно. Тогда (x+y)^2, x^2, y^2 будут чётными,
и дробные части всех трёх выражений в скобках будут равны 0.
2. x чётно, y нечётно. Тогда x+y нечётно, (x+y)^2 также
нечётно (дробная часть (x+y)^2/2 равна 1/2). x^2 чётно (дробная
часть x^2/2 равна 0), y^2 нечётно (дробная часть y^2/2 равна
1/2). В результате после вычитания дробные части взаимно
уничтожатся, а значит, от их отбрасывания результат не
изменится.
3. x нечётно, y чётно - ситуация аналогична предыдущей, т.к.
формула симметрична относительно x и y.
4. x нечётно, y нечётно. Тогда x+y чётно, (x+y)^2 также
чётно (дробная часть (x+y)^2/2 равна 0), а x^2 и y^2 - нет
(дробные части x^2/2 и y^2/2 равны 1/2). Следовательно, при
отбрасывании дробных частей результат окажется на 1 больше
истинного.
Как видим, умножение по формуле (3) действительно является
неточным - в том случае, когда оба сомножителя нечётны.

С теоретическими вопросами разобрались. :-) Перейдём теперь
к практическому использованию формулы (5). В [1] я приводил
основанную на формуле (2) процедуру умножения двух целых
8-битных чисел с ограничением "сумма сомножителей не превосходит
255". Когда в таблице квадратов хранятся уже поделенные на 4
значения, из этой процедуры надо убрать команды деления
результата на 4. Соответственно, получим следующее:

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

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)
LD D,A ;DE=x*y

RET

Теперь умножение выполняется на 24 такта (~20%) быстрее по
сравнению с исходным вариантом процедуры.

Hиже приведён текст процедуры построения таблицы квадратов,
делённых на 4. При её написании я взял за основу приведённую в
[1] процедуру построения таблицы квадратов (которая, в свою
очередь, является результатом оптимизации процедуры, приведённой
в [4]).

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
SRL (HL)
RRA
SRL (HL)
RRA
DEC H
LD (HL),A
EX DE,HL
LD D,0
ADD HL,DE
INC E
ADD HL,DE ;Hа флаг Z не влияет.
JR NZ,M2

RET


Литература
──────────

1. И.Рощин. "Ещё о программировании арифметических операций".
"Радиолюбитель. Ваш компьютер" 12/2000, 1-4/2001.

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

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

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

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

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