7fa6f8957f9086bfa73f3ee3e3fb193e
Jeg leder efter den hurtigste måde at afgøre, om en `lang` værdi er et perfekt kvadrat (dvs. at kvadratroden er et andet heltal):


1. Jeg har gjort det på den nemme måde, ved at bruge den indbyggede [`Math.sqrt()`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Math.html#sqrt(double))
funktion, men jeg spekulerer på, om der er en måde at gøre det hurtigere ved at
at begrænse sig til kun at have et heltalsdomæne.
2. Det er upraktisk at vedligeholde en opslagstabel (da der er ca.
231,5 hele tal, hvis kvadrat er mindre end 263).


Her er den meget enkle og ligetil måde jeg gør det på nu:



```
public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}
```

Bemærk: Jeg bruger denne funktion i mange [Projekt Euler](https://projecteuler.net/) problemer. Så ingen andre vil nogensinde skulle vedligeholde denne kode. Og denne form for mikrooptimering kan faktisk gøre en forskel, da en del af udfordringen er at udføre hver algoritme på mindre end et minut, og denne funktion skal kaldes millioner af gange i nogle problemer.




---


Jeg'har prøvet de forskellige løsninger på problemet:


* Efter udtømmende test har jeg fundet ud af, at det ikke er nødvendigt at tilføje `0.5` til resultatet af Math.sqrt(), i hvert fald ikke på min maskine.
* [fast inverse square root](https://en.wikipedia.org/wiki/Fast_inverse_square_root) var hurtigere, men den gav forkerte resultater for n >= 410881. Som foreslået af [BobbyShaftoe](https://stackoverflow.com/users/38426/bobbyshaftoe) kan vi dog bruge FISR-hacket for n < 410881.
* Newton's metode var en god del langsommere end `Math.sqrt()`. Dette skyldes sandsynligvis at `Math.sqrt()` bruger noget der ligner Newton's metode, men implementeret i hardwaren, så det'er meget hurtigere end i Java. Desuden krævede Newton's Method stadig brug af doubler.
* En modificeret Newton's metode, som brugte nogle få tricks, så der kun var tale om heltalsregning, krævede nogle hacks for at undgå overløb (jeg vil have denne funktion til at fungere med alle positive 64-bit signerede heltal), og den var stadig langsommere end `Math.sqrt()`.
* Binary chop var endnu langsommere. Det giver mening, fordi det binære hak i gennemsnit vil kræve 16 gennemløb for at finde kvadratroden af et 64-bit tal.
* Ifølge John's test er det hurtigere at bruge `or`-statements i C++ end at bruge en `switch`, men i Java og C# synes der ikke at være nogen forskel mellem `or` og `switch`.
* Jeg prøvede også at lave en opslagstabel (som et privat statisk array med 64 boolske værdier). Så ville jeg i stedet for enten switch eller `eller`-erklæring bare sige `if(lookup[(int)(n&0x3F)]]) { test } else return false;`. Til min overraskelse var dette (kun en lille smule) langsommere. Det skyldes, at [array bound's kontrolleres i Java](https://stackoverflow.com/questions/299079/why-is-this-code-with-several-or-statements-slightly-faster-than-using-a-lookup-t#299205).

Hurtigste måde at afgøre, om et helt tals kvadratrod er et helt tal
===================================================================


answer-id.com
2021.43
Jeg tænkte på de forfærdelige tider jeg har tilbragt på kurset i numerisk analyse.


Og så husker jeg, at der var denne funktion, der cirkulerede rundt i 'nettet fra Quake Source code:



```
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}
```

Som grundlæggende beregner en kvadratrod, ved hjælp af Newton's tilnærmelsesfunktion (kan ikke huske det nøjagtige navn).


Det burde være brugbart og måske endda hurtigere, det er fra et af de fænomenale id software spil!


Det er skrevet i C++, men det burde ikke være for svært at genbruge den samme teknik i Java, når man først har forstået ideen:


Jeg fandt den oprindeligt på: <http://www.codemaestro.com/reviews/9>


Newton's metode forklaret på wikipedia: [http://en.wikipedia.org/wiki/Newton%27s\_method](https://en.wikipedia.org/wiki/Newton%27s_method)


Du kan følge linket for at få mere forklaring på hvordan det virker, men hvis du er ligeglad, så er det nogenlunde hvad jeg husker fra at læse bloggen og fra at have taget kurset Numerical Analysis:


* `* (long*) &y` er dybest set en hurtig konverter-til-lang-funktion, så heltalsoperationer kan anvendes på de rå bytes.
* linjen `0x5f3759df - (i >> 1);` er en forudberegnet seed-værdi for approksimeringsfunktionen.
* `* (float*) &i` konverterer værdien tilbage til flydende komma.
* linjen `y = y * ( threehalfs - ( x2 * y * y * y ) )` ` itererer værdien over funktionen igen.


Tilnærmelsesfunktionen giver mere præcise værdier, jo mere man itererer funktionen over resultatet. I Quake's tilfælde er én iteration "god nok", men hvis det ikke var'for dig... så kan du tilføje så mange iterationer som du har brug for.


Dette skulle være hurtigere, fordi det reducerer antallet af divisionsoperationer, der udføres i naiv kvadratrodning, ned til en simpel dividere med 2 (faktisk en `* 0.5F` multiplikationsoperation) og erstatter det med et par faste antal multiplikationsoperationer i stedet.


Hvis du laver et binært hak for at forsøge at finde den rigtige kvadratrod, kan du ret nemt se, om den værdi, du har fået, er tæt nok på til at kunne sige det:



```
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
```

Så efter at have beregnet `n^2`, er mulighederne følgende:


* `n^2 = target`: udført, returnerer sandt
* `n^2 + 2n + 1 > target > n^2` : du'er tæt på, men det'er ikke perfekt: return false
* `n^2 - 2n + 1 < target < n^2` : ditto
* `target < n^2 - 2n + 1` : binært hak på et lavere `n`
* `target > n^2 + 2n + 1` : binært hak på et højere `n`


(Undskyld, men her bruges `n` som dit nuværende gæt og `target` som parameter. Undskyld for forvirringen!)


Jeg ved ikke, om dette vil være hurtigere eller ej, men det er et forsøg værd.


EDIT: Det binære hak behøver ikke at tage hele området af hele tal med, heller ikke `(2^x)^2 = 2^(2x)`, så når du først har fundet den øverste indstillede bit i dit target (hvilket kan gøres med et bit-twiddling-trick; jeg har glemt præcis hvordan) kan du hurtigt få en række potentielle svar. Husk på, at en naiv binær chop stadig kun vil tage op til 31 eller 32 iterationer.


Hvis du ønsker hastighed, og da dine heltal er af begrænset størrelse, formoder jeg, at den hurtigste måde ville være at (a) opdele parametrene efter størrelse (f.eks. i kategorier efter største bit-sæt) og derefter kontrollere værdien mod et array af perfekte kvadrater inden for dette område.

