Cómo trabajar en enteros grandes que no encajan en ninguna de las estructuras de datos del lenguaje

Question

Estoy tratando de resolver los problemas preliminares de un concurso de programación y para 2 de los problemas tengo que calcular e imprimir algunos enteros muy grandes (como 100 !, 2^100).

También necesito una forma rápida de calcular las potencias de estos enteros grandes. ?

¿Me puede aconsejar algunos algoritmos o estructuras de datos de este (por cierto, leí C Interfaces y sección de 'precisión arbitraria aritmética' Implementaciones pero no resuelve el problema de pow())

EDIT: Creo la exponenciación mediante el método de cuadratura y el cambio de bit funcionará para obtener energía, pero también necesito una forma rápida de calcular los factores para esta etapa. Gracias.

EDIT2: Para aquellos que estén interesados;

Encuentra la longitud de cadena de bits más corta que incluye todas las cadenas de bits con longitud N (lo siento por mi inglés, daré un ejemplo). N < = 10000

Por ejemplo, la más corta longitud de cadena de bits que incluye todas las cadenas de bits de longitud 2 (00, 01, 10, 11) es 5 (11001).

Mi solución para este problema fue de 2^n + n - 1 (por lo que debe calcular potencias de 2, creo que voy a utilizar bits de desplazamiento)

Otro problema es que, dadas las longitudes de 2, encuentre cómo de cuántas maneras diferentes puede alcanzar la longitud N. Por ejemplo, la entrada es 10, 2, 3. Entonces debe llegar a 10 con 2 y 3 (por ejemplo, 2 + 2 + 2 + 2 + 2, 2) + 2 + 3 + 3, 3 + 2 + 2 + 3, 3 + 3 + 2 + 2 ...). 1 < = N < 2^63. Calcularemos el guión en mod 1000000007.

Mi solución fue, 2x + 3y = N, entonces x = (N - 3y)/2. Para y de 0 a 2 * N/3, si x es un número entero, entonces debería calcular la permutación generalizada para esta X e Y, total + = (x + y)./(x! * y!).

Answer 1

Para C algo así como this funcionaría, o haga su propio uso de arrays int o char, con un punto en la matriz que representa un dígito. [1 | 0 | 1] o ['1'|'0'|'1'] para 101, etc.

Answer 2

Para calcular potencias utilizan algoritmo dihotomic que utiliza representación binaria de exponente y reduce resultante número de multiplicaciones. estructura de datos es una matriz de enteros

Answer 3

Para pow con números enteros, exponentiation by squaring

Answer 4

Es posible que desee echar un vistazo en las implementaciones de programas criptográficos (especialmente GnuPG viene a la mente en primer lugar). La razón es que las funciones criptográficas también hacen uso de números enteros muy grandes (llamados Enteros MultiPrecisión - MPI). Estos MPI se almacenan de tal manera que los primeros 2 bytes indican cómo el tamaño del entero y los últimos bytes almacenan el valor.

GPG es de código abierto, acaba de echar un vistazo a él :)

Answer 5

Puede almacenar un número en el formato folowing: número de dígitos y variedad de dígitos de este número. Es una forma común de lidiar con grandes números en concursos de programación.

Aquí hay una clase que proporciona almacenamiento de números y multiplicación. Se pueden agregar entradas y salidas de números que son triviales.

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

Use GMP para manejar estos. Ha construido soporte factorial y grandes potencias, etc. Tiene una interfaz C y una interfaz C++, entre otras cosas. Necesitará mpz_t como un tipo que contiene números enteros muy grandes.

Answer 7

matemáticas básicas pueden hacer la multiplicación de cualquier doble con doble ...

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)