Fehler Implementierung des Karatsuba-Algorithmus mit BigInteger

Ich versuche, den Karatsuba-Algorithmus mit Java zu implementieren, der BigInteger verklagt, ich habe alle Schritte befolgt, aber ich bekomme nicht das richtige Ergebnis, was mich verrückt macht.Fehler Implementierung des Karatsuba-Algorithmus mit BigInteger

Hier ist mein Code:

public BigInteger karatsuba(BigInteger a, BigInteger b, int base) { 
    if (a.compareTo(BigInteger.TEN) == -1 || b.compareTo(BigInteger.TEN) == -1) { 
     return a.multiply(b); 
    } 

    /* calculates the size of the numbers */ 
    int tam = a.toString().length(); 
    int mitad = tam/2; 


    BigInteger a1 = (a.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger a0 = (a.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    BigInteger b1 = (b.divide(BigInteger.valueOf((long) Math.pow(base, mitad)))); 
    BigInteger b0 = (b.remainder(BigInteger.valueOf((long) Math.pow(base, mitad)))); 

    /* 3 calls made to numbers approximately half the size */ 
    BigInteger t1 = karatsuba(a1, b1, base); 
    BigInteger t2 = karatsuba(a0, b0, base); 
    BigInteger t3 = karatsuba(a1.add(a0), b1.add(b0), base); 

    BigInteger aux1 = (t1.multiply(BigInteger.valueOf((long)Math.pow(base, tam)))); 
    BigInteger aux2 = t1.subtract(t2); 
    BigInteger aux4 = aux2.subtract(t3); 
    BigInteger aux3 = aux4.multiply(BigInteger.valueOf((long) Math.pow(base,mitad)).add(t2)); 

    return aux1.add(aux3); 

}

ich den Code mit dem folgenden Eintrag getestet: karatsuba(new BigInteger("1252",new BigInteger("532") , 10) während das korrekte Ergebnis 666.064, ich 2.212.864 !!! bekommen. und ich debuggte, die Überraschung war, dass, wenn der Ausführungsfluss bei der return-Anweisung ankommt, das Programm nicht aufhört, sondern auf die -Anweisung geht.

Also ich weiß nicht, was ich falsch mache. Jede Hilfe wäre sehr willkommen.

Quelle

2017-02-04 shadow

nicht ein JAVA-Coder so kann ich falsch sein, aber: 1. 'Math.pow (Basis, mitad)' ist verdächtig, da das Ergebnis ist "float", die höchstwahrscheinlich nicht das Ergebnis in passen wird. 2. Karatsuba ist rekursiv Also müssen alle Rekursionsebenen aufgerufen werden, bevor die endgültige Rückkehr wirklich zurückkehrt ... Da ich keine große Ganzzahl verwende, bin ich nicht sicher, ob 'a.divide, a.remainder 'tatsächlich tut, was Sie wollen. Wenn es wirklich Division und Modul ist, dann ist das falsch, da Sie die interne Repräsentation von bigint nicht durch die Nummer selbst teilen müssen, sonst würden Sie bigint '/,%' für bigint '*' verwenden, was Wahnsinn ist. – Spektre

Dies ist wahrscheinlich nicht dein Problem (da 1252 und 532 gut im Bereich von Nicht-Big-Ganzzahlen liegen), aber "Math.pow" ist sehr unwahrscheinlich, dass es für große Ganzzahlen richtig funktioniert. Dies ist wahrscheinlich auch nicht Ihr Problem (da Sie mit 'base' auf 10 setzen), aber 'a.toString(). Length()' ist unwahrscheinlich, die richtige Größe zu berechnen, es sei denn 'base' ist 10. –

btw hier [Fast bignum square computation] (http://stackoverflow.com/q/18465326/2521214) Sie können am Ende meine arbnum Karatsuba-Implementierung in C++ finden (arbnum ist willkürlich mantisse float, so dass Sie den Exponenten für bigints ignorieren können) – Spektre

Hier ist Karatsuba algorithm implementation von der Princeton University "Einführung in die Programmierung in Java" Kurs:

public static BigInteger karatsuba(BigInteger x, BigInteger y) { 

    // cutoff to brute force 
    int n = Math.max(x.bitLength(), y.bitLength()); 
    if (n <= 10) return x.multiply(y); 

    // number of bits divided by 2, rounded up 
    n = (n/2) + (n % 2); 

    final BigInteger b = x.shiftRight(n); 
    final BigInteger a = x.subtract(b.shiftLeft(n)); 
    final BigInteger d = y.shiftRight(n); 
    final BigInteger c = y.subtract(d.shiftLeft(n)); 

    // compute sub-expressions 
    final BigInteger ac = karatsuba(a, c); 
    final BigInteger bd = karatsuba(b, d); 
    final BigInteger abcd = karatsuba(a.add(b), c.add(d)); 

    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(n)).add(bd.shiftLeft(2 * n)); 
    }

Ich glaube, Sie kühn es verwenden können.

Quelle

2017-03-11 09:46:36 Nolequen

Fehler Implementierung des Karatsuba-Algorithmus mit BigInteger

Antwort

Verwandte Themen