🚀 go-pugleaf

Michoo pisze:
> roxy pisze:
>> Witam
>> Czy ktos moze mi podac namiary na algorytm szybkiego mnozenia dwoch 
>> liczb 16bitowych.
>> Dokladnie chodzi o pomnozenie liczby A przez samą siebie czyli AxA 
>> (podnoszenie do potęgi 2).
>> Do dyspozycji mam mikrokontroler 8bit i mozliwosc wykonywania 
>> dodawania, odejmowania i mnozenie dwoch liczb 8 bit.
>> Moze jest jakas własciwośc podczas podnoszenia do kwadratu liczby 
>> ktorą mozna by wykorzystać i przyspieszyć znacząco obliczenia? (tak 
>> jak np podczas mnozenia liczby A x 4 to to samo co  a<<2 a znaczaco 
>> brzyspiesza działanie).
>>
> Ztcw to jedyne co możesz zrobić to rozbić liczbę na 2 części:
> X = (A*2^8 + B)
> X^2 = (A*2^8 + B)*(A*2^8 + B)
> rozpisać i poupraszczać - będą 4 mnożenia i dodawania.(O ile tylko ten 
> uC daje wynik mnożenia na 16 bitach a dodawania przynajmniej na 9.)
> 

Jeśli wynik mnożenia liczb 8-bitowyh jest 16-bitowy, to da się za pomocą
3 mnożeń i 4 do 10 dodawań. Niech

C := A*A
D := A*B
E := B*B

(C, D, E to 16-bitowe słowa, Lo() i Hi() to odpowiednio mniej i bardziej
znaczaca część słowa).


Powtarzamy 2 razy na stępujący fragment:

Hi(C) := Hi(C) + Lo(D), jeśli powstaje przeniesienie to Lo(E) := Lo(E) +
1 (jeśli procesor ma rozkaz inkrementacji to można go wykorzystać),
jeśli tym razem powstanie przeniesienie, to Hi(E) := Hi(E) + 1, i tu
przeniesienie nie ma prawa powstać

=========


Powtarzamy 2 razy:

Lo(E) := Lo(E) + Hi(D), gdy powstaje przeniesienie, to Hi(E) := hi(E)+1

=====================


Ostatecznie iloczyn tworzą bajty Hi(E), Lo(E), Hi(C), Lo(C) (w
kolejności od MSB do LSB)