Calcular a la suma de 2^1000 sin utilizar BigInt

Question

Como algunos de ustedes pueden notar esta pregunta es problem 16 desde Project Euler. Lo resolví utilizando la nueva característica "bigInt" de C# 4.0, que era bastante sencilla pero que tampoco realmente está aprendiendo todo lo que debería. Supongo que, dado que son 2^1000, habría algún tipo de solución de cambio de bit pero no entiendo exactamente cómo funcionaría.

¿Alguien sabe una forma de calcular 2^1000 sin usar bigint?

Answer 1

Aquí es una manera bastante ingenua para hacerlo en Python usando simplemente una lista (o matriz) de dígitos

digits = [1] 
for n in range(1000): 
    newdigits = [] 
    carry = 0 
    for digit in digits: 
     s = 2*digit+carry 
     carry = s/10 
     s = s%10 
     newdigits.append(s) 
    if carry: 
     newdigits.append(carry) 
    digits = newdigits 
print "".join(map(str,reversed(digits))) 

Answer 2

Podría implicar BigInt usted mismo, lo que podría introducir errores y probablemente resulte en una solución mucho más lenta. Una implementación típica es realizar manualmente las matemáticas usted mismo (en base a cada dígito), con alguna base alta, como números base 2^16.

Answer 3

bien aquí va:

1 << 1000 

En una nota más seria, lo máximo que puede tener en un entero x bits es 1<<x-1. Para calcular realmente 1<<1000 necesitaría un procesador de 1000 bits (técnicamente 1001 bits, pero quién cuenta en este punto). Como eso no es posible, tu única opción es emularlo (y eso es lo que bigint hace).

Answer 4

No hay nada para calcular realidad: 2^1000 = (1000...[994]...000)[Base2]. Es un 'resultado' ya.

Si quiere saber cómo almacenarlo, su máquina no tiene la precisión para almacenar su valor exacto. Por lo tanto, es BigInt, o el doble valor aproximado Math.Pow(2, 1000).

Editar: veo ahora de comentarios que desea es la suma de los dígitos. Vea una de las soluciones.

Answer 5

La parte más difícil de este problema no es el cálculo (simplemente comience con 1 y duplíquelo 1000 veces), pero mostrando la respuesta en decimal. Con esto en mente, es posible que te resulte conceptualmente más fácil realizar el cálculo en alguna forma de representación BCD, como base-1000. Luego realice la multiplicación larga por 2 mil veces. He aquí una solución Python:

def mul2(n): 
    result = [] 
    carry = 0 
    for i in n: 
     i = i * 2 + carry 
     carry = 0 if i < 1000 else 1 
     result.append(i % 1000) 
    if carry: result.append(1) 
    return result 

n = [1] 
for _ in range(1000): 
    n = mul2(n) 

print ''.join('{0:03}'.format(i) for i in reversed(n)).lstrip('0') 

Answer 6

El problema es realmente la conversión de 2^1000 a la base 10. Una forma fácil podría ser la implementación de algún tipo de BCD (decimal codificado en binario) de longitud arbitraria y calcular 2^1000 en BCD. Una matriz de 250 bytes sería más que suficiente. Luego solo tiene que escribir el método para realizar * 2 en un número BCD de longitud arbitraria y llamarlo 1000 veces). Luego, extraer y sumar los dígitos es fácil.

Eso es muy fácil de implementar incluso en lenguajes como C

Answer 7

Voy a tratar de responder sin dar a conocer tanto el código ...

1) utiliza una cadena para mantener el producto

2) Realizar Multiplicación larga (como lo hizo en la escuela)

Prod = "1" 
for n = 1 to 1000 
     carry = 0 
     newprod = "" 
     for i = strlen(prod) - 1 to 0 step - 1 
       digit = int(prod[i]) 
       p = digit * 2 + carry 
       newprod = (p % 10) & newprod // append 
       carry = p/10 
     next 
     if(carry > 0) newprod = carry & newprod 
     prod = newprod 
next 

prod impresión

Bloc de notas-Coding aquí ... así si alguien encuentra errores, corríjalos.

Answer 8

class Program 
{ 
    static void Main(string[] args) 
    { 
     double sum=0; 
     for (int i = 1000; i <=1000; i++) 
     { 
      double pow = Math.Pow(2, i); 
      string power = pow.ToString(); 
      for (int j = 0; j < power.Length; j++) 
      { 
       sum = sum+pow % 10; 
       StringBuilder t = new StringBuilder(pow.ToString()); 
       int len = t.Length; 
       if (len != 1) 
       { 
        t.Remove(len - 1, 1); 
       } 
       pow = Convert.ToDouble(t.ToString()); 
      } 
      Console.WriteLine(sum); 
       Console.WriteLine(); 

     } 
    } 
}