---

Jeg har ladet mig fortælle af en underviser på ingeniørstudiet på et
tidspunkt at f.eks. en TI-89 lommeregner benytter sig af Herons formel
ifb. udregning af kvadratrødder. Noget med
Gæt2=0.5*(gæt1+(maxgrænse/gæt1)) eks. kvadratrod 2: her må værdien ligge
imellem 1 og 2
så et gæt på 1.5 er kvalificeret: gæt2=0.5(1.5 + (2/1.5))=1,4166
....så fortsætter man:
gæt3=0.5(gæt2+(2/gæt2))=0.5(1.4166+(2/1.4166))=1,4142 osv indtil man
opnår ønsket præcision.

Formlen ser ud til at fungere fint med kvardratrødder men ikke med så
meget andet....hvad er den dybere sammenhæng imellem Herons formel (som
anvendes i trigonometrien) og så lige kvardratrødder siden den kan
anvendes på det område ? Desuden den her anvendte formel synes intet at
have at gøre med Herons formel som jeg læser den på wikipedia ???

Har den her viste formel overhovedet noget med Herons formel at gøre ?

---

Den 28/08/11 21.46, Pedersen skrev:
> Jeg har ladet mig fortælle af en underviser på ingeniørstudiet på et
> tidspunkt at f.eks. en TI-89 lommeregner benytter sig af Herons formel
> ifb. udregning af kvadratrødder. Noget med
> Gæt2=0.5*(gæt1+(maxgrænse/gæt1)) eks. kvadratrod 2: her må værdien ligge
> imellem 1 og 2
> så et gæt på 1.5 er kvalificeret: gæt2=0.5(1.5 + (2/1.5))=1,4166
> ...så fortsætter man:
> gæt3=0.5(gæt2+(2/gæt2))=0.5(1.4166+(2/1.4166))=1,4142 osv indtil man
> opnår ønsket præcision.
>
> Formlen ser ud til at fungere fint med kvardratrødder men ikke med så
> meget andet....hvad er den dybere sammenhæng imellem Herons formel (som
> anvendes i trigonometrien) og så lige kvardratrødder siden den kan
> anvendes på det område ? Desuden den her anvendte formel synes intet at
> have at gøre med Herons formel som jeg læser den på wikipedia ???
>
> Har den her viste formel overhovedet noget med Herons formel at gøre ?

Det er ikke Herons formel du beskriver ovenfor, men Herons metode, som
ikke er en formel, men en iterativ algoritme. De to har næppe noget med
hinanden at gøre, jeg kan i hvert fald ikke se sammenhængen.

Mvh. Lars
PS. Hvis du vil lære matematik, så hold dig fra ingeniørstudiet

---

On 28-08-2011 22:14, Lars Kongshøj wrote:
> Den 28/08/11 21.46, Pedersen skrev:
>> Jeg har ladet mig fortælle af en underviser på ingeniørstudiet på et
>> tidspunkt at f.eks. en TI-89 lommeregner benytter sig af Herons formel
>> ifb. udregning af kvadratrødder. Noget med
>> Gæt2=0.5*(gæt1+(maxgrænse/gæt1)) eks. kvadratrod 2: her må værdien ligge
>> imellem 1 og 2
>> så et gæt på 1.5 er kvalificeret: gæt2=0.5(1.5 + (2/1.5))=1,4166
>> ...så fortsætter man:
>> gæt3=0.5(gæt2+(2/gæt2))=0.5(1.4166+(2/1.4166))=1,4142 osv indtil man
>> opnår ønsket præcision.
>>
>> Formlen ser ud til at fungere fint med kvardratrødder men ikke med så
>> meget andet....hvad er den dybere sammenhæng imellem Herons formel (som
>> anvendes i trigonometrien) og så lige kvardratrødder siden den kan
>> anvendes på det område ? Desuden den her anvendte formel synes intet at
>> have at gøre med Herons formel som jeg læser den på wikipedia ???
>>
>> Har den her viste formel overhovedet noget med Herons formel at gøre ?
>
> Det er ikke Herons formel du beskriver ovenfor, men Herons metode, som
> ikke er en formel, men en iterativ algoritme. De to har næppe noget med
> hinanden at gøre, jeg kan i hvert fald ikke se sammenhængen.
>
> Mvh. Lars
> PS. Hvis du vil lære matematik, så hold dig fra ingeniørstudiet

Takker for præciseringen :)

Nej jeg ser udelukkende sammenhængen ift at begge steder halverer man
åbenbart en størrelse :) ... og fatter stadig ikke hvorfor Herons metode
er så suveræn til kvadratrødder men overhovet ikke duer i anden kontekst
:) Når jeg ikke kan gennemskue hvorfor en metode virker nægter jeg at
kendes ved den :)

---

Den 28/08/11 22.27, Pedersen skrev:
> Nej jeg ser udelukkende sammenhængen ift at begge steder halverer man
> åbenbart en størrelse :)

Man halverer jo ikke, man tager gennemsnittet af to størrelser.

> ... og fatter stadig ikke hvorfor Herons metode
> er så suveræn til kvadratrødder men overhovet ikke duer i anden kontekst

Tankegangen kan også bruges ved udvikling af andre iterative algoritmer.
Tag et kursus i numerisk analyse.

> :) Når jeg ikke kan gennemskue hvorfor en metode virker nægter jeg at
> kendes ved den :)

Den er nem at indse. Læs evt:
<http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method>

Mvh. Lars

---

On 28-08-2011 23:25, Lars Kongshøj wrote:
> Den 28/08/11 22.27, Pedersen skrev:
>> Nej jeg ser udelukkende sammenhængen ift at begge steder halverer man
>> åbenbart en størrelse :)
>
> Man halverer jo ikke, man tager gennemsnittet af to størrelser.
>
>> ... og fatter stadig ikke hvorfor Herons metode
>> er så suveræn til kvadratrødder men overhovet ikke duer i anden kontekst
>
> Tankegangen kan også bruges ved udvikling af andre iterative algoritmer.
> Tag et kursus i numerisk analyse.
>
>> :) Når jeg ikke kan gennemskue hvorfor en metode virker nægter jeg at
>> kendes ved den :)
>
> Den er nem at indse. Læs evt:
> <http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method>
>
>
> Mvh. Lars

1000 tak for link :) gav inspiration til fordybelse og indsigt :)

---

Pedersen <connyhoeyer@stofanet.dk> writes:

> Jeg har ladet mig fortælle af en underviser på ingeniørstudiet på et
> tidspunkt at f.eks. en TI-89 lommeregner benytter sig af Herons formel
> ifb. udregning af kvadratrødder. Noget med
> Gæt2=0.5*(gæt1+(maxgrænse/gæt1))
>
> Formlen ser ud til at fungere fint med kvardratrødder men ikke med så
> meget andet....

Som andre har sagt, er det her Herons metode. Herons formel er for
arealet af trakanter.

Herons metode generaliseres af Netwons metode:
http://en.wikipedia.org/wiki/Newton%27s_method

Newtons metode finder nulpunkter for funktionen f(x) ved at bruge
formlen

x1 = x0 - f(x0)/f'(x0)

osv, hvor x0 er første gæt, x1 er andet gæt osv.


Til at finde kvadratroden af y, ønsker man at finde x, så x^2-y = 0. Så
f(x) = x^2-y. Dermed er f'(x) = 2x, og Newtons metode siger

x1 = x0 - (x0^2-y)/2x0 = x0 - x0/2 + y/2x0 = x0/2 + y/2x0 = (x0+y/x0)/2

Som man ser, er det præcis det, som Heron's metode siger.

   Torben

---

Den 29/08/11 12.36, Torben Ægidius Mogensen skrev:
> Herons metode generaliseres af Netwons metode:
> http://en.wikipedia.org/wiki/Newton%27s_method

Det kan vist ikke kaldes en generalisering. Ideen bag Newtons metode er
at gætte næste værdi ved hjælp af en differentialkvotient, mens Herons
metode bruger et gennemsnit mellem sidste gæt og et funktionsudtryk, der
vides at ligge på den anden side af den præcise værdi.

At disse to udtryk så falder sammen for kvadratrodsfunktionen er bare
"et tilfælde". Hvis man generaliserede Herons metode til beregning af
kubikrødder, ville udtrykket ikke falde samme med Newtons metodes. Men
Newtons ville konvergere hurtigst.

Mvh. Lars

---

Lars Kongshøj skrev:

> At disse to udtryk så falder sammen for kvadratrodsfunktionen er bare
> "et tilfælde". Hvis man generaliserede Herons metode til beregning af
> kubikrødder, ville udtrykket ikke falde samme med Newtons metodes. Men
> Newtons ville konvergere hurtigst.

.... medmindre den rammer en worst case. Så bliver den aldrig
færdig. Herons formel er skudsikker.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Den 29/08/11 15.49, Bertel Lund Hansen skrev:
> Lars Kongshøj skrev:
>
>> At disse to udtryk så falder sammen for kvadratrodsfunktionen er bare
>> "et tilfælde". Hvis man generaliserede Herons metode til beregning af
>> kubikrødder, ville udtrykket ikke falde samme med Newtons metodes. Men
>> Newtons ville konvergere hurtigst.
>
> ... medmindre den rammer en worst case. Så bliver den aldrig
> færdig.

Kan vel ikke forekomme for kubikrødder.

> Herons formel er skudsikker.

Begge algoritmer kan risikere at støde på en division med 0. Herons dog
kun hvis man starter med en negativ startværdi.

Mvh. Lars

---

Den 29/08/11 16.08, Lars Kongshøj skrev:
> Begge algoritmer kan risikere at støde på en division med 0. Herons dog
> kun hvis man starter med en negativ startværdi.

Sludder.

Ved kvadratrødder er algoritmerne ens, og man kan få division med 0 ved
negativ startværdi.

Ved generalisering af Herons metode til andre rødder kan man også få
division med 0. Så på det punkt er Heron ikke bedre.

/Lars

---

Lars Kongshøj skrev:

> Ved generalisering af Herons metode til andre rødder kan man også få
> division med 0. Så på det punkt er Heron ikke bedre.

Det er da bedre at den falder ud med en fejl end at den bliver
ved i en uendelighed.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

On 29-08-2011 16:08, Lars Kongshøj wrote:
> Den 29/08/11 15.49, Bertel Lund Hansen skrev:
>> Lars Kongshøj skrev:
>>
>>> At disse to udtryk så falder sammen for kvadratrodsfunktionen er bare
>>> "et tilfælde". Hvis man generaliserede Herons metode til beregning af
>>> kubikrødder, ville udtrykket ikke falde samme med Newtons metodes. Men
>>> Newtons ville konvergere hurtigst.
>>
>> ... medmindre den rammer en worst case. Så bliver den aldrig
>> færdig.
>
> Kan vel ikke forekomme for kubikrødder.
>
>> Herons formel er skudsikker.
>
> Begge algoritmer kan risikere at støde på en division med 0. Herons dog
> kun hvis man starter med en negativ startværdi.
>
> Mvh. Lars
Division med 0 er vel kun et problem hvis ens grundmængde er de reele
tal ? Komplekse tal er vel også plausible ?

---

Den 30/08/11 01.30, Pedersen skrev:
> Division med 0 er vel kun et problem hvis ens grundmængde er de reele
> tal ? Komplekse tal er vel også plausible ?

Man kan ikke dividere med 0 i de komplekse tal, eller for den sags skyld
i noget legeme overhovedet.

/Lars

---

Jeg brugte selv Newton iteration kommercielt i 1990 i min Pascal oversætter,
til kvadratrod

Det var på en 68000 cpu (på Palm)
Jeg fandt en god startværdi i en russisk komputerbog.
Laver så 2 stk beregninger i heltal, og nogle flere i flydende tal (IEEE
Single)
Newton lover så at give dobbelt så mange korrekt bits/cifre for hver
gennemløb.


Og her følges så noget bit-venderi...

function FSqrt(X: Real): Real; SysProc FSysSqrt;
var
Exp: Integer;
xX1: Single;
X00,X0,X1: Longint;
ExpO: Boolean;
procedure SqrInt; //X1=1/2 (X1+X0/X1) = 1/2X1 + X0/2/X1
begin
X1:=((X1 shr 1) +((X0 shr 1) div (X1 shr 16)));
X00:=Longint(Exp+127) shl 23+ ((X1 shr 8) and $007FFFFF);
Move(X00,xX1,SizeOf(xX1));
end;

procedure SqrFloat;
begin
xX1:=0.5* (xX1 +X/xX1)
end;

begin
if X<=0.0 then begin FSqrt:=0.0; EXIT end;
ASM move X,X0 end; //Move(X,X0,SizeOf(X0));
X1:=X0;
Exp:=Integer(X1 shr 23)-127;
ExpO:=Odd(Exp);
Exp:=Exp div 2;
X1:=X1 and $007FFFFF + $00800000;
X1:=((X1 shr 8)*$9300 + $6CFF0000); //1th 0.5 < X1 < 1.0 !
SqrInt; <<< 2 stk heltal
SqrInt;
if ExpO then begin
Inc(Exp);
X1:=(X1 shr 16)*46340; //X1:=X1*SQRT(2)/2
if not Odd(X1 shr 31) then begin
Dec(Exp); X1:=X1 shl 1
end;
end;
X0:=Longint(Exp+127) shl 23+ ((X1 shr 8) and $007FFFFF);
ASM move X0,xX1 end; //Move(X0,xX1,SizeOf(xX1));
SqrFloat; <<< 4 stk flydende
SqrFloat;
SqrFloat;
SqrFloat;
FSqrt:=xX1;
end;

Christen Fihl
HSPascal.Fihl.net

---

Christen Fihl wrote:

> Jeg brugte selv Newton iteration kommercielt i 1990 i min Pascal
> oversætter, til kvadratrod

Hmm..
I folkeskolen lærte jeg at udregne kvadratrødder med papir og blyant.

Eksakt udregning, ingen iteration, blot begrænset af hvor mange decimaler
man 'gad' at udregne.

--
Med venlig hilsen
Stig Johansen

---

Og jeg lærte den på den mikro lille Zinclare byg-selv regnemaskine, der
havde +, -+ *, / og så memory
Tog få sekunder at beregne i 3 omløb

Christen

---

Sinclar Cambridge var min første regnemaskine, og byg selv
http://www.vintagecalculators.com/html/sinclair___the_pocket_calculat.html

---

Lars Kongshøj <lars_kongshoj@hotmail.com> writes:

> Den 29/08/11 12.36, Torben Ægidius Mogensen skrev:
>> Herons metode generaliseres af Netwons metode:
>> http://en.wikipedia.org/wiki/Newton%27s_method
>
> Det kan vist ikke kaldes en generalisering. Ideen bag Newtons metode
> er at gætte næste værdi ved hjælp af en differentialkvotient, mens
> Herons metode bruger et gennemsnit mellem sidste gæt og et
> funktionsudtryk, der vides at ligge på den anden side af den præcise
> værdi.
>
> At disse to udtryk så falder sammen for kvadratrodsfunktionen er bare
> "et tilfælde".

Du har vist ikke helt forstået begrebet generalisering. Hvis metode A
falder sammen med metode B i alle de tilfælde, hvor metode B kan bruges,
så er metode A en generalisering af metode B.

> Hvis man generaliserede Herons metode til beregning af kubikrødder,
> ville udtrykket ikke falde samme med Newtons metodes. Men Newtons
> ville konvergere hurtigst.

Man kan generalisere på flere forskellige måder. Du generaliserer, så
vidt jeg kan regne ud, Herons metode til kubikrødder ved at sige

x1 = (x0 + y/x0^2)/2

Newtons metode giver

x1 = x0 - (x0^3-y)/3x0^2 = x0-x0/3 + y/3x0^2 = (2x0+y/x0^2)/3

De er ikke voldsomt forskellige: Newtons metode laver blot et vægtet
gennemsnit. Generelt generaliserer Newtons metode til N'te rod således:

x1 = x0 - (x0^N-y)/(Nx0^(N-1)) = ((N-1)x0 + y/x0^(N-1))/N

hvor du generaliserer til

x1 = (x0 + y/x0^(N-1))/2

Igen er forskellen vægtet eller uvægtet gennemsnit.

   Torben

---

"Christen Fihl" <look_at_HSPascal.fihl.net@nospam.plz> writes:

> Jeg brugte selv Newton iteration kommercielt i 1990 i min Pascal oversætter,
> til kvadratrod
>
> Det var på en 68000 cpu (på Palm)

Newtons metode er fin til det formål, hvis man har hardware support for
division, for der skal laves en division i hver iteration. Men hvis man
ikke har hurtig division, kan andre metoder være hurtigere.

Hvis man har hurtig multiplikation, men ikke hurtig division, kan
tovariabels iteration være hurtigere:

a0 = y
c0 = y-1

a(n+1) = an-an*cn/2
c(n+1) = cn^2(cn-3)/4

Den konvergerer kun, hvis 0<y<3 og hurtigst, hvis y er omkring 1. Men
da mantissen i flydende kommatal er mellem 0.5 og 2, hvis man
normaliserer til en lige eksponent (som halveres ved kvadratrod), er det
ikke noget problem.

Hvis man heller ikke har hardwaresupport for multiplikation, er CORDIC
algoritmen i reglen den hurtigste, da den kun bruger addition,
subtraktion, shift og tabelopslag.

   Torben

---

Lars Kongshøj <lars_kongshoj@hotmail.com> writes:

> Den 30/08/11 10.51, Torben Ægidius Mogensen skrev:
>> Generelt generaliserer Newtons metode til N'te rod således:
>>
>> x1 = x0 - (x0^N-y)/(Nx0^(N-1)) = ((N-1)x0 + y/x0^(N-1))/N
>>
>> hvor du generaliserer til
>>
>> x1 = (x0 + y/x0^(N-1))/2
>>
>> Igen er forskellen vægtet eller uvægtet gennemsnit.
>
> Det har intet med vægtet gennemsnit at gøre. Prøv at skitsere det på
> en graf.
>
> xn+1 er skæringspunktet med x-aksen for tangenten gennem (xn,(f(xn)).

Det er ganske rigtigt, at det er den generelle ide i Newtons metode, men
lige når det gælder den N'te rod, giver det det samme som et vægtet
gennemsnit. Et vægtet gennemsnit af to tal p og q er (a*p+b*q)/(a+b).
I Newtons metode anvendt på den N'te rod er er formlen af denne form med
a=N-1, b=1, p=x0 og q=y/x0^(N-1).

   Torben

---

Stig Johansen <wopr.dk@gmail.com> writes:

> Christen Fihl wrote:
>
>> Jeg brugte selv Newton iteration kommercielt i 1990 i min Pascal
>> oversætter, til kvadratrod
>
> Hmm..
> I folkeskolen lærte jeg at udregne kvadratrødder med papir og blyant.
>
> Eksakt udregning, ingen iteration, blot begrænset af hvor mange decimaler
> man 'gad' at udregne.

Denne metode ("gardinmetoden") kan ret nemt modificeres til en
computeralgoritme, der beregner et bit pr. iteration. Det er nærmest en
binær søgning, men hvor man ikke beregner kvadratet på gættet helt
forfra hver gang, men beregner kvadratet inkrementelt, hver gang gættet
ændres.

Da Herons metode fordobler antallet af korrekte bit pr. iteration, vil
den hurtigt vinde over "gardinmetoden", med mindre division er meget
dyr. Men hvis man skal implementere division i software, kan
"gardinmetoden" dog være hurtigere.

   Torben