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

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

6 голосов
/ 13 июля 2010

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

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

Ответы [ 8 ]

3 голосов
/ 13 июля 2010

Самая сложная часть этой проблемы - не вычисления (просто начните с 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')
2 голосов
/ 13 июля 2010

Вот довольно наивный способ сделать это в 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)))
1 голос
/ 26 июля 2012 
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();

        }
    }
}
1 голос
/ 13 июля 2010

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

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

1 голос
/ 13 июля 2010

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

0 голосов
/ 13 июля 2010

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

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

print prod

Кодировка блокнота здесь ... так что, если кто-то найдет ошибки, исправьте их.

0 голосов
/ 13 июля 2010

На самом деле вычислять нечего: 2^1000 = (1000...[994]...000)[Base2]. Это уже «результат».

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

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

0 голосов
/ 13 июля 2010

ОК, здесь идет: 

1 << 1000

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

...