🚀 go-pugleaf

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.)

--
Pozdrawiam
Michoo

> Ztcw to jedyne co mo�esz zrobi� to rozbi� liczb� na 2 cz�ci:

po co wy mu to m�wicie, jak nie wie to niech si� nie rwie bo tylko
napsuje...
dla niego jedynie: A*A=A+...+A
albo lepiej niech spada na Politechnik� Warszawsk�...

identifikator: 20040501 pisze:
>> Ztcw to jedyne co mo�esz zrobi� to rozbi� liczb� na 2 cz�ci:
>
> po co wy mu to m�wicie, jak nie wie to niech si� nie rwie bo tylko
> napsuje...
Bez przesady - jak da rad� to sobie rozpisa� i wyci�gn�� wnioski to i
b�dzie w stanie zapisa� na wi�kszo�ci normalnych architektur.
> dla niego jedynie: A*A=A+...+A
Je�eli chce mie� wynik w 16 bitach to tak, je�eli chce mno�y� 16x16->32
to ~200 pot�gowa� na sekund� mo�e by� ciut ma�o...
> albo lepiej niech spada na Politechnik� Warszawsk�...
???
Poza tym z okolic Radlina ma raczej daleko.

--
Pozdrawiam
Michoo

W dniu 28.02.2010 22:59, 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).

 Witam.

 Mi przysz�o do g�owy takie co�:
1. ustaw wynik na zero
2. id�c bit po bicie w A: je�li bit numer n (licz�c od zera) jest
ustawiony, dodaj do wyniku A<<n.
3. wypychanie bit�w nie mieszcz�cych si� w rejestrach jest �atwe -
wysuni�ty bit wstawiasz jako najm�odszy do rejestru graj�cego rol�
"starszej cz�ci" w stosunku do bie��cego rejestru

 Oczywi�cie, nie musisz za ka�dym razem wylicza� A<<n, mo�esz wyniki
tymczasowe trzyma� sobie w zmiennej i tylko przesuwa� o tyle, ile
brakuje od ostatniego razu.
 A czy to b�dzie szybkie to nie mam poj�cia. Prawdopodobnie nie, ale
wszystko zale�y od szybko�ci instrukcji mno�enia, dodawania i
przesuwania bitowego (sprawdzanie bitu pomijam).

 Pobierz z http://webster.cs.usr.edu ksi��k� "Art of asembler" - tam
masz opisane mi�dzy innymi operacje wielokrotnej precyzji (gdy
argumenty dzia�a� nie mieszcz� si� w rejestrach). Opis cz�ci takich
algorytm�w znajdziesz te� na
http://rudy.mif.pg.gda.pl/~bogdro/dos/a_kurs14.htm

--
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.JabberPL.org www.TorProject.org Soft (EN): miniurl.pl/bogdro-soft

Bogdan (bogdro) pisze:
>  Mi przysz�o do g�owy takie co�:
> 1. ustaw wynik na zero
> 2. id�c bit po bicie w A: je�li bit numer n (licz�c od zera) jest
> ustawiony, dodaj do wyniku A<<n.
To spowoduje przepisanie A do wyniku. Przecie� liczba to w�a�nie suma po
n z (B_n * 2^n).

--
Pozdrawiam
Michoo

onegdaj ‟roxy” rzecze:
> 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).
na  przykład tablica składników sumy potęg 2 liczby podnoszonej do kwad-
ratu, które  umożliwią wykonanie tylko sumy operacji przesunięć bitowych
do uzyskania wyniku podniesienia do kwadratu:
( a << 2*i_1 ) + (a << 2*i_2 ) + …
o ile to przyspieszy; szczególnie wtedy, gdy coś jest stałe.
--
―oh yea, i got it!
―oh, stupid!
D. Icke

W dniu 03.03.2010 09:12, Michoo pisze:
> Bogdan (bogdro) pisze:
>>  Mi przysz�o do g�owy takie co�:
>> 1. ustaw wynik na zero
>> 2. id�c bit po bicie w A: je�li bit numer n (licz�c od zera) jest
>> ustawiony, dodaj do wyniku A<<n.
> To spowoduje przepisanie A do wyniku. Przecie� liczba to w�a�nie suma po
> n z (B_n * 2^n).

 Tak by si� sta�o, gdybym do wyniku dodawa� 1<<n, a dodaj� A<<n. Na
przyk�ad, je�li A=71b, to do wyniku b�d� kolejno (id�c od
najm�odszych bit�w w moim przypadku) dodawane: A<<0=A, A<<1=A*2 i
A<<2=A*4, czyli wynik = A + A*2 + A*4 = A*7 = A*A.

--
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.JabberPL.org www.TorProject.org Soft (EN): miniurl.pl/bogdro-soft

Bogdan (bogdro) pisze:
> W dniu 03.03.2010 09:12, Michoo pisze:
>> Bogdan (bogdro) pisze:
>>>  Mi przysz�o do g�owy takie co�:
>>> 1. ustaw wynik na zero
>>> 2. id�c bit po bicie w A: je�li bit numer n (licz�c od zera) jest
>>> ustawiony, dodaj do wyniku A<<n.
>> To spowoduje przepisanie A do wyniku. Przecie� liczba to w�a�nie suma po
>> n z (B_n * 2^n).
>
>  Tak by si� sta�o, gdybym do wyniku dodawa� 1<<n, a dodaj� A<<n. Na
> przyk�ad, je�li A=71b, to do wyniku b�d� kolejno (id�c od
> najm�odszych bit�w w moim przypadku) dodawane: A<<0=A, A<<1=A*2 i
> A<<2=A*4, czyli wynik = A + A*2 + A*4 = A*7 = A*A.
>
Racja, nie ma jak czytanie bezwzrokowe - widz� 'A', czytam '1' ;)


--
Pozdrawiam
Michoo

onegdaj ‟minięty czas” rzecze:
> onegdaj ‟roxy” rzecze:
>> 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).
> na  przykład tablica składników sumy potęg 2 liczby podnoszonej do kwad-
> ratu, które  umożliwią wykonanie tylko sumy operacji przesunięć bitowych
> do uzyskania wyniku podniesienia do kwadratu: ( a << 2*i_1 ) + (a <<
> 2*i_2 ) + …
> o ile to przyspieszy; szczególnie wtedy, gdy coś jest stałe.
pomieszałem dwa alternatywne wzory. oczywiście, że:
a * 2*i_1
lub
a << i_i
--
/ qo   |)    :@=N%_g=v=a=g_eD_e=c()=d=8! =%!gN@8'Re. w8in/ad
\    _x/ ,   ;h-%-a'hA'H4,X0'Xo~xo~xO,R`-%EXp01ITed: *-7/+eh
/    |    ng `-%__%--'__%--'__%--~__%--^%B`/$qV3r[o; &GooMee
L_._o_O_*_^_"_'_`_ -> http://thereis.notlong.com <- `L"EnOF"

> Pobierz z http://webster.cs.usr.edu ksi��k� "Art of asembler" - tam

powinno by�

http://webster.cs.ucr.edu



--
Azarien

W dniu 05.03.2010 21:04, Wiktor S. pisze:
>> Pobierz z http://webster.cs.usr.edu ksi��k� "Art of asembler" - tam
>
> powinno by�
>
> http://webster.cs.ucr.edu

 Oczywi�cie. Ach, te linuksowe przyzwyczajenia... :)

--
Pozdrawiam/Regards - Bogdan                     (GNU/Linux & FreeDOS)
Kurs asemblera x86 (DOS, GNU/Linux):http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
www.JabberPL.org www.TorProject.org Soft (EN): miniurl.pl/bogdro-soft

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)

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)

Politachnika Warszawska to najbardziej zpalancia�a uczelnia (chyba) na
�wiecie...