Большое целочисленное преобразование основание / основание из 10 ^ x в 2 ^ x - PullRequest
Новая
       20

Большое целочисленное преобразование основание / основание из 10 ^ x в 2 ^ x

6 голосов
/ 07 июня 2011

Предисловие

Я изучаю компьютерную математику, написав и улучшив свою собственную библиотеку BigInt.До сих пор в моем первом воплощении каждая цифра из 10 базовых чисел сохранялась в последовательных элементах вектора.Он может умножаться и складываться с произвольной точностью.Я хочу ускорить его, используя все доступное мне пространство в стандартном типе данных C ++ путем преобразования в базу 2 ^ x.

Информация

Я читаю 1000 или более цифр изstdin в базе 10, и я хочу преобразовать их в базу 2 ^ x, чтобы я мог легко хранить их в массиве или векторе одного из стандартных типов данных C ++, вероятно, без знака int.У меня есть только одна идея, как сделать базовое преобразование, повторное деление с использованием метода остатка.Вот некоторый код C ++, описывающий этот метод: 

vector<int> digits;
while(num!=0) {
   int mod = num%base;
   num = num/base;
   digits.push_back(mod);
}

Загадки

Некоторые вещи, на которых я заблудился, это то, является ли деление с остатком правильным способом для преобразования в большие целые числа,Я пытался посмотреть, как библиотека GMP делает это. gmp / mpn / generic / set_str.c является соответствующим исходным файлом c, где происходит «волшебство», но я не уверен, что там происходит. BigInt Мэтта Маккатчена, похоже, использует метод повторного деления с остатком.Если я использую этот метод, мне по сути нужно написать две версии моего класса BigInt, одну для работы в Base10, а другую для Base2 ^ x.

Заключение

  • Предложить совет поправильные шаги для преобразования огромного числа из строки в массив из 32-битных слов.
  • Помогите мне узнать, как GMP преобразует строку в массив из 32-битных слов, не пробираясь через многоуровневую абстракцию.

Примеры Использование 4-битного слова размером

Число, которое мы хотим сохранить (очевидно, при небольшом размере): 123456789

беззнаковые символы имеют диапазон 0-255, если мыЕсли мы хотим разделить наш номер и сохранить его в векторе, мы можем сделать это одним из трех способов:

  • В качестве базы 10 наш вектор выглядит так: [1,2,3,4,5,6,7,8,9]
    • Вот как мой вектор выглядел в моей первой реализации.
  • Как база 100, наш вектор выглядит так: [1,23,45,67,89]
    • Легко переводить из базы 10 в базу 100, имеет элемент ciel (цифры в base10 / 2)ts.
  • В качестве основы 256 наш вектор выглядит следующим образом: [7,91,205,21]

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

Ответы [ 3 ]

6 голосов
/ 07 июня 2011

Если у вас есть функции умножения и добавления для вашей библиотеки bigint, преобразование строки в bigint само по себе просто.Начните с результата преобразования ноль.Для каждой обрабатываемой цифры (слева направо) умножьте предыдущий результат на 10 и добавьте значение новой цифры (используя умножение bigint и добавление функций).

1 голос
/ 07 июня 2011

Как правило, для преобразования одной базы в другую (из старшего разряда в младший) алгоритм выглядит следующим образом: 

output = 0
foreach digit in digits:
    output = output * base + digit

В обратном порядке, это следующее: 

output = 0
multiplier = 1
foreach digit in digits:
    output = output + multiplier * digit
    multiplier = multiplier * base

Вы можете использовать свою библиотеку bigint рекурсивно, используя эту математику, чтобы выяснить, как хранить числа. Я имею в виду, что вам нужно реализовать BigInt * BigInt и BigInt + BigInt, поэтому вы можете конвертировать базы. Это не самый эффективный способ, но он намного быстрее, чем деление.

0 голосов
/ 17 августа 2012

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

Существует две формулы для преобразования осей в целых числах.(1) использует базу B, которую мы конвертируем в (базу назначения), в качестве повторяющегося делителя в сочетании с арифметикой, выполненной в базе b, где b - база, конвертирующая из .(2) с другой стороны использует базу b в качестве множителя для цифр, которые мы конвертируем, которые находятся в одной и той же базе b, и выполняет арифметику в базе B.

(1) формула использует B какпараметр и делает арифметику в базе b

(2) формула использует b в качестве параметра и делает арифметику в базе B

это вне кнута, том 2, 4.4 радикальных преобразований

...