🚀 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=7=111b, 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=7=111b, 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...