Невозможно сохранить слишком длинный тип int

Рассмотрим проблему:

It can be shown that for some powers of two in decimal format like:
2^9 = 512
2^89 = 618,970,019,642,690,137,449,562,112

Результат заканчивается строкой, состоящей из 1 и 2. На самом деле можно доказать, что для каждого целого числа R существует степень двойки, такая что 2K, где K > 0, имеет строку, состоящую только из 1 и 2 в последних R цифрах.

Наглядно это можно показать в таблице ниже:

R Smallest K 2^K
1 1 2
2 9 512
3 89 ...112
4 89 ...2112

Используя этот метод, какова тогда сумма всех наименьших значений K для 1 ‹ = R ‹ = 10? Предлагаемое решение: Теперь эту проблему не так сложно решить. Вы можете просто сделать int temp = power(2, int), а затем, если вы можете получить длину temp, умножьте ее на

(100^len)-i or (10^len)-i

// где я бы определил, сколько последних цифр вам нужно.

Теперь это temp = power(2,int) становится намного выше с увеличением int, что вы даже не можете сохранить его в типе int или даже в long int.... Итак, что нужно сделать. И есть ли другое решение, основанное на битовых строках. Я думаю, это могло бы упростить эту проблему. Заранее спасибо.


c++
person Terrenium    schedule 17.12.2012    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Нет, я сомневаюсь, что есть какие-то решения, основанные на "битовых строках". Это было бы совсем неэффективно. Но есть библиотеки Bignum, такие как GMP, в которых типы переменных либо фиксированного размера намного больше, чем типы int, либо имеют произвольный ограниченный размер. только по объему памяти, плюс соответствующие наборы математических операций, работающие аналогично программной эмуляции FPU.

Цитирование после ссылки с небольшим перефразированием.

 #include <gmpxx.h>

 int
 main (void)
 {
   mpz_class a, b, c;

   a = 1234;
   b = "-5676739826856836954375492356569366529629568926519085610160816539856926459237598";
   c = a+b;
   cout << "sum is " << c << "\n";
   cout << "absolute value is " << abs(c) << "\n";

   return 0;
 }

Благодаря перегрузке операторов C++ его намного проще использовать, чем версию ANSI C.

person SF.    schedule 17.12.2012
comment
На самом деле я впервые услышал эту библиотеку. Можете ли вы придумать простой, наглядный пример. - person Terrenium; 17.12.2012

arrow_upward
2
arrow_downward

Поскольку вас интересуют только n младшие значащие цифры вашего результата, вы можете попытаться разработать алгоритм, который вычисляет только их. Основываясь на стандартном алгоритме письменного умножения, вы можете видеть, что n младшие значащие цифры числа произведения полностью определяются n младшими цифрами множимых. На основе этого должно быть возможно создать алгоритм, который вычисляет столько цифр R^K, сколько умещается в long int.

Единственная проблема, с которой вы можете столкнуться, заключается в том, что могут быть числа, которые заканчиваются совпадающей последовательностью, которая длиннее, чем может содержать long int. В этом случае вы все равно можете прибегнуть к вычислению дополнительных цифр, используя собственный алгоритм или библиотеку.

Обратите внимание, что это в основном то же самое, что и библиотеки больших чисел, только ваш подход может быть более эффективным, потому что вы вычисляете меньше цифр, которые вам вряд ли понадобятся.

person Björn Pollex    schedule 17.12.2012

arrow_upward
1
arrow_downward

Попробуйте GMP, http://gmplib.org/
Он может хранить число любого размера, если оно подходит память.
Хотя вам может быть лучше с меньшим подходом грубой силы.

person Dani    schedule 17.12.2012

arrow_upward
1
arrow_downward

Вы можете хранить двоичные строки в std::bitset или в std::vector www.cplusplus.com/ ссылка/набор битов/набор битов/

Я думаю, что битсет - ваш выбор.

Однако использование большой арифметики для операций со степенями двойки недопустимо.

person kassak    schedule 17.12.2012
comment
Хорошо. Только одно. существует ли какой-либо определенный шаблон битовых строк, которым следует следовать в этой задаче. - person Terrenium; 17.12.2012