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):
Math.sqrt()
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.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 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:
0.5
til resultatet af Math.sqrt(), i hvert fald ikke på min maskine.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.Math.sqrt()
.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
.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.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
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.0x5f3759df - (i >> 1);
er en forudberegnet seed-værdi for approksimeringsfunktionen.* (float*) &i
konverterer værdien tilbage til flydende komma.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 sandtn^2 + 2n + 1 > target > n^2
: du'er tæt på, men det'er ikke perfekt: return falsen^2 - 2n + 1 < target < n^2
: dittotarget < 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.