Karatsuba erreur de l'algorithme

Question

je fais une implémentation Karatsuba mais je cette erreur:

java.lang.NumberFormatException: Zero length BigInteger 

    at java.math.BigInteger.<init>(BigInteger.java:296) 
    at java.math.BigInteger.<init>(BigInteger.java:476) 
    at com.Karatsuba.resolve(Karatsuba.java:20) 
    at com.Karatsuba.resolve(Karatsuba.java:26) 
    at com.KaratsubaTest.karatsubaShouldMultiply(KaratsubaTest.java:22) 

Ceci est ma méthode:

BigInteger resolve(BigInteger left, BigInteger right) { 

     String leftS = left.toString(); 
     String rightS = right.toString(); 

     int digits = Math.max(leftS.length(), rightS.length()); 
     digits = (digits/2) + (digits % 2); 

     if (left.compareTo(new BigInteger("10", 10)) == -1 || right.compareTo(new BigInteger("10", 10)) == -1) { 
      return left.multiply(right); 
     } 

     BigInteger firstLeft = new BigInteger(leftS.substring(0, digits)); 
     BigInteger secondLeft = new BigInteger(leftS.substring(firstLeft.toString().length(), leftS.length())); 
     BigInteger firstRight = new BigInteger(rightS.substring(0, digits)); 
     BigInteger secondRight = new BigInteger(rightS.substring(firstRight.toString().length(), rightS.length())); 

     BigInteger z2 = resolve(firstLeft, firstRight); 
     BigInteger z0 = resolve(secondLeft, secondRight); 
     BigInteger z1 = resolve(firstLeft.add(secondLeft), firstRight.add(secondRight)).subtract(z2).subtract(z0); 

     return z2.multiply(BigInteger.valueOf((long) Math.pow(10, 2 * digits))) 
       .add(z1.multiply(BigInteger.valueOf((long) Math.pow(10, digits)))) 
       .add(z0); 
    } 

Je pense qu'il est parce que je suis en utilisant différentes parameteres de longueur pour exemple 123 et 456789. Une idée?

Answer 1

Le NumberFormatException est lancée par new BigInteger(""), ce qui arrive par exemple lorsque left = 10 et right = 100, depuis lors, vous obtenez quelque chose comme ceci:

digits = 2 
firstLeft = new BigInteger("10".substring(0,2)) = new BigInteger("10") 
secondLeft = new BigInteger("10".substring(2,2)) = new BigInteger("") 

Ceci est assez facile à corriger en vérifiant si les chaînes sont vides, et le cas échéant, définissez le nombre à zéro, par exemple comme celui-ci

BigInteger a = fromString(leftS.substring(0, digits)); 
    BigInteger b = fromString(leftS.substring(a.toString().length(),digits)); 
    BigInteger c = fromString(rightS.substring(0, digits)); 
    BigInteger d = fromString(rightS.substring(c.toString().length(), rightS.length())); 

... 

    private BigInteger fromString(String str) { 
     if (str.length() == 0) 
      return BigInteger.ZERO; 
     else 
      return new BigInteger(str); 
    } 

J'ai essayé d'exécuter l'algorithme et bien qu'il fonctionne, il y a encore un problème avec la (mise en œuvre du) a algorithme lui-même. Par exemple, 100 * 100 est signalé comme 1000000. Je pense que cela est lié à la façon dont le fractionnement se produit, mais je n'ai pas réussi à le réparer complètement. Voici quelques réflexions:

Si vous divisez ab = 12345 à m = 3, comme cela arrive dans le code, vous obtenez a = 123 et b = 45. Mais si vous lisez hors de l'article wikipedia (que je l'ai fait), vous avez besoin que

ab = a*10^m+b 

alors que vous avez ab = a*10^(ab.length-m)+b

L'ancien peut être accompli assez facilement en modifiant le code comme ceci:

int l = leftS.length(); 
int r = rightS.length(); 
int m0 = Math.max(l, r); 
int r0 = m0%2; 
int m = (m0/2) + r0; 

... 

BigInteger a = fromString(leftS.substring(0, m-r0)); 
BigInteger b = fromString(leftS.substring(a.toString().length(),l)); 
BigInteger c = fromString(rightS.substring(0, m-r0)); 
BigInteger d = fromString(rightS.substring(c.toString().length(), r)); 

Maintenant 100 * 100 = 10000, mais il y a toujours des problèmes lorsque le nombre de chiffres est différent. Je ne pouvais pas trouver ce qui ne va pas, probablement devrait passer par toutes les étapes de l'algorithme (plutôt que de simplement copier le pseudo-code wikipedia) pour trouver l'erreur. J'espère que cela reste utile! En passant, je pense que l'algorithme fonctionnera probablement mieux avec la base 2, parce que vous pouvez alors faire des décomptes de bits pour les multiplications. Probablement le fractionnement est plus facile (et plus rapide) comme ça aussi. En outre, la récursivité devrait probablement être arrêtée beaucoup plus tôt puisque l'algorithme n'est efficace que pour de très grands nombres. Ce sont bien sûr des optimisations, mais je me suis dit qu'elles valaient la peine d'être mentionnées.