Multiplication de 2 nombres à 64 chiffres en C++

Question

J'ai implémenté l'algorithme de multiplication de karatsuba. Je veux l'améliorer de cette façon que je peux multiplier 2 nombres à 64 chiffres mais je ne sais pas comment faire. On m'a donné un indice que les deux nombres contiennent un nombre de chiffres qui est une puissance de deux, mais cela ne me suggère rien. Pourriez-vous donner d'autres indices? Soit un indice mathématique ou un indice d'amélioration de l'algorithme.

#include <iostream> 
#include <math.h> 
using namespace std; 

int getLength(long long value); 
long long multiply(long long x, long long y); 

int getLength(long long value) 
{ 
    int counter = 0; 
    while (value != 0) 
    { 
     counter++; 
     value /= 10; 
    } 
    return counter; 
} 

long long multiply(long long x, long long y) 
{ 
    int xLength = getLength(x); 
    int yLength = getLength(y); 

    // the bigger of the two lengths 
    int N = (int)(fmax(xLength, yLength)); 

    // if the max length is small it's faster to just flat out multiply the two nums 
    if (N < 10) 
     return x * y; 

    //max length divided and rounded up 
    N = (N/2) + (N % 2); 

    long long multiplier = pow(10, N); 

    long long b = x/multiplier; 
    long long a = x - (b * multiplier); 
    long long d = y/multiplier; 
    long long c = y - (d * N); 

    long long z0 = multiply(a, c); 
    long long z1 = multiply(a + b, c + d); 
    long long z2 = multiply(b, d); 


    return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N))); 

} 

int main() 
{ 
    long long a; 
    long long b; 
    cin >> a; 
    cout << '\n'; 
    cin >> b; 
    cout << '\n' << multiply(a, b) << endl; 
    return 0; 
} 

Answer 1

Voici un indice:.

(A + kB) * (C + kD) = AC + k(BC + AD) + k^2(BD) 

Cela aide si k est une puissance de la base que vous souhaitez conserver vos numéros dans Par exemple, si k est 1'000'000'000 et votre les nombres sont base-10, alors les multiplications par k sont faites en déplaçant simplement les nombres autour (en ajoutant des zéros.)

De toute façon, pensez à briser vos nombres à 64 chiffres en deux parties, chacun 32 chiffres et faites le calcul comme le au dessus. Pour calculer AC, BC, AD et BD, vous multipliez une paire de nombres à 32 chiffres qui peut être effectuée de manière similaire.

Étant donné que votre nombre de chiffres est une puissance de deux, vous pouvez continuer à casser vos numéros de moitié jusqu'à ce que vous obtenez à la taille de nombre qui sont faciles à gérer (par exemple les numéros 1 chiffres.)

BTW, on ne sait pas de votre question de savoir si vous parlez de 64 bits ou de 64 chiffres décimaux. Si tout ce que vous cherchez est de multiplier les nombres de 64 bits, faites simplement ceci:

// I haven't actually run this code, so... 

typedef unsigned long long u64; 

u64 high32 (u64 x) {return x >> 32;} 
u64 low32 (u64 x) {return x & 0xFFFFFFFF;} 

u64 add_with_carry (u64 a, u64 b, u64 * carry) 
{ 
    u64 result = a + b; 
    if (result < a) // and/or b? 
     *carry = 1; 
    return result; 
} 

void mul (u64 a, u64 b, u64 * result_low, u64 * result_high) 
{ 
    u64 a0 = low32(a), a1 = high32(a); 
    u64 b0 = low32(b), b1 = high32(b); 

    u64 a0b0 = a0 * b0; 
    u64 a0b1 = a0 * b1; 
    u64 a1b0 = a1 * b0; 
    u64 a1b1 = a1 * b1; 

    u64 c0 = 0, c1 = 0; 
    u64 mid_part = add_with_carry(a0b1, a1b0, &c1); 

    *result_low = add_with_carry(a0b0, (low32(mid_part) << 32, &c0); 
    *result_high = high32(mid_part) + a1b1 + (c1 << 32) + c0; // this won't overflow 
} 

Cette implémentation est la même idée que celle décrite ci-dessus. Comme en C/C++ standard, le plus grand nombre de bits significatifs que nous pouvons avoir dans le résultat d'une multiplication est 64, alors nous ne pouvons multiplier que deux nombres de 32 bits à la fois. C'est ce que nous faisons ici.

Le résultat final sera 128 bits, que nous retournons dans deux numéros 64 bits non signés. Nous faisons une multiplication de 64 bits par 64 bits, en faisant 4 multiplications 32 bits et quelques ajouts.

Comme une note de côté, c'est l'un de ces rares cas où la rédaction de c'est l'assemblage est généralement waaaaay plus facile que C. Par exemple, dans l'assemblage x64, c'est littéralement deux mov s, quatre mul s, quatre add s, et adc s (et c'est juste en utilisant les instructions CPU de base.)

Answer 2

Pour appliquer Karatsuba ou toute autre multiplication sur l'arithmétique de largeur de bits inférieure, vous devez diviser votre nombre en «chiffres» plus petits. Avant toute autre chose dont vous avez besoin d'accéder à ces « chiffres » alors voici comment faire:

vous avez obtenu le numéro 1234 et que vous voulez le diviser à 10^1 chiffres si

1234 = 1*1000 + 2*100 + 3*10 + 4 

vous pouvez obtenir les chiffres comme celui-ci :

x=1234; 
a0=x%10; x/=10; // 4 
a1=x%10; x/=10; // 3 
a2=x%10; x/=10; // 2 
a3=x%10; x/=10; // 1 

si vous voulez 10^2 chiffres puis:

x=1234; 
a0=x%100; x/=100; // 34 
a1=x%100; x/=100; // 12 

Maintenant, le problème est que pour ce faire, vous devez avoir la division sur le nombre entier que vous n'avez pas. Si vous avez le numéro sous forme de chaîne, c'est facile à faire, mais supposons que ce n'est pas le cas.Les ordinateurs sont basés sur des calculs binaires il est donc une bonne idée d'utiliser la puissance de 2 comme base pour « chiffres » donc:

x = 1234 = 0100 1101 0010 bin 

Maintenant, si nous voulons avoir par exemple 2^4=16 chiffres de base puis:

a0=x%16; x/=16; // 0010 
a1=x%16; x/=16; // 1101 
a2=x%16; x/=16; // 0100 

maintenant, si vous vous rendez compte que la division par puissance de 2 est tout simplement passer peu à droite et le reste peut être exprimé en puis:

a0=x&15; x>>=4; // 0010 
a1=x&15; x>>=4; // 1101 
a2=x&15; x>>=4; // 0100 

Le décalage de bits peut être empilée à une largeur de bit nombres donc maintenant vous avez tout ce dont vous avez besoin. Mais ce n'est pas tout si vous sélectionnez comme « chiffres », par exemple 2^8 qui est BYTE alors vous pouvez utiliser des pointeurs au lieu par exemple:

DWORD x=0x12345678; // 32 bit number 
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x 

a0=db[0]; // 0x78 
a1=db[1]; // 0x56 
a2=db[2]; // 0x34 
a3=db[3]; // 0x12 

vous pouvez donc accéder directement aux chiffres ou reconstruire le x de chiffres:

DWORD x; // 32 bit number 
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x 
db[0]=0x78; 
db[1]=0x56; 
db[2]=0x34; 
db[3]=0x12; 
// here x should be 0x12345678 

Attention, la commande dépend de la première commande de la plate-forme MSB ou LSB. Maintenant vous pouvez appliquer la multiplication. Par exemple 32 * 32 = 64 bits fait sur la multiplication de 16 bits est fait comme à l'approche naïve O(n^2):

x(a0+a1<<16) * y(b0+b1<<16) = a0*b0 + a0*b1<<16 + a1*b0<<16 + a1*b1<<32 

Où a0, a1, b0, b1 sont les chiffres des opérandes. Notez que le résultat de chaque multiplication ai*bj est à 2 chiffres, vous devez donc le diviser en chiffres et le stocker sur le chiffre résultant du décalage. Méfiez-vous que l'ajout peut provoquer un débordement vers des chiffres plus élevés. Pour gérer cela, vous devez soit utiliser au moins deux fois la largeur de l'arithmétique pour ajouter (16 * 16 bit mul -> 32bit ajouter) ou utiliser le drapeau de transport. Malheureusement, en utilisant l'assemblage en C++, vous n'avez pas accès au drapeau Carry. Heureusement, il peut être simulé voir:

Et maintenant, vous pouvez construire votre Karatsuba ou plus avancés multiplications pour plus d'informations voir:

• Fast bignum square computation