wurzel von bigInteger

[andreas2505]

Hallo,

ich habe hier eine Methode, die die Wurzel von einer BigInteger Zahl ziehen kann. Funktioniert auch soweit aber ich möchte nun, dass nur der Abgerundete Wert ausgegeben wird. Also z.B. sqrt(8) = 2 und nicht wie hier rauskommen würde 3. Kann mir da jemand helfen?

 public static BigInteger sqrt(BigInteger val){
        BigInteger two = BigInteger.valueOf(2);
        BigInteger a = BigInteger.ONE.shiftLeft(val.bitLength()/2);
        BigInteger b;
        do{
            b = val.divide(a);
            a = (a.add(b)).divide(two);
        }
        while (a.subtract(b).abs().compareTo(two) >= 0);
        return a;
    }

 

[Ark]

Ohne dass ich den Code zum Wurzelziehen genau im Kopf habe: Bringt es vielleicht was, aus der do-while-Schleife eine while-Schleife zu machen?

Ark

 

[andreas2505]

hab ich probiert, klappt nicht!

 

[Tharsonius]

Bilde doch vom Ergebnis wieder das Quadrat. Wenn es kleiner als Deine Ausgangszahl ist, dann ist das Ergebnis bereits abgerundet, ansonsten einfach 1 abziehen.

 

[PaulT]

Ich brauchte auch einen sqrt für BigInteger, der niemals aufrundet.
Vermutlich ist der Code nicht optimal effizient, aber allzu langsam scheint er auch nicht zu sein.
Jedenfalls erledigt er den Job.

public static BigInteger sqrt(BigInteger x) {
        if (x.compareTo(BigInteger.ONE) < 0)
            return BigInteger.ZERO.subtract(BigInteger.ONE);
        BigInteger low, hi, tmp, two;
        low = BigInteger.ONE;
        two = hi = tmp = new BigInteger("2");
        while (x.divide(tmp).compareTo(tmp) > 0) {
            low = tmp;
            tmp = tmp.multiply(two);
        }   // verdopple tmp bis es grösser als die Wurzel ist
        if (x.divide(tmp).compareTo(tmp) == 0)
            return tmp;
        while (low.compareTo(tmp) != 0) {
            if (x.divide(tmp).compareTo(tmp) < 0)
                hi = tmp;
            else
                low = tmp;
            tmp = low.add(hi).divide(two);
        }   // Binary Search abwärts
        return tmp;
    }