Вычислите к сумме 2^1000, не используя BigInt
Поскольку некоторые из Вас могут заметить, что этим вопросом является проблема 16 от Euler Проекта. Я решил его с помощью новой "bigInt" функции C# 4.0, который был довольно прост, но который также действительно не изучает все, что я должен. Я предполагаю, что, так как это - 2 ^ 1000, были бы своего рода решения для смещения бита, но я не могу выяснить, как точно это работало бы.
Кто-либо знает способ вычислить 2^1000, не используя bigint?
7 ответов
Вот довольно наивный способ сделать это в 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)))
Вы можете внедрить BigInt самостоятельно, что потенциально приведет к появлению ошибок и, вероятно, приведет к гораздо более медленному решению. Типичная реализация состоит в том, чтобы вручную выполнить математические вычисления самостоятельно (для каждой цифры) с некоторой высокой базой, например, с основанием 2 ^ 16 чисел.
Хорошо, здесь идет:
1 << 1000
Если серьезно, то максимум, что вы можете удержать в x-битном целом числе, это 1 < <х-1 . Чтобы фактически вычислить 1 << 1000 , вам понадобится 1000-битный процессор (технически 1001-битный, но кто сейчас считает). Поскольку это невозможно, ваш единственный выбор - подражать этому (и это то, что делает bigint).
На самом деле вычислять нечего: 2 ^ 1000 = (1000 ... [994] ... 000) [Base2] . Это уже «результат».
Если вы хотите знать, как его сохранить, ваша машина не обладает точностью, чтобы сохранить его точное значение. Таким образом, это либо BigInt , либо двойное приближенное значение Math.Pow (2, 1000) .
Редактировать: Теперь я вижу, что вы из комментариев просто хотите получить сумму цифр. Смотрите одно из решений.
Я постараюсь ответить, не раскрывая большого количества кода ...
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
Notepad-Coding здесь ... так что, если кто-то обнаружит ошибки, исправьте их.
Самая сложная часть этой проблемы - это не вычисление (просто начните с 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^1000 в основание 10. Одним из простых способов может быть реализация некоего массива BCD (Binary Coded Decimal) произвольной длины и вычисление 2^1000 в BCD. Массива в 250 байт будет более чем достаточно. Затем нужно просто написать метод для выполнения *2 над BCD числом произвольной длины и вызвать его 1000 раз). Тогда извлечение и суммирование цифр не составит труда.
Это очень легко реализовать даже в таких языках, как C.