Herons formel
Pedersen
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 ?
Lars Kongshøj
> 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
> 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 ;-)
Pedersen
> Den 28/08/11 21.46, Pedersen skrev:
>> tidspunkt at f.eks. en TI-89 lommeregner benytter sig af Herons formel
>> 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å
>> anvendes i trigonometrien) og så lige kvardratrødder siden den kan
>> 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
> 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 :)
Lars Kongshøj
> 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
Pedersen
> Den 28/08/11 22.27, Pedersen skrev:
>> �benbart en st�rrelse :)
>
> Man halverer jo ikke, man tager gennemsnittet af to st�rrelser.
>
>> ... og fatter stadig ikke hvorfor Herons metode
>
> Tankegangen kan ogs� bruges ved udvikling af andre iterative algoritmer.
> Tag et kursus i numerisk analyse.
>
>> 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 :)
Torben Ægidius Mogensen
> 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
Lars Kongshøj
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
Bertel Lund Hansen
> 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.
Lars Kongshøj
> 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
Lars Kongshøj
> 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
Bertel Lund Hansen
> 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.
Pedersen
tal ? Komplekse tal er vel også plausible ?
Lars Kongshøj
> 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
Christen Fihl
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
Torben Ægidius Mogensen
> 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
Torben Ægidius Mogensen
> 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
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)).
/Lars
Christen Fihl
68000 var dejlig, da den kunne dividere 32 bit med 16
Christen
Torben Ægidius Mogensen
> 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
Lars Kongshøj
Det er jo mere en strid om ord. De gælder om på passende vis at vælge en
værdi mellem to værdier, sådan at algoritmen giver en hurtig konvergens.
Det vil jeg ikke kalde et vægtet gennemsnit, da valget ikke er baseret
på en gennemsnitsbetragtning, men ideen at vælge en tangents skæringspunkt.
Mvh. Lars
Stig Johansen
> 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
Torben �gidius Mogensen
> 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
Christen Fihl
havde +, -+ *, / og så memory
Tog få sekunder at beregne i 3 omløb
Christen
Christen Fihl
http://www.vintagecalculators.com/html/sinclair___the_pocket_calculat.html