Jak zaimplementować efektywną procedurę dzielenia dwubajtowego w ASM dla 51 z liczby 28125?

Sun Mar 28, 2004 12:48 am   

Znalazlem metode ruskiego chlopa
http://csweb.bd.psu.edu/CLB/Research/MAA_s2003.PDF
ale na koncu algorytmu z przedostatniej strony jest
q=q+1
co mnie calkowicie nie urzadza gdyz rownie dobrze moge sobie dodawac
dzielnik do siebie, liczyc ilosc dodawan i czekac az zrowna sie z liczba
dzielona albo ja przekroczy.
Widzialem tez metode egipska
http://mathforum.org/library/drmath/view/57574.html
ale jakos nie moge tego rozgryzc coby do asm zaadoptowac.
Przyklady z EP sa nieczytelne jak dla mnie.
Kwestia jest taka ze im wieksza liczba wyniku (mniejszy dzielnik) tym
mniej czasu proca mam na obliczenia.
Liczba ktora trzeba dzielic jest zawsze stala i wynosi 28125
Ma ktos gotowca? najlepiej z komentarzami?

Sun Mar 28, 2004 1:33 am   

"AlexY" <alexy@irc.-cut_this-.pl> wrote in message news:c44b9u$ai1$1@atlantis.news.tpi.pl...

A nie myslales o zastosowaniu szybszego proca?
Szybkie kostki sa dzisiaj tansze niz czas spedzony na "myslenie".

Sun Mar 28, 2004 2:55 am   

Użytkownik Pszemol napisał:
[...]

Nie zebym byl niewdzieczny ale pytalem o 51...
Potrzebuje cos (konkretnie predkosciomierz i licznik km do samochodu bo
sie zebatki popsuly) w miare szybko zrobic a do tego proca mam wszystko
i znam go dosyc dobrze, nie mam czasu, checi, osprzetu ani potrzeby
przesiadac sie na inny (przynajmniej na razie).

howgh!

Sun Mar 28, 2004 3:10 am   

Uzytkownik "AlexY" <alexy@irc.-cut_this-.pl> napisal w wiadomosci
news:c44b9u$ai1$1@atlantis.news.tpi.pl...

Rozumiem, ze wynik ma byc calkowitoliczbowy?
Jesli jest stala to moze zrób tablice z wynikami?
Oczywiscie jakos sprytnie, coby zbyt duza nie wyszla ;)

pozdrawiam
Alek

Sun Mar 28, 2004 5:21 am   

Użytkownik Alek napisał:


tak zakres uzyteczny 1-170, zero wykrywam inaczej


to jest mysl... wprawdzie na wstepie ten pomysl odrzucilem ze wzgledu na
zajecie ROM'u ale to tak tragicznie nie bedzie (3*~170B), tyle ze
procedura wyboru elementu z tablicy zajelaby tyle cykli co dodawanie,
ale jest plus , mozna sprawdzac od gory tablicy (najwieksze wyniki)
czyli wtedy kiedy mam najmniej wolnych cykli.

Sun Mar 28, 2004 6:42 am   

"AlexY" <alexy@irc.-cut_this-.pl> wrote in message news:c44ir1$nt4$1@nemesis.news.tpi.pl...

Słyszałem - głuchy nie jestem - 51-ka występuje obecnie
w tysiącach różnych odmian i kształtów - są wersje klonów
pracujące z zegarami idącymi w dziesiątki megabajtów...


No to powodzenia...

Sun Mar 28, 2004 5:09 pm   

Użytkownik "AlexY" <alexy@irc.-cut_this-.pl> napisał w wiadomości
news:c46hu3$g0v$1@atlantis.news.tpi.pl...

czemu nieliniowe?


Przyznam się, że tabelki nie zrozumiałem :(



To o czym mówiłem:
masz 2 tabele wielkość 333 pozycji (2B każda pozycja) (dla dzielenia
całego zakresu ):
A - przedziały wartości przez którą dzielisz, a wynik masz taki sam
(upożądkowane rosnąco)
B - wynik dzielenia dla przedziału A(i) - A(i-1)

Na przykładzie (dla 15)
tabela A:
indeks: 1 2 3 4 5 6
wartość: 1 2 3 4 6 8
tabela B
indeks: 1 2 3 4 5 6
wartość: 15 7 5 3 2 1
przykład obliczenia:
dzielimy przez d= 5:
krok 1: szukamy w A takiego indeksu i (przesunięcie w pamięci), aby
A[i] <= d, oraz A[i+1] > d
(to możemy wykonać szybciej niż liniwo (logarytmicznie))
krok 2: wynik dzielenia to B[i]

pozdrawiam
Alek

Sun Mar 28, 2004 6:09 pm   

się wielu tego typu "rozterek" i zamiast wyważać otwarte już dawno drzwi
masz czas żeby zająć się meritum sprawy.

pzdr
kb

Sun Mar 28, 2004 6:16 pm   

Użytkownik "AlexY" <alexy@irc.-cut_this-.pl> napisał w wiadomości
news:c44rb5$36p$1@atlantis.news.tpi.pl...

czemu 3*?



???? tego nie rozumiem, chcesz przeszukiwać tablicę element po
elemencie???


Jak znajdę chwilę to może opiszę jak bym to widział z wynikami w
tablicy.

pozdrawiam
Alek

Sun Mar 28, 2004 7:08 pm   

AlexY wrote:


Gotowca nie podeślę ale rzucę dwa pomysły.
1. Jeśli masz dzielić przez stałą to zamiast tego możesz mnożyć przez
stałą np przez 3556 i potem przesuwać przecinek.
2. Jeśli 1. jest dla ciebie mało ambitne proponuję zrealizowaną
przezemnie metodę przybliżonego dzielenia liczb 32 bitowych mając
arytmetykę 16 bitową w 80c537. Definiujesz mnożenie 32 bitowe -
trywialne, następnie tworzysz funkcje do generowania kolejnych poteg
liczb 32 bit. Liczbę będącą dzielnikiem rozkładasz na 16 bitowe
przybliżenie i resztę będącą "odchyleniem". Rozkładasz funkcję 1/X na
szereg Taylora w pobliżu wartości przybliżonej. Szeregiem wyliczasz
poprawki do przybliżonego 16 bitowego ilorazu, sprawdzasz zbieżność albo
ucinasz na zadanym stopniu. Pewnie algorytm nie jest najprostszy ale
zastosowałem go bo i tak stosowałem szereg do liczenia logarytmów. Kod
pisany w assemblerze zajmował eprom 27128 a wyliczal sie chyba ok 6 ms
(wyliczanie logarytmu i ilorazu i trochę innych drobiazgów)

--
Pozdrawiam
MD

Sun Mar 28, 2004 7:14 pm   

Mariusz Dybiec wrote:

nieaktualne :)


--
Pozdrawiam
MD

Sun Mar 28, 2004 8:31 pm   

Użytkownik Krzysztof Bąk napisał:


Zeby nie rozpoczynac dyskusji advocacy stwierdze krotko:
od zawsze (12 lat z przerwami) pisze w asm i tego sie bede trzymal,
jesli nie jestes w stanie mi pomoc to prosze cobys sie w tej dyskusji
nie udzielal poniewaz nic konstruktywnego nie wnosisz.

Sun Mar 28, 2004 8:37 pm   

Jacek R. Radzikowski wrote:

czyli w arytmetyce dziesiętnej . A tak masz rację wyszło bez sensu. Tym
bardziej, że źle przeczytałem.

--
Pozdrawiam
MD

Sun Mar 28, 2004 8:53 pm   

Użytkownik Alek napisał:


raczej tak, szukanie bedzie po tablicy dwubajtowej ktorej wartosci beda
nieliniowe, watpie czy uda sie usyskac efektyny algorytm uwzgledniajacy
nieliniowosc, prosciej i szybciej bedzie z dodawaniem


Dopowiem co juz napisalem, jest to podprogram do predkosciomierza
timer T0 liczy ilosc cykli maszynowych na dystansie 1m , w dodatkowym
bajcie licze przepelnienia timera gdyz przy predkosci 1km/h musi on
policzyc do 3600000 co wymaga 3 bajtow, i teraz nalezaloby podzielic
wartosc 3600000 przez ilosc zliczonych cykli (sa to mikrosekundy przy
zegarze 12MHz) i wychodzi przedkosc w km/h. Dla uproszczenia obie liczby
dzielimy 7 razy przez 2 zwyczajnie przesowajac bity w prawo. W efekcie
dzielimy stala 28125 przez ilosc us z przesunietymi bitami.
kawalek tablicy :
1km/h = 3600000us/m 1101101110111010000000
2km/h = 1800000us/m 110110111011101000000
3km/h = 1200000us/m 100100100111110000000
4km/h = 900000us/m 11011011101110100000
120km/h = 30000us/m 111010100110000
168km/h = 21428us/m 101001110110100
169km/h = 21301us/h 101001100110101
170km/h = 21176us/m 101001010111000

jak widac im wieksza przedkosc tym mniej wazne bity sa wazne

Nadal staram sie rozgryzc dzielenie egipskie...

Sun Mar 28, 2004 10:07 pm   

Mariusz Dybiec <mardyb@poczta.onet.pl> wrote:

A skad wziales te stala ?
A jesli juz mnozyc to przez odwrotnosc. Tylko ze nie korzystac ze
zmiennego/stalego przecinka, a policzyc odwrotnosc modulo 65536 i
mnozyc tez modulo 65536. Mnozenie modulo bedzie banalne, bo wystarczy
obciac bity nadmiarowe.
Odwrotnosc policzysz rozszerzonym algorytmem euklidesa (do liczenia
odwrotnosci multiplikatywnych).
Jesli nie znasz algorytmu, zernknij na
http://ece.gmu.edu/courses/ECE543/viewgraphs_F03/lecture5_math_3.pdf albo
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm, ewentualnie do
dowolnej ksiazki wyjasniajacej podstawy arytmetyki modulo

pzdr.
j.