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. ════════════════════════════════════════════════ С уважением, Иван Рощин.