algorytm pierwiastkowania

[Maciek]

Jak zaimplementowac algorytm pierwiastkowania (dowolnego stopnia)
na liczbach rzeczywistych?
Prosze uwzglednic fakt ze moja znajomosc matematyki jest na poziome
drugiej klasy liceum.
Pytanie jest raczej informatyczne, ale wydaje mi sie ze to najlepsza grupa
zeby je zadac. Jesli nie to prosze mnie odeslac do innej grupy.

Zalezy, jakimi mechanizmami dysponujesz.
Tzn. jakie dzialania elementarne mozesz wykonywac na liczbach,
w jakim formacie te liczby sa zapisane, czy w ogole
dostepne operacje elementarne zaleza od formatu
liczby, itd, itp.......


Jezeli masz do dyspozycji przynajmniej dzialania dodawaniia
i dzielenia, i zakladasz ze sa one dokladne, to najprostszy
algorytm wynika z zastosowania metody stycznych do rownania:

x^2 = X (X > 0)

Rozwiazaniem jest oczywiscie
x = sqrt( X )
a uzyskuje sie je zaczynajac np. od x=1,
i iterujac obliczenie:
x := (x + X/x) / 2


Maciek

[Radiac]

Post by Maciek
Rozwiazaniem jest oczywiscie
x = sqrt( X )
a uzyskuje sie je zaczynajac np. od x=1,
x := (x + X/x) / 2

Nie bardzo rozumiem. Biorac np. sqrt(5) zacynajc od x=1, otrzymuje 3. I co
dalej?

Poza tym wydaje mi sie ze zalozyles ze chodzi mi o pierwiastek kwadratowy, a
mi chdozi o pierwiastek dowolnego stopnia. Przy okazji dosc banalne pytanie:
czy pierwiastek moze byc stopnia rzeczywistego? Bo na wiem.onet.pl napisane
jest: "zazwyczaj b[stopien pierwistatka] jest liczbą naturalną" i nie
rozumiem co znaczy "zazwyczaj".

Jedyne co ja wymyslilem to podniesie x do n(stopien pierwiastka) i
porownanie wyniku z argumentem pierwiastka, a nastepnie odpowiednie
iterowanie x az do uzyskania rownosci. Jednak proces ten w zaleznosci od
argumentow moze byc niezmiernie czasochlonny i mnie nie satysfakcjonuje.
Mialem nadzieje ze moze instnieje jakis szereg (tak zrobilem funkcje
trygonometryczne) albo cos...?

Post by Maciek
Zalezy, jakimi mechanizmami dysponujesz.
Tzn. jakie dzialania elementarne mozesz wykonywac na liczbach,
w jakim formacie te liczby sa zapisane, czy w ogole
dostepne operacje elementarne zaleza od formatu
liczby, itd, itp.......

Coz, mam po prostu dokladne liczby rzeczywiste, takie jak pani uczy w
podstawowce. A dostepne dzialania to +-*/ i sa one wykonywane dokladnie.

[£ukasz Kalbarczyk]

Post by Radiac

Post by Maciek
Rozwiazaniem jest oczywiscie
x = sqrt( X )
a uzyskuje sie je zaczynajac np. od x=1,
x := (x + X/x) / 2

Nie bardzo rozumiem. Biorac np. sqrt(5) zacynajc od x=1, otrzymuje 3.
I co dalej?
Poza tym wydaje mi sie ze zalozyles ze chodzi mi o pierwiastek
kwadratowy, a mi chdozi o pierwiastek dowolnego stopnia. Przy okazji
dosc banalne pytanie: czy pierwiastek moze byc stopnia rzeczywistego?
Bo na wiem.onet.pl napisane jest: "zazwyczaj b[stopien pierwistatka]
jest liczbą naturalną" i nie rozumiem co znaczy "zazwyczaj".

Zazwyczaj - bo jeśli chodzi o pierwiastkowanie jako
odwrotność potęgowania, to zazwyczaj lepiej powiedzieć
x^(7/13) niż pierwiastek stopnia (13/7) z x, ale nie jest to błędem.

Post by Radiac
Jedyne co ja wymyslilem to podniesie x do n(stopien pierwiastka) i
porownanie wyniku z argumentem pierwiastka, a nastepnie odpowiednie
iterowanie x az do uzyskania rownosci. Jednak proces ten w zaleznosci
od argumentow moze byc niezmiernie czasochlonny i mnie nie
satysfakcjonuje. Mialem nadzieje ze moze instnieje jakis szereg (tak
zrobilem funkcje trygonometryczne) albo cos...?

Jest szereg...
Może wzór na (a+b)^r coś pomoże
z uogólnionymi dwumianami Newtona...

[Krzysztof Dulęba]

Post by £ukasz Kalbarczyk

Post by Radiac
Jedyne co ja wymyslilem to podniesie x do n(stopien pierwiastka) i
porownanie wyniku z argumentem pierwiastka, a nastepnie odpowiednie
iterowanie x az do uzyskania rownosci. Jednak proces ten w zaleznosci
od argumentow moze byc niezmiernie czasochlonny i mnie nie
satysfakcjonuje. Mialem nadzieje ze moze instnieje jakis szereg (tak
zrobilem funkcje trygonometryczne) albo cos...?

Jest szereg...
Może wzór na (a+b)^r coś pomoże
z uogólnionymi dwumianami Newtona...

Nabijasz się z chłopaka czy mówisz to serio?
Dobre rozwiązanie wskazał Maciek, do policzenia pierwiastka stopnia k
wystarczy je lekko zmodyfikować, pierwiastek stopnia wymiernego też liczy
się łatwo. Błąd maleje bardzo szybko, w przybliżeniu przy każdej iteracji
podwaja się ilość poprawnie wyliczonych cyfr (od pewnego momentu, na
początku może iść trochę wolniej).

Zamiast liczyć a^x, można znaleźć e^(x * ln (a)). Układy logarytmujące i
liczące funkcję wykładniczą są wbudowane w koprocesor matematyczny i
wywołanie funkcji logarytm jest zamieniane na instrukcję dla tego
koprocesora.

Pozdrawiam
Krzysztof Dulęba

[Radiac]

Post by Krzysztof Dulęba
Nabijasz się z chłopaka czy mówisz to serio?

Prosze sie ze mnie nie nabijac, jak juz mowielm matematyk ze mnie zaden (a
szkoda) :(

Post by Krzysztof Dulęba
Dobre rozwiązanie wskazał Maciek, do policzenia pierwiastka stopnia k
wystarczy je lekko zmodyfikować, pierwiastek stopnia wymiernego też liczy
się łatwo. Błąd maleje bardzo szybko, w przybliżeniu przy każdej iteracji
podwaja się ilość poprawnie wyliczonych cyfr (od pewnego momentu, na
początku może iść trochę wolniej).

Czy moglibyscie zatem przedstawic mi je nieco dokladniej, bo nie barzdo je
rozumiem?

Post by Krzysztof Dulęba
Zamiast liczyć a^x, można znaleźć e^(x * ln (a)). Układy logarytmujące i
liczące funkcję wykładniczą są wbudowane w koprocesor matematyczny i
wywołanie funkcji logarytm jest zamieniane na instrukcję dla tego
koprocesora.

hmm, chyba nikt nie mowil liczeniu a^x? Poza tym ja nie moge korzystac z
funkcji koprocesora. Mam do dyspozycji tylko dodawanie, odejmowanie,
mnozenie i dzielenie.


Łukasz Kalbarczyk, stwierdzil ze istnieje szereg do policzenia pierwiastka.
To jakto jest w koncu, istnieje czy sie ze mnie nabijal?

Bardzo prosze o wyrozumialosc.
Dziekuje

[jtg]

Post by Radiac

Post by Krzysztof Dulęba
Nabijasz się z chłopaka czy mówisz to serio?

Prosze sie ze mnie nie nabijac, jak juz mowielm matematyk ze mnie zaden (a
szkoda) :(

Post by Krzysztof Dulęba
Dobre rozwiązanie wskazał Maciek, do policzenia pierwiastka stopnia k
wystarczy je lekko zmodyfikować, pierwiastek stopnia wymiernego też liczy
się łatwo. Błąd maleje bardzo szybko, w przybliżeniu przy każdej iteracji
podwaja się ilość poprawnie wyliczonych cyfr (od pewnego momentu, na
początku może iść trochę wolniej).

Czy moglibyscie zatem przedstawic mi je nieco dokladniej, bo nie barzdo je
rozumiem?

Post by Krzysztof Dulęba
Zamiast liczyć a^x, można znaleźć e^(x * ln (a)). Układy logarytmujące i
liczące funkcję wykładniczą są wbudowane w koprocesor matematyczny i
wywołanie funkcji logarytm jest zamieniane na instrukcję dla tego
koprocesora.

hmm, chyba nikt nie mowil liczeniu a^x? Poza tym ja nie moge korzystac z
funkcji koprocesora. Mam do dyspozycji tylko dodawanie, odejmowanie,
mnozenie i dzielenie.
Łukasz Kalbarczyk, stwierdzil ze istnieje szereg do policzenia pierwiastka.
To jakto jest w koncu, istnieje czy sie ze mnie nabijal?

Szereg istnieje, jego wyprowadzenie jest opisane w II części
"Matematyki" Żakowskiego i Kołodzieja, w rozdziale "Szereg Taylora".
(Znajdziesz w każdej księgarni z podręcznikami albo u każdego
znajomego studiującego na uczelni technicznej).
Ogólnie rozwijane jest w szereg wyrażenie (1+x)^a, co pozwala Ci
liczyć pierwiastki i potęgi dowolnego stopnia (również rzeczywistego).
Dla a =/= 1, 2, 3, ...
(1+x)^a = 1 + ax + (a*(a-1)*x^2)/2! + (a*(a-1)*(a-2)*x^3)/3! + ...
Dla a = 1, 2, 3, ...
otrzymujemy to samo, ale szereg jest skończony i ma (a+1) wyrazów.

I co z tym robisz? Na przykład jeśli chcesz obliczyć pierwiastek stopnia
3.5 z liczby 17, podstawiasz
1+x = 17, czyli x=16
a = 1/3.5 = 0.28571428571429...
I liczysz szereg.

Szereg jest szybko zbieżny, ale pamiętaj że "szybkość zbieżności"
zależy od x. Im mniejsze x, tym szybciej szereg się zbiega.
Z początku wartości wyrazów bardzo szybko rosną, dopiero
od momentu gdy potęga (i podstawa silni) przekroczy wartość x
zaczynają maleć.

[Krzysztof Dulęba]

Post by jtg
Ogólnie rozwijane jest w szereg wyrażenie (1+x)^a, co pozwala Ci
liczyć pierwiastki i potęgi dowolnego stopnia (również rzeczywistego).
Dla a =/= 1, 2, 3, ...
(1+x)^a = 1 + ax + (a*(a-1)*x^2)/2! + (a*(a-1)*(a-2)*x^3)/3! + ...
Dla a = 1, 2, 3, ...
otrzymujemy to samo, ale szereg jest skończony i ma (a+1) wyrazów.
Szereg jest szybko zbieżny, ale pamiętaj że "szybkość zbieżności"
zależy od x. Im mniejsze x, tym szybciej szereg się zbiega.
Z początku wartości wyrazów bardzo szybko rosną, dopiero
od momentu gdy potęga (i podstawa silni) przekroczy wartość x
zaczynają maleć.

Obaj użyliśmy wyrażenia "szybko zbieżny", więc gwoli ścisłości:

błąd w metodzie stycznej maleje coraz szybciej, przy czym od pewnego
momentu szybciej, niż 1/10^(2^n)), więc ilość poprawnie wyliczonych cyfr
przynajmniej podwaja się. Dokładniej, jeśli e_n to błąd przybliżenia w
n-tym kroku, mamy
e_{n+1} < (k-1)/2*(b^(1/k)) * (e_n)^2.

błąd w przedstawionym przez Ciebie rozwiązaniu maleje wolniej, niż x^n/n!.

Różnica jest duża i istotna.

Pozdrawiam
Krzysztof Dulęba

[Radiac]

Post by jtg
Dla a =/= 1, 2, 3, ...
(1+x)^a = 1 + ax + (a*(a-1)*x^2)/2! + (a*(a-1)*(a-2)*x^3)/3! + ...
Dla a = 1, 2, 3, ...
otrzymujemy to samo, ale szereg jest skończony i ma (a+1) wyrazów.

Wyglada na to ze tak jak napisal Taneli Huuskonen ten szereg nie jest
zbiezny dla nieniaturalnych a, gdy x>1. Sprawdzilem to empirycznie sumujac
200 wyrazow szregeu. Natomiast np dla policzenia sqrt(2) czyli x=1 i a =0.5
szereg jest zbiezny do okolo -6.87 (zsumowalem 200 i 1000 wyrazow). Jednak
dla naturalnych a metoda dziala bez zarzutow.

Tak wiec bylbym bardzo wdzieczny jesli ktos na przykladzie wytlumaczylby mi
"metode stycznej", tak jak to zrobil jtg ze swoim rozwiazaniem.

[£ukasz Kalbarczyk]

Post by Radiac
Łukasz Kalbarczyk, stwierdzil ze istnieje szereg do policzenia
pierwiastka. To jakto jest w koncu, istnieje czy sie ze mnie nabijal?

Pod warunkiem, że potrafisz podnosić do potęgi wymiernej. A to jest
równoznaczne z pierwiastkowaniem, koło się zamyka.

Raczej chodziło mi o to, co opisał itg.
Nie mam zwyczaju nabijać się z ludzi,
którzy zadają sensowne pytania... :)
Czasem tylko (jak ktoś woli - często)
coś pomylę, bo jak pewnie wiesz,
jest jeszcze miesiąc wakacji i staram się
na ten czas całkowicie odłączyć od studiów.

[Maciek]

Post by Radiac

Post by Maciek
Rozwiazaniem jest oczywiscie
x = sqrt( X )
a uzyskuje sie je zaczynajac np. od x=1,
x := (x + X/x) / 2

Nie bardzo rozumiem. Biorac np. sqrt(5) zacynajc od x=1, otrzymuje 3.
I co dalej?

I dalej biorac x=3 otrzymujesz (3+5/3)/2 = 7/3 ~= 2,333333
Dalej biorac x=7/3 otrzymujesz (7/3 + 5/(7/3))/2 = 47/21 ~= 2,238095
Dalej biorac x=47/21 ... (47/21 + 5/(47/21))/2 = 2207/987 ~= 2,236069

Post by Radiac
Poza tym wydaje mi sie ze zalozyles ze chodzi mi o pierwiastek kwadratowy

Oczywisty domysl.

Post by Radiac
a mi chdozi o pierwiastek dowolnego stopnia.

Trza bylo napisac. :)

Post by Radiac
Jedyne co ja wymyslilem to podniesie x do n(stopien pierwiastka) i
porownanie wyniku z argumentem pierwiastka, a nastepnie odpowiednie
iterowanie x az do uzyskania rownosci. Jednak proces ten w zaleznosci od
argumentow moze byc niezmiernie czasochlonny i mnie nie satysfakcjonuje.

Mozesz odpowiednio znormalizowac argument, aby obliczenia byly
szybciej zbiezne (o ile pierwiastek jest "naturalny", tzn. liczysz
wartosc x^(1/n) dla naturalnych n).

Mozesz tez wybadac, ktora metoda jest szybciej zbiezna - stycznych,
czy siecznych. Moze dla pewnych wartosci wykladnikow (dostatecznie
malych albo dostatecznie duzych) warto pierwsze kilka krokow
zrobic najprostszym algorytmem polowienia (bisekcji), by dopiero
potem przejsc na szybko zbiezny algorytm siecznych...?


Ewentualnie zaimplementuj najpierw funkcje logarytmiczna
i wykladnicza (dosc proste szeregi, ew. - po normalizacji
argumentu - aproksymacja wielomianem), a potem wykorzystaj
to, ze funkcje te sa wzajemnie odwrotne:

exp( ln( x ) ) = x

oraz wlasnosc logarytmu:

ln( x^a ) = a * ln( x )

i zastosuj rownosc:

x^a = exp( a * ln( x ) )



Maciek

[Radiac]

Post by Maciek
I dalej biorac x=3 otrzymujesz (3+5/3)/2 = 7/3 ~= 2,333333
Dalej biorac x=7/3 otrzymujesz (7/3 + 5/(7/3))/2 = 47/21 ~= 2,238095
Dalej biorac x=47/21 ... (47/21 + 5/(47/21))/2 = 2207/987 ~= 2,236069

Ok rozumiem :), dzieki.

Post by Maciek
Ewentualnie zaimplementuj najpierw funkcje logarytmiczna
i wykladnicza (dosc proste szeregi, ew. - po normalizacji
argumentu - aproksymacja wielomianem), a potem wykorzystaj
exp( ln( x ) ) = x
ln( x^a ) = a * ln( x )
x^a = exp( a * ln( x ) )

A czy bylbys w stanie mi podac szereg do obliczenia ln(x) ? (exp(x) juz
znam)

[Maciek]

Post by Radiac

(.....)
x^a = exp( a * ln( x ) )

A czy bylbys w stanie mi podac szereg do obliczenia ln(x) ?
(exp(x) juz znam)

Popatrz tu: http://mathworld.wolfram.com/MaclaurinSeries.html



Maciek

[Radiac]

Post by Maciek
Popatrz tu: http://mathworld.wolfram.com/MaclaurinSeries.html

wow, super! wielkie dzieki!!! :)

[Radiac]

Post by Maciek
I dalej biorac x=3 otrzymujesz (3+5/3)/2 = 7/3 ~= 2,333333
Dalej biorac x=7/3 otrzymujesz (7/3 + 5/(7/3))/2 = 47/21 ~= 2,238095
Dalej biorac x=47/21 ... (47/21 + 5/(47/21))/2 = 2207/987 ~= 2,236069

Ok rozumiem :), dzieki.

Post by Maciek
Ewentualnie zaimplementuj najpierw funkcje logarytmiczna
i wykladnicza (dosc proste szeregi, ew. - po normalizacji
argumentu - aproksymacja wielomianem), a potem wykorzystaj
exp( ln( x ) ) = x
ln( x^a ) = a * ln( x )
x^a = exp( a * ln( x ) )

A czy bylbys w stanie mi podac szereg do obliczenia ln(x) ? (exp(x) juz
znam)

[Grzegorz Gierlasiñski]

poszukaj w archiwum grupy
nie tak dawno Wlodek Holsztynski podal bardzo szybki algorytm (metode)
obliczania pierwiastkow kwadratowych
zacznij od tego, zrozumiesz idee i potem napiszesz algorytm dla dowolnego
pierwiastka ;-)

Grzegorz Gierlasiński

PS nie nabijam sie z Ciebie (zauwazylem ze jestes przeczulony na tym
punkcie)

[Radiac]

Post by Grzegorz Gierlasiñski
poszukaj w archiwum grupy
nie tak dawno Wlodek Holsztynski podal bardzo szybki algorytm (metode)
obliczania pierwiastkow kwadratowych
zacznij od tego, zrozumiesz idee i potem napiszesz algorytm dla dowolnego
pierwiastka ;-)

No znalazlem to czym mowisz, tylko ze tego nie rozumiem :(
Juz na samym poczatku Wlodzimierz Holsztynski pisze: "Zacznij od dowolnej
liczby dodatniej A(0)", i nie wiem jak mam rozumiec to A(0), bo dla mnie to
jest wartosc funkcji A(x). A co to za funkcja???
Wiec domyslam sie ze nie chodzi tu zadna funckje, ale o co to ja nie wiem.

Post by Grzegorz Gierlasiñski
PS nie nabijam sie z Ciebie (zauwazylem ze jestes przeczulony na tym
punkcie)

I wlasnie dlatego mam te kompleksy :(

[Grzegorz Gierlasiñski]

Post by Radiac
Juz na samym poczatku Wlodzimierz Holsztynski pisze: "Zacznij od dowolnej
liczby dodatniej A(0)", i nie wiem jak mam rozumiec to A(0), bo dla mnie to
jest wartosc funkcji A(x). A co to za funkcja???

w zacytowanym przez Ciebie zdaniu wogole nie trzeba nic kombinowac. skoro
masz zaczac od DOWOLNEJ liczby dodatniej to wez sobie 1
i dokonaj obliczen

sprawdzalem ten algorytm i jest naprawde dobry

pozdrawiam
Grzegorz Gierlasiński