Come lavorare su interi grandi che non si adattano a nessuna delle strutture dati del linguaggio

Question

Sto cercando di risolvere i problemi preliminari di un concorso di programmazione e per 2 dei problemi devo calcolare e stampare alcuni interi molto grandi (come 100 !, 2^100).

Ho anche bisogno di un modo veloce per calcolare i poteri di questi grandi numeri interi. ?

Mi può consigliare alcuni algoritmi o strutture di dati per questo (a proposito, ho letto Interfacce C e la sezione 'arbitraria precisione aritmetica' Implementazioni ma non aiuta per pow())

EDIT: Penso che l'esponenziazione con il metodo di squadratura e il cambio di bit funzionerà per il potere ma ho anche bisogno di un modo veloce per calcolare i fattoriali per questo inte. Grazie.

EDIT2: per coloro che sono interessati;

Trova la lunghezza della stringa di bit più breve che include tutte le stringhe di bit con lunghezza N (scusate il mio inglese, darò un esempio). N < = 10000

Ad esempio, la lunghezza della stringa di bit più breve che include tutte le stringhe di bit di lunghezza 2 (00, 01, 10, 11) è 5 (11001).

La mia soluzione per questo problema è stato 2^n + n - 1. (quindi dovrei calcolare potenze di 2, penso che userò bit-shifting)

altro problema è, date le 2 lunghezze, scopri in quanti modi diversi puoi raggiungere la lunghezza N. Ad esempio, l'input è 10, 2, 3. Quindi devi raggiungere 10 con 2 e 3 (ad esempio, 2 + 2 + 2 + 2 + 2, 2 + 2 + 3 + 3, 3 + 2 + 2 + 3, 3 + 3 + 2 + 2 ...). 1 < = N < 2^63. Calcoleremo l'anwser nel mod 1000000007.

La mia soluzione era, 2x + 3y = N, quindi x = (N - 3y)/2. Per y da 0 a 2 * N/3, se x è un numero intero, allora dovrei calcolare la permutazione generalizzata per questa X e Y, totale + = (x + y)!/(x! * y!).

Answer 1

Per C qualcosa come this funzionerebbe, o rotolerebbe il proprio usando int o array di caratteri, con un punto nell'array che rappresenta una cifra. [1 | 0 | 1] o ['1'|'0'|'1'] per 101, ecc

Answer 2

Per calcolare potenze usano algoritmo dihotomic che utilizza rappresentazione binaria di esponente e riduce il numero di moltiplicazioni risultante. La struttura dati è solo un array di interi

Answer 3

Per pow con numeri interi, exponentiation by squaring

Answer 4

Si potrebbe voler dare un'occhiata a implementazioni di programmi di crittografia (soprattutto GnuPG viene in mente prima). La ragione è che le funzioni crittografiche utilizzano anche interi molto grandi (i cosiddetti Integri MultiPrecision - MPI). Questi MPI sono memorizzati in modo tale che i primi 2 byte indicano come la dimensione del numero intero e gli ultimi byte memorizzano il valore.

GPG è open-source, basta un'occhiata :)

Answer 5

È possibile memorizzare il numero nel formato folowing: numero di cifre e serie di cifre di questo numero. È un modo comune per gestire grandi numeri nei concorsi di programmazione.

Questa è una classe che fornisce la memorizzazione di numeri e moltiplicazione. È possibile aggiungere input e output di numeri che sono banali.

class huge { 
public: 
    int size; 
    int data[1000]; 

    friend void mul(const huge &a, int k, huge &c) { 
     c.size = a.size; 
     int r = 0; 
     for (int i = 0; i < a.size; i++) { 
      r += a.data[i] * k; 
      c.data[i] = r % 10; 
      r = r/10; 
     } 
     if (r > 0) { 
      c.size++; 
      c.data[c.size - 1] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 

    friend void mul(const huge &a, const huge &b, huge &c) { 
     c.size = a.size + b.size; 
     memset(c.data, 0, c.size * sizeof(c.data[0])); 
     for (int i = 0; i < a.size; i++) { 
      int r = 0; 
      for (int j = 0; j < b.size; j++) { 
       r += a.data[i] * b.data[j] + c.data[i + j]; 
       c.data[i + j] = r % 10; 
       r /= 10; 
      } 
      if (r > 0) 
       c.data[i + b.size] = r; 
     } 
     while (c.size > 1 && c.data[c.size - 1] == 0) 
      c.size--; 
    } 
}; 

Answer 6

Utilizzare GMP per gestirli. Ha costruito un supporto fattoriale e grandi poteri, ecc. Ha un'interfaccia C e una C++, tra le altre cose. Avrai bisogno di mpz_t come un tipo che contiene interi molto grandi.

Answer 7

Matematica di base in grado di fare la moltiplicazione di qualsiasi doppia con letto ...

def biginteger(num1, num2): 
result = [] 
lnum1 = len(num1) 
lnum2 = len(num2) 

k = x = remainder = 0 
while len(result) < lnum1: 
    result.append(0) 
for i in range(lnum1, 0, -1): 
    multiplier = int(num1[i - 1]) 
    for j in range(lnum2, 0, -1): 
     temp = (int(num2[j - 1]) * multiplier) + remainder + int(result[k]) 
     result[k] = str(temp % 10) 
     remainder = temp/10 
     k += 1 
    result.append(str(remainder)) 
    if remainder != 0: 
     remainder = 0 
    x += 1 
    k = x 

return ''.join([result[i - 1] for i in range(len(result), 0, -1)]) 

num1 = '37234234234234' 
num2 = '43234234234232' 
print biginteger(num1, num2)