🚀 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 2 do 5 dodawań. Niech

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

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


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ć

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)