Question Manipulation de grands nombres en C ++?


Quelle est la meilleure façon de gérer de grandes entrées numériques en C ++ (par exemple, 10^100)?

Pour les algorithmes, je passe généralement à Ruby et j'utilise parfois des chaînes.

D'autres bonnes méthodes?


15
2017-09-22 20:31


origine


Réponses:


Il semble que vous cherchiez un moyen d'entrer des nombres de précision arbitraire. Voici deux bibliothèques que vous pouvez utiliser: GMP et MAPM


15
2017-09-22 20:41



Check-out La grande étude de cas en nombres entiers en C ++. Pdf par Owen Astrachan. J'ai trouvé ce fichier extrêmement utile avec l'introduction détaillée et l'implémentation du code. Il n'utilise aucune bibliothèque tierce. J'ai utilisé ceci pour gérer des nombres énormes (du moment que vous avez suffisamment de mémoire pour stocker vector<char>) sans problèmes.


Idée: Il implémente une classe entière de précision arbitraire en stockant big int dans un vector<char>.

vector<char> myDigits; // stores all digits of number

Ensuite, toutes les opérations liées au gros int, y compris <<, >>, +, -, *, ==, <, !=, >, etc., peut être fait en fonction des opérations sur ce char array.


Goût du code: Voici le fichier d'en-tête, vous pouvez trouver son cpp avec des codes dans le fichier pdf.

#include <iostream>
#include <string> // for strings
#include <vector> // for sequence of digits
using namespace std;

class BigInt
{
public:
    BigInt(); // default constructor, value = 0
    BigInt(int); // assign an integer value
    BigInt(const string &); // assign a string
    // may need these in alternative implementation
    // BigInt(const BigInt &); // copy constructor
    // ~BigInt(); // destructor
    // const BigInt & operator = (const BigInt &);
    // assignment operator
    // operators: arithmetic, relational
    const BigInt & operator += (const BigInt &);
    const BigInt & operator -= (const BigInt &);
    const BigInt & operator *= (const BigInt &);
    const BigInt & operator *= (int num);
    string ToString() const; // convert to string
    int ToInt() const; // convert to int
    double ToDouble() const; // convert to double
    // facilitate operators ==, <, << without friends
    bool Equal(const BigInt & rhs) const;
    bool LessThan(const BigInt & rhs) const;
    void Print(ostream & os) const;
private:
    // other helper functions
    bool IsNegative() const; // return true iff number is negative
    bool IsPositive() const; // return true iff number is positive
    int NumDigits() const; // return # digits in number
    int GetDigit(int k) const;
    void AddSigDigit(int value);
    void ChangeDigit(int k, int value);
    void Normalize();
    // private state/instance variables
    enum Sign{positive,negative};
    Sign mySign; // is number positive or negative
    vector<char> myDigits; // stores all digits of number
    int myNumDigits; // stores # of digits of number
};

// free functions
ostream & operator <<(ostream &, const BigInt &);
istream & operator >>(istream &, BigInt &);
BigInt operator +(const BigInt & lhs, const BigInt & rhs);
BigInt operator -(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, const BigInt & rhs);
BigInt operator *(const BigInt & lhs, int num);
BigInt operator *(int num, const BigInt & rhs);
bool operator == (const BigInt & lhs, const BigInt & rhs);
bool operator < (const BigInt & lhs, const BigInt & rhs);
bool operator != (const BigInt & lhs, const BigInt & rhs);
bool operator > (const BigInt & lhs, const BigInt & rhs);
bool operator >= (const BigInt & lhs, const BigInt & rhs);
bool operator <= (const BigInt & lhs, const BigInt & rhs);

7
2017-12-24 04:32



Cherchez-vous comment effectuer des opérations sur les grandes entrées que vous recevez? Il y a un grand nombre entier C ++ bibliothèque (similaire à Java) qui vous permet d'effectuer des opérations arithmétiques ...


6
2017-09-22 20:38



Si vous souhaitez créer votre propre code à cet effet, essayez d’utiliser des chaînes pour stocker de gros nombres ... vous pouvez ensuite créer des opérations de base comme + - / * sur elles ... par exemple -

#include <iostream>

using namespace std;

string add (string &s1, string &s2){
    int carry=0,sum,i;

    string  min=s1,
    max=s2,
    result = "";

    if (s1.length()>s2.length()){
        max = s1;
        min = s2;
    } else {
        max = s2;
        min = s1;
    }

    for (i = min.length()-1; i>=0; i--){
        sum = min[i] + max[i + max.length() - min.length()] + carry - 2*'0';

        carry = sum/10;
        sum %=10;

        result = (char)(sum + '0') + result;
    }

    i = max.length() - min.length()-1;

    while (i>=0){
        sum = max[i] + carry - '0';
        carry = sum/10;
        sum%=10;

        result = (char)(sum + '0') + result;
        i--;
    }

    if (carry!=0){
        result = (char)(carry + '0') + result;
    }       

    return result;
}

int main (){
    string a,b;

    cin >> a >> b;

    cout << add (a,b)<<endl;

    return 0;
}

4
2017-10-30 15:59



en supposant que vous parlez de la saisie des nombres, la double précision vous amènerait à 1.7976931348623157 x 10 ^ 308


3
2017-09-22 20:32



Vous voudrez peut-être regarder gmplib, une bibliothèque de manipulation de nombres de précision arbitraire pour C et C ++


3
2017-09-22 20:39



Si vous voulez que ce soit exact, vous avez besoin d'une bibliothèque pour traiter les gros nombres. Java a BigInt qui sera toujours précis, quel que soit le nombre de chiffres que vous voulez lui donner, et fournit des opérations mathématiques sur ces derniers. Tout le code source est inclus, vous pouvez le transférer, mais ce n'est vraiment pas le genre de chose que C ++ est le meilleur: j'utiliserais un langage basé sur JVM et utiliserais l'une des grandes bibliothèques.

Je ne pense pas que j'utilise le ruby ​​à moins que vous ne vouliez que ce soit lent, et je suppose que puisque vous parlez de C ++, la vitesse est quelque peu une considération de conception.


3
2017-09-22 20:44



Comme d’autres l’ont déjà fait remarquer, il existe diverses bibliothèques de précision bignum / arbitraire en C ++ que vous trouverez probablement utiles. Si la vitesse n'est pas nécessaire, j'ai l'impression que Python et Lisp utilisent tous les deux des bignums par défaut.


2
2017-09-22 20:48