Come implementare big int in C ++

Question

Vorrei implementare una grande classe int in C ++ come esercizio di programmazione & # 8212; una classe che può gestire numeri più grandi di una lunga int. So che ci sono già diverse implementazioni open source là fuori, ma mi piacerebbe scriverne una mia. Sto cercando di capire quale sia l'approccio giusto.

Comprendo che la strategia generale è ottenere il numero come una stringa, quindi suddividerlo in numeri più piccoli (ad esempio cifre singole) e posizionarli in un array. A questo punto dovrebbe essere relativamente semplice implementare i vari operatori di confronto. La mia principale preoccupazione è come implementare cose come l'addizione e la moltiplicazione.

Sto cercando un approccio generale e consigli rispetto al vero codice di lavoro.

Answer 1

Cose da considerare per una grande classe int:

1. Operatori matematici: +, -, /, *,% Non dimenticare che la tua classe potrebbe trovarsi su entrambi i lati del operatore, che gli operatori possono essere incatenato, quello degli operandi potrebbe essere un int, float, double, ecc.

2. Operatori I / O: > > ;, < < Questo è dove capisci come farlo correttamente crea la tua classe dall'input dell'utente e come formattarla anche per l'output.

3. Conversioni / Cast: capire quali tipi / classi il tuo grande int la classe dovrebbe essere convertibile in, e come gestire correttamente il conversione. Un breve elenco sarebbe include double e float e può include int (con limiti appropriati controllo) e complesso (assumendolo può gestire l'intervallo).

Answer 2

Una sfida divertente. :)

Presumo che tu voglia interi di lunghezza arbitraria. Suggerisco il seguente approccio:

Considera la natura binaria del tipo di dati " int " ;. Pensa all'utilizzo di semplici operazioni binarie per emulare ciò che fanno i circuiti nella tua CPU quando aggiungono cose. Nel caso in cui tu sia interessato in modo più approfondito, prendi in considerazione la lettura di questo articolo di Wikipedia su semi-additivi e full-adders . Farai qualcosa di simile, ma puoi scendere a un livello così basso - ma essendo pigro, ho pensato di rinunciare e trovare una soluzione ancora più semplice.

Ma prima di entrare nei dettagli algoritmici sull'aggiunta, sottrazione, moltiplicazione, troviamo una struttura di dati. Un modo semplice, ovviamente, è quello di archiviare le cose in uno std :: vector.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Potresti voler considerare se vuoi creare il vettore di una dimensione fissa e se preallocare. Il motivo è che per diverse operazioni, dovrai passare attraverso ogni elemento del vettore - O (n). Potresti voler sapere a mano quanto complessa sarà un'operazione e un n fisso fa proprio questo.

Ma ora alcuni algoritmi sull'operare sui numeri. Potresti farlo a livello logico, ma useremo quella potenza magica della CPU per calcolare i risultati. Ma ciò che prenderemo il posto dell'illustrazione logica di Half- e FullAdders è il modo in cui tratta. Ad esempio, considera come implementeresti + = operatore . Per ogni numero in BigInt & Lt; & Gt; :: value_, dovresti aggiungerli e vedere se il risultato produce una qualche forma di carry. Non lo faremo in modo un po 'saggio, ma faremo affidamento sulla natura del nostro BaseType (sia esso lungo o int o corto o altro): trabocca.

Sicuramente, se aggiungi due numeri, il risultato deve essere maggiore di quello maggiore, giusto? In caso contrario, il risultato è traboccato.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

L'altra operazione aritmetica diventa analoga. Cavolo, potresti anche usare gli stl-functors std :: plus e std :: minus, std :: times e std :: divides, ..., ma attenzione al carry. :) Puoi anche implementare la moltiplicazione e la divisione usando gli operatori più e meno, ma è molto lento, perché ricalcolerebbe i risultati già calcolati nelle chiamate precedenti a più e meno in ogni iterazione. Esistono molti buoni algoritmi disponibili per questo semplice compito, use wikipedia o sul web.

E ovviamente, dovresti implementare operatori standard come operator<< (sposta ogni valore in value_ a sinistra per n bit, iniziando da value_.size()-1 ... oh e ricorda il carry :), <= > - puoi anche ottimizzare un po 'qui, controllando prima il numero approssimativo di cifre con operator<. E così via. Quindi rendi utile la tua classe, diventando amico std :: ostream size().

Spero che questo approccio sia utile!

Answer 3

C'è una sezione completa su questo: [The Art of Computer Programming, vol.2: Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. Puoi trovare altro materiale interessante nel capitolo 4, Aritmetica.

Se davvero non vuoi guardare un'altra implementazione, hai considerato cosa stai imparando? Ci sono innumerevoli errori da fare e scoprirli è istruttivo e anche pericoloso. Esistono anche sfide nell'individuare importanti economie computazionali e disporre di strutture di archiviazione adeguate per evitare gravi problemi di prestazioni.

Una domanda di sfida per te: come intendi testare la tua implementazione e come proponi di dimostrare che l'aritmetica è corretta?

Potresti voler testare un'altra implementazione (senza guardare come lo fa), ma ci vorrà molto di più per essere in grado di generalizzare senza aspettarsi un livello lancinante di test. Non dimenticare di prendere in considerazione le modalità di errore (problemi di memoria esaurita, stack eccessivo, esecuzione troppo lunga, ecc.).

Buon divertimento!

Answer 4

l'aggiunta dovrebbe probabilmente essere eseguita nell'algoritmo del tempo lineare standard
ma per moltiplicazioni potresti provare http://en.wikipedia.org/wiki/Karatsuba_algorithm

Answer 5

Una volta che hai le cifre del numero in un array, puoi fare addizioni e moltiplicazioni esattamente come faresti a mano.

Answer 6

Non dimenticare che non è necessario limitarsi a 0-9 come cifre, ovvero utilizzare byte come cifre (0-255) e si può ancora fare l'aritmetica a lancetta lunga come si farebbe con le cifre decimali. Potresti persino usare un array di long.

Answer 7

Non sono convinto che usare una stringa sia la strada giusta da percorrere - anche se non ho mai scritto il codice da solo, penso che usare una matrice di un tipo numerico di base potrebbe essere una soluzione migliore. L'idea è di estendere semplicemente ciò che hai già allo stesso modo in cui la CPU estende un singolo bit in un numero intero.

Ad esempio, se hai una struttura

typedef struct {
    int high, low;
} BiggerInt;

È quindi possibile eseguire manualmente operazioni native su ciascuna delle " cifre " (alto e basso, in questo caso), tenendo conto delle condizioni di overflow:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

È un po 'un esempio semplicistico, ma dovrebbe essere abbastanza ovvio come estenderlo a una struttura che avesse un numero variabile di qualunque classe numerica di base che stai usando.

Answer 8

Come altri hanno detto, fallo alla vecchia maniera, ma stai lontano dal fare tutto nella base 10. Suggerirei di fare tutto nella base 65536 e di conservare le cose in una serie di long.

Answer 9

Usa gli algoritmi appresi dal 1 ° al 4 ° grado.
Inizia con la colonna uni, poi le decine e così via.

Answer 10

Se l'architettura di destinazione supporta la rappresentazione dei numeri BCD (codice binario decimale), è possibile ottenere un supporto hardware per la moltiplicazione / aggiunta a mano libera che è necessario eseguire. Fare in modo che il compilatore emetta istruzioni BCD è qualcosa su cui dovrai leggere ...

I chip Motorola serie 68K avevano questo. Non che io sia amaro o niente.

Answer 11

Il mio inizio sarebbe quello di avere una matrice di numeri interi di dimensioni arbitrarie, usando 31 bit e 32n come overflow.

L'operazione di avvio sarebbe ADD, quindi MAKE-NEGATIVE, usando il complemento di 2. Dopodiché, la sottrazione scorre in modo banale e, una volta aggiunto / sub, tutto il resto è fattibile.

Probabilmente ci sono approcci più sofisticati. Ma questo sarebbe l'approccio ingenuo dalla logica digitale.

Answer 12

Potrei provare a implementare qualcosa del genere:

http://www.docjar.org/html/ API / java / math / BigInteger.java.html

Avresti bisogno solo di 4 bit per una singola cifra da 0 a 9

Quindi un valore Int consentirebbe fino a 8 cifre ciascuno. Ho deciso di rimanere con una serie di caratteri, quindi uso il doppio della memoria, ma per me viene utilizzato solo 1 volta.

Inoltre, quando si memorizzano tutte le cifre in un singolo int, ciò lo complica eccessivamente e, se non altro, può addirittura rallentarlo.

Non ho alcun test di velocità ma guardando la versione java di BigInteger sembra che stia facendo un sacco di lavoro.

Per me faccio quanto segue

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

Answer 13

sottrai 48 dalla tua stringa di numeri interi e stampa per ottenere il numero di grandi cifre. quindi eseguire l'operazione matematica di base.    altrimenti fornirò una soluzione completa.