Karatsuba Entier Échec de la multiplication avec un défaut de segmentation

Question

Lorsque j'exécute le programme, il se bloque avec un défaut de segmentation. En outre, lorsque je débogue le code dans IDE codeblocks, je suis également incapable de le déboguer. Le programme se bloque avant même que le débogage ne commence. Je ne suis pas capable de comprendre le problème. Toute aide serait appréciée. Merci!!

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

// Method to make strings of equal length 
int makeEqualLength(string& fnum,string& snum){ 
    int l1 = fnum.length(); 
    int l2 = snum.length(); 
    if(l1>l2){ 
     int d = l1-l2; 
     while(d>0){ 
      snum = '0' + snum; 
      d--; 
     } 
     return l1; 
    } 
    else if(l2>l1){ 
     int d = l2-l1; 
     while(d>0){ 
      fnum = '0' + fnum; 
      d--; 
     } 
     return l2; 
    } 
    else 
     return l1; 
} 

int singleDigitMultiplication(string& fnum,string& snum){ 
    return ((fnum[0] -'0')*(snum[0] -'0')); 
} 

string addStrings(string& s1,string& s2){ 
    int length = makeEqualLength(s1,s2); 
    int carry = 0; 
    string result; 
    for(int i=length-1;i>=0;i--){ 
    int fd = s1[i]-'0'; 
    int sd = s2[i]-'0'; 
    int sum = (fd+sd+carry)%10+'0'; 
    carry = (fd+sd+carry)/10; 
    result = (char)sum + result; 
    } 
    result = (char)carry + result; 
    return result; 
} 

long int multiplyByKaratsubaMethod(string fnum,string snum){ 

    int length = makeEqualLength(fnum,snum); 
    if(length==0) return 0; 
    if(length==1) return singleDigitMultiplication(fnum,snum); 

    int fh = length/2; 
    int sh = length - fh; 

    string Xl = fnum.substr(0,fh); 
    string Xr = fnum.substr(fh,sh); 
    string Yl = snum.substr(0,fh); 
    string Yr = snum.substr(fh,sh); 

    long int P1 = multiplyByKaratsubaMethod(Xl,Yl); 
    long int P3 = multiplyByKaratsubaMethod(Xr,Yr); 
    long int P2 = multiplyByKaratsubaMethod(addStrings(Xl,Xr),addStrings(Yl,Yr)) - P1-P3; 

    return (P1*pow(10,length) + P2*pow(10,length/2) + P3); 
} 


int main() 
{ 
    string firstNum = "62"; 
    string secondNum = "465"; 
    long int result = multiplyByKaratsubaMethod(firstNum,secondNum); 
    cout << result << endl; 
    return 0; 
} 

Answer 1

Il y a trois problèmes graves dans votre code:

1. result = (char)carry + result; ne fonctionne pas.
   Le report a une valeur comprise entre 0 (0 * 0) et 8 (9 * 9). Il doit être converti en la valeur ASCII correspondante:
   result = (char)(carry + '0') + result;. Cela conduit au problème suivant: Le report est même inséré si 0. Il manque un if:
   if (carry/* != 0*/) result = (char)(carry + '0') + result;. Après la correction des deux premiers problèmes et le test à nouveau, le dépassement de pile se produit toujours. Donc, j'ai comparé votre algorithme avec un autre que j'ai trouvé par google:
   Divide and Conquer | Set 4 (Karatsuba algorithm for fast multiplication)
   (et peut-être était votre origine parce qu'il semble très similaire). Sans creuser plus profond, je fixe ce qui ressemblait à une simple erreur de transfert: (. Je l'ai remplacé length par 2 * sh et length/2 par sh comme je l'ai vu dans le code googlé)
   return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
   Cela est devenu évident pour moi de voir dans le débogueur cette longueur peut avoir valeurs impaires de sorte que sh et length/2 sont des valeurs distinctes.

Ensuite, votre programme est devenu opérationnel.

j'ai changé la fonction main() pour le tester un peu plus difficile:

#include <cmath> 
#include <iostream> 
#include <string> 

using namespace std; 

string intToStr(int i) 
{ 
    string text; 
    do { 
    text.insert(0, 1, i % 10 + '0'); 
    i /= 10; 
    } while (i); 
    return text; 
} 

// Method to make strings of equal length 
int makeEqualLength(string &fnum, string &snum) 
{ 
    int l1 = (int)fnum.length(); 
    int l2 = (int)snum.length(); 
    return l1 < l2 
    ? (fnum.insert(0, l2 - l1, '0'), l2) 
    : (snum.insert(0, l1 - l2, '0'), l1); 
} 

int singleDigitMultiplication(const string& fnum, const string& snum) 
{ 
    return ((fnum[0] - '0') * (snum[0] - '0')); 
} 

string addStrings(string& s1, string& s2) 
{ 
    int length = makeEqualLength(s1, s2); 
    int carry = 0; 
    string result; 
    for (int i = length - 1; i >= 0; --i) { 
    int fd = s1[i] - '0'; 
    int sd = s2[i] - '0'; 
    int sum = (fd + sd + carry) % 10 + '0'; 
    carry = (fd + sd + carry)/10; 
    result.insert(0, 1, (char)sum); 
    } 
    if (carry) result.insert(0, 1, (char)(carry + '0')); 
    return result; 
} 

long int multiplyByKaratsubaMethod(string fnum, string snum) 
{ 
    int length = makeEqualLength(fnum, snum); 
    if (length == 0) return 0; 
    if (length == 1) return singleDigitMultiplication(fnum, snum); 

    int fh = length/2; 
    int sh = length - fh; 

    string Xl = fnum.substr(0, fh); 
    string Xr = fnum.substr(fh, sh); 
    string Yl = snum.substr(0, fh); 
    string Yr = snum.substr(fh, sh); 

    long int P1 = multiplyByKaratsubaMethod(Xl, Yl); 
    long int P3 = multiplyByKaratsubaMethod(Xr, Yr); 
    long int P2 
    = multiplyByKaratsubaMethod(addStrings(Xl, Xr), addStrings(Yl, Yr)) 
    - P1 - P3; 
    return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3; 
} 

int main() 
{ 
    int nErrors = 0; 
    for (int i = 0; i < 1000; i += 3) { 
    for (int j = 0; j < 1000; j += 3) { 
     long int result 
     = multiplyByKaratsubaMethod(intToStr(i), intToStr(j)); 
     bool ok = result == i * j; 
     cout << i << " * " << j << " = " << result 
     << (ok ? " OK." : " ERROR!") << endl; 
     nErrors += !ok; 
    } 
    } 
    cout << nErrors << " error(s)." << endl; 
    return 0; 
} 

Remarques sur les changements que je l'ai fait:

1. En ce qui concerne std bibliothèque: S'il vous plaît, ne mélangez pas les en-têtes avec ".h" et sans. Chaque en-tête de la bibliothèque std est disponible en "sans suffixe". (L'en-tête avec ".h" est soit en-tête C ou démodé.) Les en-têtes de la bibliothèque C ont été adaptés à C++. Ils ont l'ancien nom avec le préfixe "c" et sans le suffixe ".h". Par conséquent, j'ai remplacé #include <math.h> par #include <cmath>.

2. Je n'ai pas pu résister à faire un peu plus court makeEqualLength().

3. S'il vous plaît, notez, que beaucoup de méthodes std utiliser std::size_t au lieu de int ou unsigned. std::size_t a une largeur appropriée pour effectuer un arithmétique de pointé et de pointeur de tableau, c'est-à-dire qu'il a une "largeur de mot machine". Je croyais depuis longtemps que int et unsigned devrait avoir "largeur de mot machine" aussi et ne se soucie pas de size_t. Lorsque nous avons changé dans Visual Studio de x86 (32 bits) en x64 (64 bits), j'ai appris à tort que j'avais tort: ​​std::size_t est maintenant 64 bits mais int et unsigned sont toujours 32 bits.(MS VC++ n'est pas une exception.Les autres fournisseurs de compilateurs (mais pas tous) le font de la même manière.)
   J'ai inséré des distributions de type C pour supprimer les avertissements de la sortie du compilateur. De tels lancers pour supprimer des avertissements (que vous utilisiez des distributions C ou mieux les distributions C++) doivent toujours être utilisés avec précaution et doivent être compris comme une confirmation: Cher compilateur. Je vois que vous avez des inquiétudes mais je (crois à) savoir et vous assurer que cela devrait fonctionner correctement.

4. Je ne suis pas sûr de votre intention d'utiliser long int dans certains endroits. (Probablement, vous avez transféré ce code de la source d'origine sans se soucier de.) Comme vous le savez sûrement, la taille réelle de tous les types int peut différer pour correspondre à la meilleure performance de la plate-forme cible. Je travaille sur un PC Intel avec Windows 10, en utilisant Visual Studio. sizeof (int) == sizeof (long int) (32 bits). Ceci est indépendant si je compile le code x86 (32 bits) ou le code x64 (64 bits). La même chose est vraie pour gcc (sur cygwin dans mon cas) ainsi que sur n'importe quel Intel-PC avec Linux (AFAIK). Pour un type plus grand que int, vous devez choisir long long int.

Je l'ai fait la séance d'échantillon dans Cygwin sur Windows 10 (64 bits):

$ g++ -std=c++11 -o karatsuba karatsuba.cc 

$ ./karatsuba 
0 * 0 = 0 OK. 
0 * 3 = 0 OK. 
0 * 6 = 0 OK. 

etc., etc.

999 * 993 = 992007 OK. 
999 * 996 = 995004 OK. 
999 * 999 = 998001 OK. 
0 error(s). 

$