Calcola fino alla somma di 2^1000 senza utilizzare BigInt

Question

Come alcuni di voi potrebbero notare questa domanda è problem 16 da Project Euler. L'ho risolto usando la nuova funzionalità "bigInt" di C# 4.0 che era abbastanza semplice ma che non apprende davvero tutto ciò che dovrei. Presumo che dal momento che è 2^1000 ci sarebbero alcune soluzioni di bit shifting ma non riesco a capire come funzionerebbe esattamente.

Qualcuno sa un modo per calcolare 2^1000 senza utilizzare bigint?

Answer 1

Ecco un modo piuttosto ingenuo di farlo in python solo utilizzando una lista (o array) di cifre

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

Potresti implorare BigInt da solo, potenzialmente introducendo bug e probabili risultati in una soluzione molto più lenta. Un'implementazione tipica è quella di eseguire manualmente i calcoli manualmente (su base per cifra), con una base elevata, come i numeri di base 2^16.

Answer 3

OK qui va:

1 << 1000 

Su una nota più grave, il più si può tenere in un intero x-bit è 1<<x-1. Per calcolare effettivamente lo 1<<1000 avresti bisogno di un processore a 1000-bit (tecnicamente 1001-bit, ma a quel punto chi sta contando). Dal momento che non è fattibile, la tua unica scelta è quella di emularlo (e questo è ciò che fa bigint).

Answer 4

Non c'è niente di calcolare in realtà: 2^1000 = (1000...[994]...000)[Base2]. È già un "risultato".

Se si desidera sapere come memorizzarlo, la macchina non ha la precisione per memorizzare il suo valore esatto. Quindi è uno BigInt o il doppio valore approssimativo Math.Pow(2, 1000).

Edit: Vedo ora si dai commenti desidera solo la somma delle cifre. Vedi una delle soluzioni.

Answer 5

La parte più difficile di questo problema non è il calcolo (basta iniziare con 1 e raddoppiarlo 1000 volte), ma visualizzare la risposta in decimale. Con questo in mente, potresti trovare concettualmente più semplice eseguire il calcolo in una qualche forma di rappresentazione BCD, come base-1000. Quindi esegui una moltiplicazione lunga di 2 volte. Ecco una soluzione 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

Il problema è davvero conversione di 2^1000 a base 10. Un modo semplice potrebbe essere quella di realizzare una sorta di BCD (Binary Coded Decimal) di lunghezza arbitraria e calcolare 2^1000 BCD. Un array di 250 byte sarebbe più che sufficiente. Quindi devi solo scrivere il metodo per eseguire * 2 su un numero BCD di lunghezza arbitraria e chiamarlo 1000 volte). Quindi estrarre e citare le cifre è facile.

che è molto facile da implementare anche in linguaggi come C.

Answer 7

Cercherò e risposta senza dare via molto codice ...

1) utilizzare una stringa per contenere il prodotto

2) Eseguire lungo Moltiplicazione (come hai fatto a scuola)

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 

stampa prod

Notepad-Coding qui ... così se qualcuno trova bug, correggili.

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(); 

     } 
    } 
}