---

Hejsa,


Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt maaange
gange og der bliver den til en flaskehals.
Nogen der kender til en hurtigere metode at lave kvadratrod på end
Math.sqrt() ? Det behøver ikke have så høj nøjagtighed som den i Math,
men det er afgørende at metoden er hurtigere.

MVH
Kim

---

Kim Schulz wrote:
> Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt maaange
> gange og der bliver den til en flaskehals.
> Nogen der kender til en hurtigere metode at lave kvadratrod på end
> Math.sqrt() ? Det behøver ikke have så høj nøjagtighed som den i Math,
> men det er afgørende at metoden er hurtigere.

Principielt afhænger mulighederne af hvilken JVM
du bruger.

Men på en gængs platform som SUN JVM Win32 x86 er det håbløst.

Math.sqrt ender op som eksekvering af en enkelt maskin
instruktion.

Jeg prøvede at lave en soft sqrt iterativ algoritme og kunne
konstatere at Math.sqrt er hurtigere end *en* iteration.

Så medmindre du sidder på en platform med en rigtig dårlig
implementation af Math.sqrt, så opgiv det.

Arne

---

On Sun, 14 May 2006 10:43:52 -0400
Arne Vajhøj <arne@vajhoej.dk> wrote:

> Kim Schulz wrote:
> > Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt
> > maaange gange og der bliver den til en flaskehals.
> > Nogen der kender til en hurtigere metode at lave kvadratrod på end
> > Math.sqrt() ? Det behøver ikke have så høj nøjagtighed som den i
> > Math, men det er afgørende at metoden er hurtigere.
>
> Principielt afhænger mulighederne af hvilken JVM
> du bruger.
>
> Men på en gængs platform som SUN JVM Win32 x86 er det håbløst.
>
> Math.sqrt ender op som eksekvering af en enkelt maskin
> instruktion.
>
> Jeg prøvede at lave en soft sqrt iterativ algoritme og kunne
> konstatere at Math.sqrt er hurtigere end *en* iteration.
>
> Så medmindre du sidder på en platform med en rigtig dårlig
> implementation af Math.sqrt, så opgiv det.


jeg sidder på sun JVM på windows, linux og solaris. Jeg kan ikke forstå
at du siger at den er så hurtig som den er, for hvis jeg kalder et
eksternt C++ lib fra java så kan det gøres hurtigere. Denne løsninger
bare ikke så køn efter min mening.

---

---

---

Michael Zedeler <michael@zedeler.dk> writes:

> Når jeg afprøver den, ser det ud til at dens køretid er o(x), hvilket
> trods alt giver en del multiplikationer og divisioner. Er det ikke
> hurtigere at Taylorudvikle i en række punkter, slå dem op og hælde dem
> igennem et Taylorpolynomium?

Så¨vidt jeg husker er det Newtons algoritme, som konvergerer meget
hurtigt.

Taylorudvikling kræver en del forarbejde for hvert punkt man ønsker at
taylorudvikle om (og tallene bliver svjh let store).

--
Thorbjørn Ravn Andersen

---

---

Arne Vajhøj <arne@vajhoej.dk> writes:

> Umiddelbart vil jeg mene at den:
> konvergerer hurtigere
> kræver færre beregning
> er mere stabil med hensyn til udgangspunkt

http://www.library.cornell.edu/nr/cbookcpdf.html

Kapitel 5 - har en del om udregning af diverse udtryk.

Desværre er min gamle lærebog ikke online, hvilket er ærgeligt for den
er på dansk.

--
Thorbjørn Ravn Andersen

---

Thorbjørn Ravn Andersen wrote:
> Arne Vajhøj <arne@vajhoej.dk> writes:
>> Umiddelbart vil jeg mene at den:
>> konvergerer hurtigere
>> kræver færre beregning
>> er mere stabil med hensyn til udgangspunkt
>
> http://www.library.cornell.edu/nr/cbookcpdf.html
>
> Kapitel 5 - har en del om udregning af diverse udtryk.

Kvadratrod er faktisk i kapitel 20 ...

ARne

---

---

Arne Vajhøj <arne@vajhoej.dk> writes:

> Win32 SUN JVM 1.5.0

Gider du også prøve med 1.6'eren? Den skulle være endnu mere aggresiv
med inlining?
--
Thorbjørn Ravn Andersen

---

Thorbjørn Ravn Andersen wrote:
> Arne Vajhøj <arne@vajhoej.dk> writes:
>> Win32 SUN JVM 1.5.0
>
> Gider du også prøve med 1.6'eren? Den skulle være endnu mere aggresiv
> med inlining?

-client

Math.sqrt: 141
Newton: 875
Table lookup: 125
Taylor scaled: 4203
Taylor scaled precalculated: 2125
Taylor multi point precalculated: 1828
Newton inverse: 1063
Newton bit guess: 1297
Newton inverse bit guess: 1343
Newton bit guess fixed iterations: 1078
Newton inverse bit guess fixed iterations: 1141

-server

Math.sqrt: 125
Newton: 1016
Table lookup: 140
Taylor scaled: 4735
Taylor scaled precalculated: 2719
Taylor multi point precalculated: 2281
Newton inverse: 969
Newton bit guess: 1109
Newton inverse bit guess: 906
Newton bit guess fixed iterations: 797
Newton inverse bit guess fixed iterations: 672

så ja - den ser hurtigere ud.

Arne

---

Kim Schulz <kim@schulz.dk> writes:

> Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt maaange
> gange og der bliver den til en flaskehals.

Hvordan har du afgjort det?

Hvordan ser koden ud?
--
Thorbjørn Ravn Andersen

---

On 14 May 2006 17:22:36 +0200
nospam0000@gmail.com (Thorbjørn Ravn Andersen) wrote:

> Kim Schulz <kim@schulz.dk> writes:
>
> > Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt
> > maaange gange og der bliver den til en flaskehals.
>
> Hvordan har du afgjort det?

profiling af system gennem hele udviklingsperioden.

> Hvordan ser koden ud?

lidt svært at lige give et eksempel på da det er del at et ret
omfattende system.

---

Kim Schulz <kim@schulz.dk> writes:

> > > Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt
> > > maaange gange og der bliver den til en flaskehals.
> >
> > Hvordan har du afgjort det?
>
> profiling af system gennem hele udviklingsperioden.
>
> > Hvordan ser koden ud?
>
> lidt svært at lige give et eksempel på da det er del at et ret
> omfattende system.

Jamen så bliver svaret derefter.

Hvis du skal bruge kvadratrødderne i afstandsberegninger (pythagoras) og blot skal
sammenligne med noget andet, så overvej at lade være med at tage
kvadratroden, men blot den absolutte værdi.

Hvis det er et begrænset interval kan du eventuelt forudberegne for N
punkter i intervallet, og så blot tage det forudberegnede resultat for
det nærmeste punkt til det aktuelle interval.

--
Thorbjørn Ravn Andersen

---

Thorbjørn Ravn Andersen wrote:
> Kim Schulz <kim@schulz.dk> writes:
>
>>lidt svært at lige give et eksempel på da det er del at et ret
>>omfattende system.
>
> Hvis du skal bruge kvadratrødderne i afstandsberegninger (pythagoras) og blot skal
> sammenligne med noget andet, så overvej at lade være med at tage
> kvadratroden, men blot den absolutte værdi.

Hvis det er til noget som har med geometri at gøre, er der en masse
genveje, hvis man primært benytter "kvadranser", frem for aftande. Det
er også en mulighed.

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

Kim Schulz wrote:
> Sidder med nogle beregninger nu hvor Math.sqrt() bliver kaldt maaange
> gange og der bliver den til en flaskehals.

Hvad vil maaange gange sige? Har du overvejet om der måske er urimeligt
mange kald?

> Nogen der kender til en hurtigere metode at lave kvadratrod på end
> Math.sqrt() ? Det behøver ikke have så høj nøjagtighed som den i Math,
> men det er afgørende at metoden er hurtigere.

Hvilken størrelsenorden har tallene?
Hvilken nøjagtighed er påkrævet?

Hvis svarende på ovenstående spørgemål er "tilstrækkeligt moderate", kan
en pænt hurtig metode være at bruge tallet som index til en array med
forudberegnede resultater.

F.eks. er det næppe noget større problem at have en array med 10
millioner elementer, hvilket giver plads til 7-cifrede input tal.
Selvfølgelig tager det lidt tid at forudberegne resultaterne, men
derefter er hastigheden svær at slå.