gyökszámolási probléma

Programozás - kezdő

Hello!REmélem tud nekem valaki segíteni!A feladat a következő lenne:
. A √x kiszámolása iterációval (c=(x-1)/4, y2+y-c=0 Ţ yi+1=c/(yi+1), ha i->végtelen, 2yi+1->gyök x) adott pontossággal (input vagy fixen beírva). Az sqrt() nem használható.

Már az is nagy segítség lenne ha valaki tuná értelmezni ezt az iterációt mert én már ezt sem nagyon értem! Vagy akármilyen más segítség jól jönne.
Köszönöm

  • 3697 megtekintés

( mazursky | 2007. 12. 13., cs – 10:13 )

ezt nézd meg hátha:

http://www.prog.hu/tudastar/12596/Logaritmus+es+n-edik+gyok.html

illetve pár okosság még van itt is:

http://www.hik.hu/tankonyvtar/site/books/b128/

ami még eszembe jutott:

Van egy jó rekurzió a gyök(x)-re. Elég béna lesz ez így leírva. Tehát legyen:
a(0) 1, x, vagy x/2. (Vagy bármilyen pozitív szám.)
a(n+1) = (a(n)+x/a(n))/2.
Ez egy marha gyors eljárás. Ráadásul elég könnyű bizonyítani, hogy jó. Pl. x=2-re és a(0)=1 választással:
a(0)=1
a(1)=1,5
a(2)=1,416666667
a(3)=1,414215686
a(4)=1,414213562
a(5)=a(4) (!)
és gyök(2)=1,414213562. Az adatok a számológépem kijelzőjéről valók.
Mint látod, mindegy egyes iterációval egyel több helyes számjegy lesz benne.

/mazursky

( Galadh Ereb | 2007. 12. 13., cs – 10:29 )

Hát, így nekem sem érthető, első ránézésre még erre hasonlít a legjobban.
Ezt a részt beírnád pontosabban : y2+y-c=0 Ţ.

( vondra | 2007. 12. 13., cs – 10:45 )

bocsánat nem vettem észre hogy kicsit hibásan jelent meg:
c=(x-1)/4 , yˇ2(négyzeten)+y-c=0 -> y(alsóindexbe:i+1)=c/(y(alsóindexbe:i)+1) ha i->végtelen, 2y(alsóindexbe:i)+1->gyökx

Ez már pontos. Remélem értehető is mi hol van :)

Na kezdjük az elején. Az x szám gyökére lenne szükséged. ha x helyére beírod az adott számot akkor kapsz egy c-t ezt bevésed egy 0-ra rendezett egység együtthatós másodfokú egyenletbe. Így a másodfokú egyenlet megoldókéletébe behelyettesítve maga a szám gyoke az 2*y, ha hozzáadunk 1-et, ha jól értelmezem. Tehát itt neked csak annyi van felírva, hogy a másodfokú egyenlet megoldókélete van közelítéssel megoldva, egység együtthatóra, kivéve a c, mert az a számunk gyökét képezi. Tehát ez csak egy átrendezett másodfokú egynelet megoldóképlet közelítéssel.

Dehogynem!
Teljesen tőkéletes!
Ez egy matematikai trükk, de jó. A másodfokú egynelet megoldóképletéből van kifelyezve a c lényegében, és visszaírva. Lényegében úgy választjuk meg c-t hogy x szám gyöke legyen a megoldás. Mikorra kell neked a megoldás?
Ha ráér estére lekódolom neked C-ben.

igazából nekem minél előbb kéne de péntekig kell leadnom. természetesenn nagyon hálás lennék ha azt nekem vlaahogy átírnád c be :)
akkor meg pláne hogyha még el is magyaráznád valamilyen úton, mert azért szeretném megérteni. Mármint c be is mert igy már kezdem kapizsgálni :D

#include

main ()

{
double y, hiba=1.0, c, x, ry, q;

printf ("Kérem adja meg a számot:");
scanf ("%lf",&x);
c=(x-1.0)/4.0;
q=c;
while (hiba>0.0000001)
{
ry=q;
q=(c/(q+1)+q)/2;
hiba=1000.0*(ry-q);
printf ("A gyök %.15lf %lf\n",2*q+1, hiba);
};
}

//Itt a kód! Ez az első működő nem csinosítottam rajta semmit csak fut.

Bocs hogy ismét problémám van. De a tanár azt mondja hogy a hibát ugy adjam vissza hogy a q értékét(mert az a gyök) megszorozva önmagával és ezt kivonva a bekért számból. Szóval az csak annyi lenne hogy nem ezerrel szorzom vissza hanem
q val? vagy teljesen hülyeség? :D

Mert a hibahatár ellenőrzését is át kell írni, hiszen tök más értékekre fog helyesen lefutni.

De ha kreatív vagy, pusztán matematikai úton is meg tudod a végén buherálni a hiba értékét úgy, hogy jól adja vissza, és akkor az eredeti kód is jó lesz. Persze ehhez picit számolni kell...

Azt hiszem sikerült megérteni.
Tehát a lényeg, hogy inicializálod y_0 -t valamivel, aztán folyamatosan alkalmazod az y_{i+1}= c/(y_i + 1)-et,amíg jó nem lesz. Ahol c ugye egy konstnas.

Próbáltam a módszert visszavezetni a Babiloni módszerre, de vagy én vagyok nagyon béna ma reggel, vagy tényleg nem ekvivalens a a kettő. Most el kell mennem, de ha lesz időm, ránézek megint.

szerk.: jah, és kipróbálva,szépen közelít tényleg, szóval a Babilonitól amivel eltér hibatagban az valószínűleg elhanyagolható.

( mrev | 2007. 12. 13., cs – 11:28 )

Itt egy komplett Clipper program az iterációra: 


// y=x**2, y --> x 

function main(arg)

local y:=val(arg),y1,x1
local hiba:=1

    x1:=y //első közelítés
    while( abs(hiba)>0.000001 )
        y1:=x1*x1
        hiba:=y-y1
        ? x1:=(y1+hiba/2)/x1 //következő közelítés
    end

A ? operátor kiírja a változót. Az x1:=(y1+hiba/2)/x1 egyenletnek fixpontja a keresett megoldás.

--
CCC3

Nem vette észre a srác, hogy működő programot kapott. Itt a C-be átírt változat: 


#include <stdio.h>
#include <math.h>

int main()
{
    double y,y1,x1,hiba=1;
    
    y=20; //ennek a gyöke kell
    x1=y; //első közelítés

    while( fabs(hiba)>0.0000001 )
    {
        y1=x1*x1;
        hiba=y-y1;
        x1=(y1+hiba/2)/x1; //következő közelítés
        printf("%f\n",x1);
    }
}

--
CCC3

( Balu007 | 2007. 12. 13., cs – 12:04 )

Ha nem feltetlenul iteracioval szeretned megoldani, akkor ott a Taylor sor vagy a Maclaurin sor
∑f(x(0))(n)/n! * (x-x0)n
neked ez: x0=1, n meg amennyit szeretnel

0. differencial eseten: x01/2/1 * 1
1. differencial eseten: 1/2 * x0-1/2/1 * (x-x0)
2. differencial eseten: -1/4 * x0-3/2/2 * (x-x0)2
3. differencial eseten: 3/8 * x0-5/2/6 * (x-x0)3
4. differencial eseten: -15/16 * x0-7/2/24 * (x-x0)4
5. differencial eseten: 105/32 * x0-9/2/120 * (x-x0)5
...
...
...
persze ezeket osszeadod

Es neked x0=1, x meg a keresett szam!
Szerintem olyan n=15-ig ha elmesz az mar soksok tizedesjegyig pontos

( rpsoft v | 2007. 12. 13., cs – 13:33 )

Bocs, C-ben nem akarom most megírni a házidat (mert abból te semmit sem tanulsz, én meg már csináltam gyökkeresőt), csak egy kis segítség:

hogy is számolunk iterációt:

1. kiszámoljuk, amire szükségünk lesz menet közben

2. addig számolgatjuk a sorozat későbbi tagjait, amíg elég pontosak nem lettünk. Eközben persze az előző tagokat eldobhatjuk.

Tehát valami olyan, hogy 


legyen c = (x-1)/4
legyen y = (valami kezdőérték, x ha nem jut jobb eszünkbe)

amígy elég pontosak nem lettünk
           addig legyen y = c/(y+1)

írjuk ki gyok(x) = 2 y+1-et

Az persze jó kérdés, hogy mikor vagyunk már elég pontosak, egy lehetségés megoldás mindig eltenni y egy régebbi értékét is, és ha már a változás kisebb egy korlátnál, akkor vagyunk kész. Vagy visszahelyettesíted y-t az egyenletébe, és ha a hiba kisebb valaminél, akkor van kész.

( gsimon | 2007. 12. 17., h – 10:16 )

Már elnézést, de ha egyszer _gyorsan_ szeretnénk egész gyököt vonni, akkor a ciklusmagban lévő változóval (tehát nem 2-hatvány konstanssal) való osztás miatt a fenti algoritmusok finoman szólva szuboptimálisak. Tessék kicsit szétnézni az uclibc forrásában (int_sqrt.c): 


unsigned long int_sqrt(unsigned long x)
{
        unsigned long op, res, one;

        op = x;
        res = 0;

        one = 1UL << (BITS_PER_LONG - 2);
        while (one > op)
                one >>= 2;

        while (one != 0) {
                if (op >= res + one) {
                        op = op - (res + one);
                        res = res +  2 * one;
                }
                res /= 2;
                one /= 4;
        }
        return res;
}

Mint látható, csak 2-hatvánnyal való szorzás ill. osztás van benne, amit a fordító shifteléssé ill. dupla hozzáadássá fog alakítani. Amúgy csak érdekességképp, a fenti algoritmus x86 asm verziójával valamikor '95 körül találkoztam a szép emlékű comp.lang.asm.x86 newsgroupon: 


From goliat.eik.bme.hu!scsing.switch.ch!swidir.switch.ch!univ-lyon1.fr!fdn.fr!uunet!cs.utexas.edu!swrinde!gatech!concert!deltacom!sean.palmer Fri Mar 31 10:08:33 1995
Path: goliat.eik.bme.hu!scsing.switch.ch!swidir.switch.ch!univ-lyon1.fr!fdn.fr!uunet!cs.utexas.edu!swrinde!gatech!concert!deltacom!sean.palmer
Distribution: world
Newsgroups: comp.lang.asm.x86
X-Apparently-to: ODD MAGNE HAAGENSEN
Subject: WANTED: square root rout
From: sean.palmer _at_ delta.com (Sean Palmer)
Message-ID: <ac.3501.8467 _at_ delta.com>
Date: Tue, 28 Mar 1995 16:12:00 -0500
Organization: deltaComm Online :: 919-481-9399 v.32bis
Lines: 37

OM>Has anyone got, or know where to find, a (fast) assembler routine for 
OM>calculating the square root for 16.16 fixed point numbers? (in 386 asse

;function iSqrt(x:longint):word;
        xor eax,eax
        xor edx,edx
        mov edi,x
        mov cx,17   ;only calc 1 word, plus 1 binary point for rounding
@@L:    shld edx,edi,2
        shl edi,2
        shl eax,1
        cmp edx,eax
        jle @@S
        sub edx,eax
        dec edx
        add eax,2
@@S:    dec cx
        jnz @@L
        shr eax,2               ;to ax, carry
        adc ax,0                ;round result
        xor dx,dx               ;result in dx:ax
        mov dl,ah               
        shl ax,8
        ret

This should work on fixed point numbers (I just patched it in the mail 
reader), provided you don't mind losing 8 bits of accuracy in the 
process... There are slightly faster algorithms out there, but my at-work 
copies seem to have disappeared. Unrolling the above loop would help alot.

If you wanted to save those lower 8 bits, you'd have to convert this to a 
48-bit square root and shift the input up 16 bits before running it 
through, which would slow it down quite a bit. 8 bit fractional accuracy is 
sufficient for most applications though. 

---
 * WR  # 380 * C program run.  C program crash.  C programmer drink.