Calcule a soma de 2 ^ 1000 sem usar BigInt

Question

Como alguns de vocês podem notar, esta questão é problema 16 de Projeto Euler.Eu resolvi isso usando o novo recurso "bigInt" do C # 4.0, que era bastante simples, mas também não estava aprendendo tudo o que deveria.Estou assumindo que, como é 2 ^ 1000, haveria algum tipo de solução de mudança de bits, mas não consigo descobrir como exatamente funcionaria.

Alguém sabe uma maneira de calcular 2 ^ 1000 sem usar bigint?

Answer 1

Aqui está uma maneira bastante ingênua de fazer isso em python apenas usando uma lista (ou array) 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

A parte mais difícil deste problema não é o cálculo (basta começar com 1 e dobrar 1000 vezes), mas exibir a resposta em decimal.Com isso em mente, você pode achar conceitualmente mais fácil realizar o cálculo em alguma forma de representação BCD, como base 1000.Em seguida, faça uma longa multiplicação por 2 mil vezes.Aqui está uma solução 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 3

Você pode implmegar se enorme, potencialmente introduzindo bugs e provavelmente resultará em uma solução muito mais lenta.Uma implementação típica é realizar manualmente a matemática (por uma base por dígito), com alguma base alta, como base 2 ^ 16 números.

Answer 4

O problema é realmente conversão de 2 ^ 1000 para base 10. Uma maneira fácil pode ser implementar algum tipo de BCD (decimal codificado binário) de comprimento arbitrário e computar 2 ^ 1000 no BCD.Uma matriz de 250 bytes seria mais que suficiente.Então você só precisa escrever o método para executar * 2 em um número BCD de comprimento arbitrário e chamá-lo de 1000 vezes).Em seguida, extrair e resumir os dígitos é fácil.

Isso é muito fácil de implementar mesmo em idiomas como c.

Answer 5

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

        }
    }
}

Answer 6

OK, aqui vai:

1 << 1000

Falando mais sério, o máximo que você pode conter em um número inteiro de x bits é 1<<x-1.Para realmente calcular 1<<1000 você precisaria de um processador de 1000 bits (tecnicamente 1001 bits, mas quem está contando neste momento).Como isso não é viável, sua única opção é emulá-lo (e é isso que o bigint faz).

Answer 7

Na verdade, não há nada para calcular: 2^1000 = (1000...[994]...000)[Base2].Já é um 'resultado'.

Se você quiser saber como armazená-lo, sua máquina não tem precisão para armazenar seu valor exato.Então é um BigInt, ou o valor aproximado duplo Math.Pow(2, 1000).

Editar: Eu vejo você agora dos comentários só quero a soma dos dígitos.Veja uma das soluções.

Answer 8

Vou tentar responder sem revelar muito código ...

1) Use um barbante para segurar o produto

2) Faça multiplicações longas (como você fez na escola)

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

produto de impressão

Codificação do bloco de notas aqui... então, se alguém encontrar bugs, corrija-os.