---

Jeg lærte engang en algoritme, der med vilkårlig præcision kunne udregne
kvadratroden på et vilkårligt reelt tal:

* Algoritmen gav i første trin det første chiffer af resultatet, dernæst det
andet chiffer, osv.

* Metoden mindede om division i hånden. På et tidspunkt i et trin skulle man
altid addere en fast konstant. Jeg husker ikke konstanten, men det var
omkring 20 eller 30.

Det er alt jeg husker - er der nogen der kender denne algoritme?

Ps. jeg er IKKE interesseret i alle de øvrige algortimer for kvadratrødder.

Mvh,

Lasse

---

"LR" <lar@tdcadsl.dk> enriched usenet with:

> Jeg lærte engang en algoritme, der med vilkårlig præcision kunne
> udregne kvadratroden på et vilkårligt reelt tal:
>
> * Algoritmen gav i første trin det første chiffer af resultatet,
> dernæst det andet chiffer, osv.
>
> * Metoden mindede om division i hånden. På et tidspunkt i et trin
> skulle man altid addere en fast konstant. Jeg husker ikke konstanten,
> men det var omkring 20 eller 30.
>
> Det er alt jeg husker - er der nogen der kender denne algoritme?

Gak til Google og bliv vis:
http://shor.ter.dk/373347092

--
Lars Kyndi Laursen, representatum nixi

Marge Gunderson: "I'm not sure I agree with you a hunnert percent
on your policework, there, Lou."

---

Jubi, det var lige den jeg tænkte på :)

Tak til jer begge

Lasse


"Lars Kyndi Laursen" <spam_me_senseless@mail.dk> wrote in message
news:Xns92E8E8811EA9Flarskyndidk@aa635.kyndi.dk...
> "LR" <lar@tdcadsl.dk> enriched usenet with:
>
> > Jeg lærte engang en algoritme, der med vilkårlig præcision kunne
> > udregne kvadratroden på et vilkårligt reelt tal:
> >
> > * Algoritmen gav i første trin det første chiffer af resultatet,
> > dernæst det andet chiffer, osv.
> >
> > * Metoden mindede om division i hånden. På et tidspunkt i et trin
> > skulle man altid addere en fast konstant. Jeg husker ikke konstanten,
> > men det var omkring 20 eller 30.
> >
> > Det er alt jeg husker - er der nogen der kender denne algoritme?
>
> Gak til Google og bliv vis:
> http://shor.ter.dk/373347092
>
> --
> Lars Kyndi Laursen, representatum nixi
>
> Marge Gunderson: "I'm not sure I agree with you a hunnert percent
> on your policework, there, Lou."

---

Lars Kyndi Laursen wrote:

> "LR" <lar@tdcadsl.dk> enriched usenet with:
>
> > Jeg lærte engang en algoritme, der med vilkårlig præcision kunne
> > udregne kvadratroden på et vilkårligt reelt tal:
> >
> > * Algoritmen gav i første trin det første chiffer af resultatet,
> > dernæst det andet chiffer, osv.

Der findes en sjov numerisk metode til beregning af kvadratrod.

Det tal, vi skal udregne kvadratrod af, kalder vi n. Vi tager to vilkårlige
faktorer af n, som vi kalder a og b (er n et primtal, så er a = n og b =
1).

Vi beregner det "aritmetiske gennemsnit" (der kaldes r) af disse to
faktorer. Det er jo det, vi normalt nøjes med at kalde gennemsnit:

r = (a + b) / 2

Derefter beregnes det såkaldte "harmoniske gennemsnit" (der kaldes s), som
er:

s = (2*a*b) / (a + b)

Så tager vi det aritmetiske gennemsnit r(1) af de to gennemsnit r og s,
som vi har beregnet, samt deres harmoniske gennemsnit s(1). Osv. osv.

Værdierne r og s er tilnærmede værdier for kvadratrodden. Metoden
konvergerer meget hurtigt imod den korrekte værdi.

Lad os f.eks. beregne sqrt(3): a = 3 og b = 1.
Vi får følgende tilnærmede værdier:

r = 2 r(1) = 7/4 r(2) = 97/56 r(3) = 18817/10864
s = 3/2 s(1) = 12/7 s(2) = 168/97 s(3) = 32592/18817

Standser vi her, har vi:

r(3) = 1,732050810
s(3) = 1,732050805

altså hele 7 korrekte decimaler allerede efter tre passager!

Beregningen af det aritmetiske gennemsnit er ikke specielt vanskelig. For
at beregne det armoniske gennemsnit er der en praktisk metode: Man bytter
om på tæller og nævner og man ganger med n. F.eks.:

s(2) = (56/97)*3 = 168/97

Som sagt har denne metode den fordel, at resultatet er meget præcist
allerede efter få tilnærmelser. Ulempen er, at det kan blive svært at se,
om det pågældende tal er et perfekt kvadrat (altså et tal som 25, 64, 81,
256 osv.). Desuden bliver metoden vanskelig at anvende i praksis, når
tallet har mange cifre.

Karamel

---

karamel <karamel@REMOVEoncable.dk> writes:

> Lars Kyndi Laursen wrote:
>
> > "LR" <lar@tdcadsl.dk> enriched usenet with:
> >
> > > Jeg lærte engang en algoritme, der med vilkårlig præcision kunne
> > > udregne kvadratroden på et vilkårligt reelt tal:
> > >
> > > * Algoritmen gav i første trin det første chiffer af resultatet,
> > > dernæst det andet chiffer, osv.
>
> Der findes en sjov numerisk metode til beregning af kvadratrod.

[metode slettet]

Den "almindelige" newtoniteration ser nemmere ud:

1) Start med 1 som gæt på en rod, altså r0 = 1.

2) Lad r1 = (r0 + x/r0)/2.

3) Lad r2 = (r1 + x/r1)/2.

4) Osv.

For x=3 fås:

r0 = 1, r1 = 2, r2 = 7/4, r3 = 97/56, r4 = 18817/10864 osv.

Men igen er denne metode mest interessant, hvis man har en
regnemaskine. Den divisions-lignende metode har dog den ulempe, at
den konvergerer langsomt (hvert trin giver et nyt ciffer, mens
newtoniteration ca. fordobler antallet af rigtige cifre i hver
iteration).

   Torben Mogensen

---

"Torben Ægidius Mogensen" <torbenm@diku.dk> skrev i en meddelelse news:w5n0n1j677.fsf@pc-032.diku.dk...
> karamel <karamel@REMOVEoncable.dk> writes:
>
> > Lars Kyndi Laursen wrote:
> >
> > > "LR" <lar@tdcadsl.dk> enriched usenet with:
> > >
> > > > Jeg lærte engang en algoritme, der med vilkårlig præcision kunne
> > > > udregne kvadratroden på et vilkårligt reelt tal:
> > > >
> > > > * Algoritmen gav i første trin det første chiffer af resultatet,
> > > > dernæst det andet chiffer, osv.
> >
> > Der findes en sjov numerisk metode til beregning af kvadratrod.
>
> [metode slettet]
>
> Den "almindelige" newtoniteration ser nemmere ud:
>
> 1) Start med 1 som gæt på en rod, altså r0 = 1.
>
> 2) Lad r1 = (r0 + x/r0)/2.
>
> 3) Lad r2 = (r1 + x/r1)/2.
>
> 4) Osv.
>
> For x=3 fås:
>
> r0 = 1, r1 = 2, r2 = 7/4, r3 = 97/56, r4 = 18817/10864 osv.
>
> Men igen er denne metode mest interessant, hvis man har en
> regnemaskine. Den divisions-lignende metode har dog den ulempe, at
> den konvergerer langsomt (hvert trin giver et nyt ciffer, mens
> newtoniteration ca. fordobler antallet af rigtige cifre i hver
> iteration).
>
Jamen er karamels metode ikke newtons?

Mvh
Martin

---

Martin Larsen wrote:

> Jamen er karamels metode ikke newtons?
>
> Mvh
> Martin

Jeg ved det ikke, men det er da muligt, for Newton har lavet så meget... det ville ikke undre mig, hvis jeg
fandt en opskrift som "Spaghetti à la Newton"

Men når man taler om Newtons iteration mener man som regel en numerisk metode for at løse ligninger, som
ikke kan løses algebraisk (man kan selvfølgelig løse enhver slags ligning ved hjælp af N.I., men når en
ligning ikke kan løses algebraisk, så bliver man ligefrem nødt til at bruge numeriske metoder). Som
f.eks.: x + cosx = 0.

Kort sagt går N.I. ud på, at man gætter en løsning, og så finder man en bedre løsning ved at erstatte
funktionen med en ret linie, som har en hældning, der er lig med funktionens differentialkvotient, hvor man
har gættet (geometrisk er det tangenten til grafen for funktionen, og løsningen er nulpunktet). Derefter
sammenlignes det fundne nulpunkt med funktionens rigtige værdi dér, og hvis det ikke ligger inden for den
tolerance, man har valgt, gætter man videre herfra.

Men med hensyn til den numeriske metode for at finde kvadratrødder, så mener jeg, at løsningen nærmer sig
eksponentielt til den rigtige værdi for hvert nyt gæt - så jeg ved ikke, hvad man kan forlange mere... Jeg
kan evt. tjekke i den bog, jeg har den fra.

Karamel

---

"karamel" <karamel@REMOVEoncable.dk> skrev i en meddelelse news:3E035845.8E68AA0B@REMOVEoncable.dk...
> Martin Larsen wrote:
>
> > Jamen er karamels metode ikke newtons?
>
[snip]
>
> Men med hensyn til den numeriske metode for at finde kvadratrødder, så mener jeg, at løsningen nærmer sig
> eksponentielt til den rigtige værdi for hvert nyt gæt - så jeg ved ikke, hvad man kan forlange mere... Jeg
> kan evt. tjekke i den bog, jeg har den fra.
>
Newtons approximation for kvadratrod er som angivet af Ægidius.
Den kan skrives x1=1/2*(x0+N/x0). N = 3 i exemplet.
Dens approximerer kvadratisk (genrelt).

Ved nærmere betragtning ser vi at den er magen til din metode.
Det du kalder r svarer til x1 og det du kalder s svarer til N/x0.

Generelt for roden n har man iøvrigt x1=1/n*((n+1)x0-N/x0^(n-1))

Mvh
Martin

---

(n-1) erstatter (n+1)

---

karamel <karamel@REMOVEoncable.dk> writes:

> Men når man taler om Newtons iteration mener man som regel en numerisk metode for at løse ligninger, som
> ikke kan løses algebraisk (man kan selvfølgelig løse enhver slags ligning ved hjælp af N.I., men når en
> ligning ikke kan løses algebraisk, så bliver man ligefrem nødt til at bruge numeriske metoder). Som
> f.eks.: x + cosx = 0.

Hmm, sådan noget må du jo ikke sige på en lørdag hvor jeg ikke har noget
at lave... Nu sidder jeg jo og kan ikke få det ind i hovedet hvorfor den
ikke kan løses.... Jeg kan (selvfølgelig) ikke selv løse den, men "kan"
det virkelig ikke lade sig gøre? Så vidt jeg kan se har det noget at
gøre med at der faktisk er 2 ukendte, fordi man ikke i dette tilfælde
umiddelbart kan fjerne cos(x) fra udtrykket, uden at få et tilsvarende
led med acos(x) ud af det andet led... Men det /må/ da teoretisk set
kunne lade sig gøre at løse det? Eller har jeg bare for stor tillid til
algebra? Kan det så heller ikke lade sig gøre at løse 3. gradsligninger?
Jeg spørger fordi jeg på HTX 3. års matematik A-niveau er blevet
introduceret til Newtons metode som en løsning til disse... Jeg troede
det var fordi at en algebraisk/teoretisk løsning er for avanceret til
vores pensum, men det er måske simpelthen ikke muligt?

--
Ulrik Jensen
ulrik@qcom.dk - http://www.minefilm.tk
"It's only a movie, and, after all, we're all grossly overpaid."

---

Ulrik Jensen wrote:
>
> > f.eks.: x + cosx = 0.
>
> Hmm, sådan noget må du jo ikke sige på en lørdag hvor jeg ikke har noget
> at lave... Nu sidder jeg jo og kan ikke få det ind i hovedet hvorfor den
> ikke kan løses.... Jeg kan (selvfølgelig) ikke selv løse den, men "kan"
> det virkelig ikke lade sig gøre?

Det kan nok ikke lade sig gøre at udtrykke løsningen med »standard-
funktioner«. Men hvis man »snyder« og indører nye funktioner, kan man
jo altid udtrykke løsningen ved dem.

Fx kan ligningen 2^x=3 heller ikke løses *før* man indfører logaritme-
funktionen.

Da funktionen f(x)=x+cosx er strengt voksende, har den en omvendt
funktion som man kunne kalde noget. Lad os kalde den invidpluscos.
Så er løsningen jo bare invidpluscos(0) .

> [...] Kan det så heller ikke lade sig gøre at løse 3. gradsligninger?

Jo, der findes (indviklede) formler til eksakt løsning af tredje- og
fjerdegradsligninger. Til gengæld kan man ikke løse femtegradsligninger
(bevist af Abel og Galois).

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

karamel wrote:
>
> f.eks.: x + cosx = 0.

På en regnemaskine findes der for resten en nem måde at finde løsningen
til denne ligning på. Indtast et tal nær 0,7, og bliv ved med at tage
cosinus (iterér). Det er naturligvis vigtigt at regnemaskinen er ind-
stillet på radianer. På mange regnemaskiner trykker man blot gentagne
gange på COS. På fx TI-83 skriver man "cos(Ans)" og trykker mange
gange på ENTER.

Det tal der kommer frem, løser ligningen

cos x = x

Løsningen til x+cosx=0 er naturligvis blot den negative værdi af det
samme tal.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse news:3E043D8C.6D5019ED@jeppesn.dk...
> karamel wrote:
> >
> > f.eks.: x + cosx = 0.
>
> På en regnemaskine findes der for resten en nem måde at finde løsningen
> til denne ligning på. Indtast et tal nær 0,7, og bliv ved med at tage
> cosinus (iterér). Det er naturligvis vigtigt at regnemaskinen er ind-
> stillet på radianer. På mange regnemaskiner trykker man blot gentagne
> gange på COS. På fx TI-83 skriver man "cos(Ans)" og trykker mange
> gange på ENTER.
>
> Det tal der kommer frem, løser ligningen
>
> cos x = x
>
> Løsningen til x+cosx=0 er naturligvis blot den negative værdi af det
> samme tal.
>
Jeg brugte Newtons approximation og fik -.7390851332151607 (3 skridt)
Det nager mig lidt at jeg ikke lige fandt et "kendt" udtryk.

Mvh
Martin

---

[Torben Ægidius Mogensen]

| Den "almindelige" newtoniteration ser nemmere ud:
|
| 1) Start med 1 som gæt på en rod, altså r0 = 1.
|
| 2) Lad r1 = (r0 + x/r0)/2.
|
| 3) Lad r2 = (r1 + x/r1)/2.
|
| 4) Osv.
|
| For x=3 fås:
|
| r0 = 1, r1 = 2, r2 = 7/4, r3 = 97/56, r4 = 18817/10864 osv.
|
| Men igen er denne metode mest interessant, hvis man har en
| regnemaskine.

I hvilket fall man formodentlig heller bruker sqrt-knappen på
regnemaskinen ...

| Den divisions-lignende metode har dog den ulempe, at den konvergerer
| langsomt (hvert trin giver et nyt ciffer, mens newtoniteration
| ca. fordobler antallet af rigtige cifre i hver iteration).

Fett nok, men for å fa tak på de riktige sifre må du jo nettopp utføre
en lang divisjon til slutt, med ett skritt pr siffer. Eller?
--
Stein Arild Strømme +47 55584825, +47 95801887
Universitetet i Bergen Fax: +47 55589672
Matematisk institutt www.mi.uib.no/~stromme
Johs Brunsg 12, N-5008 BERGEN stromme@mi.uib.no

---

> Men igen er denne metode mest interessant, hvis man har en
> regnemaskine. Den divisions-lignende metode har dog den ulempe, at
> den konvergerer langsomt (hvert trin giver et nyt ciffer, mens
> newtoniteration ca. fordobler antallet af rigtige cifre i hver
> iteration).

Jeg havde et håb om, at "divisionsmetoden" havde linær tidskompleksitet mht.
præcision (har den ikke), hvilket heller ikke kan lade sig gøre, har jeg nu
erfaret.

Mvh,

Lasse

---

> *> * Metoden mindede om division i hånden. På et tidspunkt i et trin
skulle man
> altid addere en fast konstant. Jeg husker ikke konstanten, men det var
> omkring 20 eller 30.

Kan det være sådan noget her?: http://tinyurl.com/3nvh


> Det er alt jeg husker - er der nogen der kender denne algoritme?

Ellers prøv at lede efter Trachtenbergs metoder på Google, der plejer at
være noget.

-----
Jes Hansen