Snabb rutin för att upptäcka om Sqrt() är möjlig utan att svaret innehåller decimaler

Som en del av ett större projektet försöker jag hitta en rutin som inte hittar Sqrt() utan endast ser om det blir ett exakt värde utan decimaler.

Exempel:
Sqrt(81) = 9 -> Funktionen ger SANT
Sqrt(14) = 3.74165-> Funktionen ger FALSKT
Sqrt(100) = 10 -> Funktionen ger SANT

Hastighet är av absolut största vikt. Finns det någon lämplig snabb algoritm?

Om det är programmering så borde du väl kunna ta roten ur ditt tal och sen ta ditt svar minus heltalsdelen av ditt svar och kolla om det blir 0?

Rooten ur är en hyfsat långsam funktion så jag tror inte att han vill använda den

Helt rätt

Eftersom jag inte behöver varken värde (eller decimaler) hade jag hoppats att man kunde uppnå en högre hastighet.

Ok, jag tvivlar på att det finns ett enklare sätt. Vad jag kan förstå så vill man kolla om ett tal har 2 och endast 2 lika primtalsfaktorer. Jag vet inte hur det skulle gå till, men kanske någon annan som vet.

Projektet gäller optimering av en existerande faktoriseringsmetod. Så hade jag löst det enligt det sättet hade projektet redan varit klart

En enkel algoritm för att undersöka om ett heltal N är en perfekt kvadrat, dvs att sqrt(N) är ett heltal, som endast kräver heltalsaritmetik:
Algoritmen är ju dock rätt långsam O(sqrt(N)) vilket kanske inte räcker för din applikation. Annars kan du kolla in källkoden till GMP-biblioteket och se hur de har löst det.

Va? Nej, kvadratroten ur 81 är 9, men 9 är inte en primtalsfaktor för det.

Känns betydligt långsammare än den nuvarande jag använder:

http://en.wikipedia.org/wiki/Integer_square_root

Dock räknar den faktiskt ut värdet på roten. Vilket inte är nödvändigt. Hade hoppats att det fanns fina knep för att öka beräkningshastigheten om värdet var oviktigt. Exempelvis använder denna en väldigt massa div, vilket inte ger speciellt bra prestanda.

Kolla in hur de har löst det i källkoden till GMP-biblioteket: http://www.gmplib.org. De verkar ha ett bra sätt för att sålla bort tal: http://gmplib.org/manual/Perfect-Square-Algorithm.html.

Mycket bra länk. Skall se om en ny implementation kan påverka exekveringstiden på programmet nämnvärt

Det finns bara en smart lösning till detta om hastighet är av största vikt men det kostar minne. Generera alla talen på förhand och vips så är kostnaden bara O(1) för kollen.