Schneller Quadratzahltest für beliebig große natürliche Zahlen

[pinkysbrain]

Ich bin auf der Suche nach einem guten Algorithmus um große Zahlen (zB BigInteger) darauf zu testen, dass sie eine Quadratzahl sind.
Ich habe auch schon eine Methode gebaut die für beliebig große Zahlen funktioniert.
Allerdings ist diese nicht besonders schnell (immerhin 6 Sekunden für eine Zahl mit 100000 Stellen).

Bisher teste ich erst ob die letzte Ziffer gleich 0, 1, 4, 5, 6 oder 9 ist.
Dann benutze ich eine Methode um Wurzeln beliebig genau auf dem Papier zu ziehen.

Das ist mir nur alles nicht schnell genug und finde keine vernünftigen anderen Ansätze.

 

[geqoo]

Aus einem anderen Thread: Wie wärs mit dem Ansatz?

public boolean isSquare(int n) {
   int squareRoot = (int) Math.sqrt(n);
   return squareRoot * squareRoot == n;
}

 

[DrZoidberg]

Ich hab mal etwas rumprobiert und bin jetzt bei 35ms für eine 100,000 stellige Zahl. Allerdings ist das der Durchschnittswert. Bei ca. 3% aller Zahlen benötigt er mehr als 1 Sekunde.
Es finden zwei Tests statt. Der erste relativ schnelle Test kann schon mal bei 97% aller Zahlen sofort erkennen, dass das keine Quadratzahl sein kann.
Die restlichen 3% müssen dann intensiver betrachtet werden mittels dem Heron Verfahren.

import java.math.BigInteger;
import java.util.Random;

class Square {
    private static Random rand = new Random();
    
    public static BigInteger sqrt(BigInteger n) {
        BigInteger ZERO = BigInteger.ZERO;
        BigInteger TWO = new BigInteger("2");
        BigInteger guess = n.shiftRight((n.bitLength()-1)/2);
        BigInteger oldGuess = n;
        while(guess.subtract(oldGuess).abs().compareTo(ZERO) > 0) {
            oldGuess = guess;
            guess = guess.add(n.divide(guess)).divide(TWO);
        }
        return guess;
    }
    
    public static boolean isSquare(BigInteger n) {
        int base = 39600;
        int mod = n.mod(new BigInteger(""+base)).intValue();
        boolean maybeSq = false;
        for(int i = 0; i < base; i++) {
            int sq = i*base+mod;
            int sqrt = (int)Math.sqrt(sq);
            if(sqrt*sqrt == sq) {
                maybeSq = true;
                break;
            }
        }
        if(!maybeSq) return false; 
        BigInteger sqrt = sqrt(n);
        return sqrt.multiply(sqrt).equals(n);
    }
    
    public static BigInteger randomBI(int digits) {
        char[] ca = new char[digits];
        for(int i = 0; i < digits; i++) ca[i] = (char)(rand.nextInt(10) + '0');
        return new BigInteger(new String(ca));
    }
    
    public static void main(String[] args) {
        BigInteger a = randomBI(50000);
        BigInteger sq = a.multiply(a);
        long start = System.nanoTime();
        boolean isSquare = isSquare(sq);
        long end = System.nanoTime();
        double time = (end - start)/1e6;
        System.out.println("isSquare = " + isSquare);
        System.out.println("time = " + time + "ms");
        
        double totalTime = 0;
        double worstTime = 0;
        int tries = 100;
        for(int i = 0; i < tries; i++) {
            sq = randomBI(100000);
            start = System.nanoTime();
            isSquare = isSquare(sq);
            end = System.nanoTime();
            time = (end - start)/1e6;
            if(time > worstTime) worstTime = time;
            totalTime += time;
        }
        System.out.println("worst time = " + worstTime + "ms");
        System.out.println("total time = " + totalTime + "ms");
        System.out.println("average time = " + (totalTime/tries) + "ms");
    }
}