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

Newton-Raphsons metod? Konvergerar kvadratiskt ... Bara att hitta en bra startpunkt så behövs inte många iterationer.

EDIT: såg att den nämdes i wiki-artikeln du hänvisade till

EDIT2: http://mathcentral.uregina.ca/RR/dat...grzesina1.html
Jag skummade bara igenom artikeln, kanske intressant?

Tack för länken. Skummat igenom. Jag vet inte hur lätt det blir att omsätta i riktigt snabb kod, men jag kommer nog göra ett försök.

Hur kul det än var att försöka skriva en egen riktigt snabb faktoriserande algoritm så börjar jag inse att det finns alltid någon jäkel som redan på 70-80talet som skrivit kod med betydligt bättre tidskomplexitet och smartare lösningar.

Nåja. Nobelpriset verkar få vänta ett tag till. Men jag har iaf lärt mig en hel del under resans gång.

Nu vet jag ju inte vilken algoritm du använder för att hitta roten ( eller om det är en "perfekt rot" ). Men om du använder Newton-Raphsons (NR) metod så bör du kunna hitta ett hyffsat startvärde bara genom att ta "halva tiopotensen" av talet. Jag tror inte att NR divergerar för någon startpunkt när funktionen är sqrt(x). Det bör inte krävas många iterationer då för att hitta roten (även om det inte är det du är ute efter).

Blir nästan sugen på att undersöka möjligheterna själv!
Testa programutvecklings-forumet, dom kanske har stött på samma problem som du!

EDIT: har du funderat något på primtalsfaktorisering? Kanske går att hitta en snabb algoritm den vägen? Jag skulle tro att det är långsammare än NR men det kan finnas en chans ...

EDIT2: Hur många klockcykler ( eller tid ) tar det för dig att bestämma om en rot är ett heltal eller ej?
Matlab klarar att räkna ut sqrt(1e14) på 0.016660 s.
sqrt(0.14e14) tar 0.000075 s.
Tror att det blir ganska svårt att slå dom tiderna ...

Det finns ju lite fler problem, använder han flyttal för att representera siffrorna och sedan utför beräkningar på dem finns det ju en hel del man måste ta hänsyn till.

Well.. Tack för alla intressanta svar

Från början var jag tveksam på att tråden skulle få ett enda svar.

Nu är jag ganska trött på sqrt():en. Newton verkar hittills snabbast (med någon mindre modifiering) för mina heltal.

Rutinen för faktorisering som jag har utgått från är:

http://en.wikipedia.org/wiki/Dixon%2...ization_method

Nu leker jag mest med olika strukturer för att se om man snabbare kan avgöra när man har lämpliga värden för att bilda x^2 = y^2 + N, utan att först fylla en en hel matris med potenserna och sedan lösa ut lämpliga 2-potenser med gauss-eliminering. (Jag vill inte gå direkt in på quadratic sieve).

Dixon-rutinen är ganska okomplicerad när man lekt ett tag med den och känns som ett bra startläge.

T.ex. förlorar man väldigt mycket tid på att fylla hela matrisen (kanske 1000x1000 för stora tal att faktorisera). Tänk om man får en bra träff nästan direkt? Funderar på om man kan använda nåt sökträd för att lösa ut efter hand.

Oh well.. För icke kryptologi-intresserade måste detta låta fruktansvärt tråkigt. Men men

Ja, självklart ... dessa tider gäller ju för min gamla dator. Vad jag menade var att det blir nog svårt att slå hastigheten på Matlabs sqrt-algoritm. Jag tror att den är ganska nära optimal.

Trams... de flesta som är helt ointresserade av den här typen av problem klickar nog inte ens på en sån här tråd. Verkar vara en intressant metod. Får nog ta och göra mig en egen implementation någon dag när programmeringssuget kommer smygande.