Рассчитать до суммы 2^1000 без использования BigInt

Question

Как некоторые из вас могут заметить, этот вопрос - проблема 16 из Project Euler. Я решил эту проблему, используя новую функцию bigInt в C# 4.0, которая была довольно простой, но в действительности не изучала все, что мне нужно. Я предполагаю, что, поскольку это 2 ^ 1000, было бы какое-то решение с битовым сдвигом, но я не могу понять, как именно это будет работать.

Кто-нибудь знает способ расчета 2 ^ 1000 без использования bigint?

Answer 1

Вот довольно наивный способ сделать это в Python, просто используя список (или массив) цифр

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

Самая сложная часть этой проблемы - не вычисления (просто начните с 1 и удвоите их 1000 раз), а отображение ответа в десятичном виде. Имея это в виду, вам может показаться, что концептуально проще выполнять вычисления в некоторой форме представления BCD, такой как base-1000. Затем выполните длинное умножение в 2 тысячи раз. Вот решение 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

Проблема в действительности заключается в преобразовании 2^1000 в основание 10. Одним из простых способов может быть реализация некоторого вида BCD (двоично-десятичного числа) произвольной длины и вычисление 2^1000 в BCD. Массив из 250 байтов будет более чем достаточно. Затем вам просто нужно написать метод для выполнения *2 для числа BCD произвольной длины и вызвать его 1000 раз). Тогда извлечь и суммировать цифры легко.

Это очень легко реализовать даже на таких языках, как C.

Answer 4

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 5

Вы можете сами внедрить BigInt, что может привести к появлению ошибок и, скорее всего, к более медленному решению. Типичная реализация состоит в том, чтобы вручную выполнить математику самостоятельно (на основе цифры), с некоторым высоким основанием, таким как числа 2^16.

Answer 6

Хорошо здесь идет:

1 << 1000

На более серьезной ноте, самое большее, что вы можете держать в x-битном целом числе: 1<<x-1, На самом деле рассчитать 1<<1000 вам понадобится 1000-битный процессор (технически 1001-битный, но кто рассчитывает на данный момент). Поскольку это невыполнимо, ваш единственный выбор - подражать этому (и именно это делает bigint).

Answer 7

Там нет ничего, чтобы рассчитать на самом деле: 2^1000 = (1000...[994]...000)[Base2], Это уже "результат".

Если вы хотите знать, как его хранить, у вашего компьютера нет точности, чтобы сохранить его точное значение. Так что это либо BigIntили двойное приблизительное значение Math.Pow(2, 1000),

Изменить: я вижу, теперь вы из комментариев просто хотите, чтобы сумма цифр. Смотрите одно из решений.

Answer 8

Я постараюсь ответить, не выдавая много кода...

1) Используйте строку, чтобы держать продукт

2) Выполните длинное умножение (как вы делали в школе)

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

печатный продукт

Блокнот-кодирование здесь... поэтому, если кто-то найдет ошибки, исправьте их.