Умножение через сложение

← →
Servy © (2008-09-12 03:49) [0]

Есть некий микроконтроллер, который не умеет умножать. Зато он умеет складывать, вычитать, and, or, xor, not, shl, shr и много других полезных вещей. Вопрос: как реализовать на нем умножение наилучшим образом. Под наилучшим понимается относительно быстрый, но не слишком длинный (памяти команд у него всего на 2k оных, зря их тратить не хотелось бы).

Пока мне придумался такой алгоритм:

function Mul(X, Y: Integer): Integer; var Add: Integer; begin Add := 0; Result := 0; if (X = 0) then Exit; while (X > 1) do begin if (X and 1 > 0) then Add := Add + Y; X := X shr 1; Y := Y shl 1; end; Result := Y + Add; end;

Если у кого-нибудь есть идеи как сделать короче/быстрее, буду рад их услышать. Кстати, лобовой метод через сложение Y"ков X раз записывается вроде как короче, правда выполняться может на порядок дольше.

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

PS. В гугле искал, но ничего путнего не нашлось :(.

← →
brother © (2008-09-12 04:14) [1]

умножение через сложение?
function Umn(a,b:integer):integer;
var tmp:iteger;
begin
result:=0;
if (a=0) or (b=0) then exit;

for tmp:=1 to b do
result:=result+a;
end;

как то так?

← →
brother © (2008-09-12 04:17) [2]

> Кстати, лобовой метод через сложение Y"ков X раз записывается
> вроде как короче, правда выполняться может на порядок дольше.

не пароверял...
зы а разве проги под микроконтроллеры не на асм пишут?

← →
X9 © (2008-09-12 07:05) [3]

> [2] brother © (12.09.08 04:17)
> зы а разве проги под микроконтроллеры не на асм пишут?

Ещё и на C. Но не на Pascal :)

← →
KilkennyCat © (2008-09-12 08:29) [4]

На паскале тоже.

← →
Рамиль © (2008-09-12 09:03) [5]

> Servy © (12.09.08 03:49)

Думаешь ты единственный, кто озаботился умножением и делением на RISC микроконтроллере? Раз не нашел, значит не так искал:) Найди для PIC ов, лучше на ASM если места жалко, должно работать (может переделки понадобятся).

← →
Рамиль © (2008-09-12 09:06) [6]

Вот, например
http://www.kazus.ru/nuke/files/arifm.asm

← →
palva © (2008-09-12 09:07) [7]

Можно записать экономней. Кроме того, алгоритм работает для беззнакового X. Поэтому либо нужно включать дополнительный анализ либо не использовать тип Integer.
function Mul(X, Y: Cardinal): Cardinal; begin Result := 0; while X > 0 do begin if odd(X) then Result := Result + Y; X := X shr 1; Y := Y shl 1; end; end;

← →
Jeer © (2008-09-12 10:01) [8]

Пример 16 разрядного знакового умножения с фиксированной точкой на asm i8080
(Циклы развернуты в целях повышения скорости вычислений)

PUBLIC FMULT

FMULT: LXI H,0
MOV A,D
MOV D,L
ADD A
JNC MA
DAD B
ADC D
MA: DAD H
ADC A
JNC MB
DAD B
ADC D
MB: DAD H
ADC A
JNC MC
DAD B
ADC D
MC: DAD H
ADC A
JNC MD
DAD B
ADC D
MD: DAD H
ADC A
JNC ME
DAD B
ADC D
ME: DAD H
ADC A
JNC MF
DAD B
ADC D
MF: DAD H
ADC A
JNC MG
DAD B
ADC D
MG: DAD H
ADC A
JNC MH
DAD B
ADC D
MH: MOV D,A
MOV A,E
MVI E,0
RAR
PUSH PSW
ADD A
DAD H
ADC A
JNC MI
DAD B
ADC E
MI: DAD H
ADC A
JNC MJ
DAD B
ADC E
MJ: DAD H
ADC A
JNC MK
DAD B
ADC E
MK: DAD H
ADC A
JNC ML
DAD B
ADC E
ML: DAD H
ADC A
JNC MM
DAD B
ADC E
MM: DAD H
ADC A
JNC MN
DAD B
ADC E
MN: DAD H
ADC A
JNC MO
DAD B
ADC E
MO: DAD H
ADC A
JNC MP
INR D
MP: MOV E,A
POP PSW
RNC
DAD B
RNC
INX D
RET
END

PUBLIC MULTS
EXTRN FMULT

MULTS: PUSH B
PUSH PSW
LDAX D
MOV C,A
INX D
LDAX D
MOV B,A
MOV E,C
MOV D,B
MOV C,M
INX H
MOV B,M
MOV L,C
MOV H,B
MOV A,H
XRA D
RAL
PUSH PSW
MOV A,D
RAL
JNC PA
MOV A,E
CMA
ACI 0
MOV E,A
MOV A,D
CMA
ACI 0
MOV D,A
PA: MOV A,H
RAL
JNC PB
MOV A,C
CMA
ACI 0
MOV C,A
MOV A,B
CMA
ACI 0
MOV B,A
PB: CALL FMULT
XRA A
MOV A,L
RAL
MOV C,A
MOV A,H
RAL
MOV B,A
MOV A,E
RAL
MOV E,A
MOV A,D
RAL
MOV D,A
POP PSW
JNC PC
MOV A,C
CMA
ACI 0
MOV C,A
MOV A,B
CMA
ACI 0
MOV B,A
MOV A,E
CMA
ACI 0
MOV E,A
MOV A,D
CMA
ACI 0
MOV D,A
PC: POP PSW
CPI 2
POP H
JZ W
MOV M,C
INX H
MOV M,B
INX H
W: MOV M,E
INX H
MOV M,D
MOV A,D
ORA A
RET
END

← →
iZEN (2008-09-12 10:27) [9]

Используйте побитовый сдвиг.

← →
Правильный$Вася (2008-09-12 10:58) [10]

> Умножение через сложение

тебе только целые? и целое кол-во раз?
а как с отрицательными X,Y ?

А просто взять томик Кнута и посмотреть там?!

> зы а разве проги под микроконтроллеры не на асм пишут?

Проги-то на асм, а вот алгоритм на делфевом форуме я на асме излагать постеснялся :).

> Кроме того, алгоритм работает для беззнакового X

Да, я думал об этом, спасибо что напомнили. Видимо, умножение стоит производить без старшего бита, а старший бит определять как sign1 xor sign2.

> А просто взять томик Кнута и посмотреть там?!

Видимо, у этого томика по запросам ala "умножение" низковата релевантность :). Спасибо за пинок, посмотрю.

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

PS. Если еще кто-нибудь выскажется по поводу деления, буду вообще счастлив. Хотя, дяденька Кнут наверно и об этом подумал.

> Servy © (12.09.08 12:05) [13]

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

Деление на константу можно заменить умножением на другую константу-"магическое число". Напр вот здесь:

http://www.wasm.ru/forum/viewtopic.php?id=28039

можно об этом почитать.
Однако, не думаю что это применимо в общем случае, слишком громоздкими выйдут таблицы МЧ.

Умножение через сложение Найти похожие ветки