Karatsuba algorithme sans usage de BigInteger

Enfin, après plusieurs heures de pensée, j'ai trouvé la solution correcte: xxx pré>

Je ne peux pas expliquer pourquoi n ne peut pas être étrange fort>, mais juste Maintenant, la multiplication fonctionne correctement pour le tas de tests que j'ai écrit. Je vais expliquer ce comportement dès que je découvrirai. P>

Mise à jour: strong> Je prends des algorithmes: conception et analyse, cours de la partie 1 sur Coursera et posté une question sur ce comportement. Voici une réponse de Andrew Patton: P>

Comme mentionné ailleurs, la clé avec rupture des entrées consiste à s'assurer que B et D est la même longueur, de sorte que A et C ont la même puissance de 10 coefficients. Quoi que ce pouvoir devienne votre N / 2; ... Donc, la valeur du n dans 10 ^ N n'est pas réellement la longueur totale de vos entrées, mais plutôt N / 2 * 2. p> BlockQuote>

Donc, dans le cas d'un numéro de 3 chiffres Vous suivez Exemple: P>

n = 3;   
n/2 = 2;
n != n/2 * 2;

/** Function to multiply two numbers **/
    public long multiply(long x, long y)
    {
        int size1 = getSize(x);
        int size2 = getSize(y);
        /** Maximum of lengths of number **/
        int N = Math.max(size1, size2);
        /** for small values directly multiply **/        
        if (N < 10)
            return x * y;
        /** max length divided, rounded up **/    
        N = (N / 2) + (N % 2);    
        /** multiplier **/
        long m = (long)Math.pow(10, N);

        /** compute sub expressions **/        
        long b = x / m;
        long a = x - (b * m);
        long d = y / m;
        long c = y - (d * N);
        /** compute sub expressions **/
        long z0 = multiply(a, c);
        long z1 = multiply(a + b, c + d);
        long z2 = multiply(b, d);          

        return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * N)));        
    }
    /** Function to calculate length or number of digits in a number **/
    public int getSize(long num)
    {
        int ctr = 0;
        while (num != 0)
        {
            ctr++;
            num /= 10;
        }
        return ctr;
    }
That is realization for BigInteger:http://www.nayuki.io/res/karatsuba-multiplication/KaratsubaMultiplication.java

Au lieu de arrondi avec Math.Round (), j'ajoute 1 à la valeur de la taille d'entrée (la minute du nombre de chiffres dans X ou Y), si la taille d'entrée est impair. Par exemple, si x = 127 & y = 162, la taille d'entrée est ensuite 3. Incrément de 1 pour le faire 4. ALORN, A = X / MATH.POW (10, INPUT_SIZE / 2) = 1. B = x% Math .pow (10, INPUT_SIZE / 2) = 27. De même, C = 1 et D = 62. Maintenant, si nous calculons X * Y = (AC) * Math.Pow (10, INPUT_SIZE) + (AD + BC) * Math.pow (10, INPUT_SIZE / 2) + BD; Cela donne la bonne réponse. N'oubliez pas que nous incrémentons la taille d'entrée de 1 seulement quand c'est étrange. La mise en œuvre complète est ici - https://github.com/ Parag-vijay / data_structures / blob / maître / java / karatsubamultiplication.java

Voici la bonne implémente à l'aide de LIPS:

import java.math.BigInteger;
import java.util.Scanner;

/**
 * x=5678 y=1234
 * 
 * a=56,b=78
 * 
 * c=12,d=34
 * 
 * step 0 = m = n/2 + n%2
 * 
 * step 1 = a*c
 * 
 * step 2 = b*d
 * 
 * step 3 = (a + b)*(c + d)
 * 
 * step 4 = 3) - 2) - 1)
 * 
 * step 5 = 1)*pow(10, m*2) + 2) + 4)*pow(10, m)
 *
 */
public class Karatsuba {

    public static void main(String[] args) {
        BigInteger x, y;
        try (Scanner s = new Scanner(System.in)) {
            x = s.nextBigInteger();
            y = s.nextBigInteger();
        }
        BigInteger result = karatsuba(x, y);
        System.out.println(result);
    }

    private static BigInteger karatsuba(BigInteger x, BigInteger y) {
        if (x.compareTo(BigInteger.valueOf(10)) < 0 && y.compareTo(BigInteger.valueOf(10)) < 0)
            return x.multiply(y);

        int n = Math.max(x.toString().length(), y.toString().length());
        int m = n / 2 + n % 2;

        BigInteger[] a_b = x.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger a = a_b[0];
        BigInteger b = a_b[1];
        BigInteger[] c_d = y.divideAndRemainder(BigInteger.valueOf(10).pow(m));
        BigInteger c = c_d[0];
        BigInteger d = c_d[1];

        BigInteger step1 = karatsuba(a, c);
        BigInteger step2 = karatsuba(b, d);
        BigInteger step3 = karatsuba(a.add(b), c.add(d));
        BigInteger step4 = step3.subtract(step2).subtract(step1);
        BigInteger step5 = step1.multiply(BigInteger.valueOf(10).pow(m * 2)).add(step2)
                .add(step4.multiply(BigInteger.valueOf(10).pow(m)));
        return step5;
    }

}