Algorytmy dzielenia.

Cześć,
mam zadanie projektowe na temat algorytmów dzielenia. Potrzebuję pomocy w poszukiwaniu jakiś źródeł wiedzy, książek, artykułów i innych na ten temat.
Główne pytania na jakie muszę odpowiedzieć to:

1. Napisać algorytm dzielenia, gdy dzielnik jest długości słowa maszynowego.
2. Jak algorytm się zmieni, gdy dzielnik będzie 2 razy dłuższy?
3. Czy warto zrobić dzielenie numeryczne? (tutaj mam duży problem ze znalezieniem jakiś sensownych tekstów na ten temat)
4. W jaki sposób ocenić dokładność obliczenia?

Głównie chodzi mi o pomoc w odpowiedzi na pytania 2, 3, 4.
Czy ktoś jest w stanie mi coś podpowiedzieć? Podać może jakieś hasła co najlepiej poczytać, na co zwrócić uwagę itd.
Może ktoś ma wiedzę na ten temat i zechciałby coś powiedzieć z głowy/własnego doświadczenia? Każda pomoc mile widziana.

Z góry dziękuję za każdą pomoc.
Pozdrawiam.

Jakie dzielenie: całkowite czy na floatach?

A to i tak chyba na to samo wyjdzie... wystarczy potraktować całkowitą jako ułamek <0, 1).

a/b, i obliczasz 1/b, a potem mnożysz przez a.

1/b można obliczyć dość szybko za pomocą metody Newtona, ale można szybciej - jakoś tak:

b = 1-x

zatem teraz mamy:
1/b = 1/(1-x) = 1 + x + x² + x³ + ...

ale taki szereg można obliczać znacznie szybciej:
s = (1+x)
s = s(1+x²) = 1 + x + x^{2 + x}3
s = s(1+x⁴) = 1 + x + x^{2 + x}3 + ... x^7
...

jak widać to się podwaja przy każdym mnożeniu, czyli rakieta.

Np.: b = 0.2, czyli x = 0.8, i wynik 1/b = 5;

s = 1 + 0.8 = 1.8
s = 1.8 * (1+0.8²) = 2.952
s = 2.952 * (1+0.8⁴) = 4.1611392
s = 4.1611392 * (1+0.8⁸) = 4.859262511644672
s = 4.859262511644672 * (1+0.8¹⁶) = 4.9960385918742867831203228024832
s = 4.9960385918742867831203228024832 * (1+0.8³²) = 4.9999968614491323066596180821053

i już aż 32 składniki tego szeregu posumowane...

2. Jak algorytm się zmieni, gdy dzielnik będzie 2 razy dłuższy?

W tym algorytmie dojedzie tylko 1 iteracja po podwojeniu precyzji.
Z tym że gdy przekroczy rozmiary rejestru, no to wtedy musisz zrobić swoje mnożenie - takie na tablicach z przenoszeniem...

3. Czy warto zrobić dzielenie numeryczne? (tutaj mam duży problem ze znalezieniem jakiś sensownych tekstów na ten temat)

A niby jakie jak nie numeryczne?
Obecne komputery nie obliczają już analogowo... chyba w latach 60-tych były takie.

4. W jaki sposób ocenić dokładność obliczenia?

Chyba taka jak długość argumentu: 2^-(n+1), zaokrąglając pół bita.
n = 32, błąd na poziomie 1e+9, czyli 9 cyfr dokładnych
n = 64 - 18 cyfr; itd.

Ogólnie implementacja tego będzie w assemblerze, prawdopodobnie dzielenia odtwarzające (restoring), albo nieodtwarzające (non-restoring)

Aha, przedpotopowe pierdoły... no to zapraszamy dział archeologi.

Tu są różne metody:
http://en.wikipedia.org/wiki/Division_algorithm

Można też stosować przyspieszyć tę metodę, stosując dodatkową tablicę, z której pobierasz od razu przybliżoną wartość startową, zamiast zaczynać od 1 bitu.

Np. jeśli masz 12 bitów na starcie, wtedy wystarczy wykonać jedną iterację i masz 24, czyli precyzja float.
Double ma 53 bity precyzji, zatem potrzeba trzy iteracje: 24 - 48 - 96, lekko przesadzone...
wystarczy 7 bitów i wtedy: 14 - 28 - 56.

Ale obecne komputer chyba dzielą i pierwiastkują, bo to jest dość podobny problem,
za pomocą interpolacji i tablic współczynników, bo tylko tak można zejść poniżej 20 taktów.

Podobnie sinus, i inne funkcje podstawowe, można szybko wyliczyć, ale nowe procesory chyba w ogóle tego nie robią:
w SSE czy AVX nie ma żadnych sin, tan, exp, arctg, itd.
Procesory marnują aż z 200 taktów na te funkcji.

fur napisał(a):

Można też stosować przyspieszyć tę metodę, stosując dodatkową tablicę, z której pobierasz od razu przybliżoną wartość startową, zamiast zaczynać od 1 bitu.

Np. jeśli masz 12 bitów na starcie, wtedy wystarczy wykonać jedną iterację i masz 24, czyli precyzja float.
Double ma 53 bity precyzji, zatem potrzeba trzy iteracje: 24 - 48 - 96, lekko przesadzone...
wystarczy 7 bitów i wtedy: 14 - 28 - 56.

Zdecydowałem się na implementację algorytmu Newtona - Raphsona i właśnie mam jeszcze pytanie co do wyznaczenia tej pierwszej wartości (początkowej). Jak wiadomo, jest ona bardzo istotna, gdyż może znacznie skrócić ilość iteracji (tak jak przedstawił to kolega fur). Czy znajdę gdzieś stablicowane te wartości początkowe (np. różne przedziały wartości i z nich wybieramy optymalną wartość)? Ewentualnie jak nigdzie nie znajdę tego zapisanego to jak takową wyznaczyć?

Pozdrawiam.