Алгоритм преобразования большого целого числа в строку без основания по модулю

Question

Я некоторое время искал, чтобы найти алгоритм, который преобразует целые числа в строку.Мое требование - сделать это вручную, так как я использую свой собственный тип большого числа.Я определил + - * /(with remainder), но мне нужно найти способ напечатать одно число из двойного целого числа (старшее и нижнее, если целое число 64 бита, всего 128 бит).

Я видел некоторые ответы, такие как

Преобразование целого числа в строку без доступа к библиотекам

Преобразование большого целого числа в десятичную строку

но интересовался, возможен ли более быстрый алгоритм.Я открыт для работы с битами напрямую (например, от base2 до base10-строки - однако я не смог найти такой алгоритм), но я просто надеялся избежать повторного деления на 10 для чисел, возможно, таких как 2 ^ 128.

Answer 1

Вы можете попытать счастья с помощью надуманного метода, как показано ниже.

Числа могут быть представлены с использованием двоично-десятичного представления.В этом представлении каждая десятичная цифра хранится в 4 битах, и при выполнении сложения, если сумма двух цифр превышает 9, вы добавляете 6 и переносите влево.

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

Но это звучит как много операций.Вы можете «распараллелить» их, упаковав несколько цифр BCD в одно целое число: сложение целых чисел в 32 бита эквивалентно 8 одновременным сложениям цифр BCD.Но у нас есть проблемы с переносчиками.Чтобы обойти это, мы можем хранить цифры на 5 битах вместо 4, и переносы появятся в пятом бите.Затем мы можем получить переносы с помощью маскировки, добавить их к следующим цифрам (сдвиг влево на 5) и скорректировать суммы цифр (умножить на 10 и вычесть).

  2 3 4 5 6
+ 7 6 9 2 1
= 9 913 7 7

Carries:

 0-0-1-0-0

Корректировки:

  9 913 7 7
-0000010000
= 9 9 3 7 7

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

32-битные операции позволяют обрабатывать 6 цифр за раз (7 раундов для 39 цифр) и 64-битные операции, 12 цифр (4 раунда для 39 цифр).

Answer 2

1. , если вы хотите просто закодировать свои числа в виде строки

   , используйте шестнадцатеричные числа, которые быстрые, так как вы можете привести все цифрыпросто с помощью битовых операций ... также используя кодирование Base64 возможно только с помощью битовых операций + таблица перевода.Представления на стенде могут быть выполнены на малой int арифметике только в O(n), где n - количество напечатанных цифр.

2. Если вам нужно base10

   , выведите строку hex и преобразуйте ее в десятичную строку, например:

   • str_hex2dec

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

Для bigint libs также есть другие способы ослабления строки /целочисленные преобразования:

1. BCD

   десятичное двоичное кодирование ... число, напечатанное в шестнадцатеричном виде, является десятичным числом.Таким образом, каждая цифра имеет 4 бита.Это приводит к потере памяти, но многие процессоры имеют поддержку BCD и могут выполнять операции с такими целыми числами.

2. База 10^n

   иногда используетсяbase 10^n вместо 2^m, в то время как

   10^n <= 2^m
   

   m - битовая ширина вашего атомного целого числа и n i - количество десятичных цифр, которое вписывается в него.

   дляНапример, если ваше атомное целое число без знака равно 16 битам, оно может содержать до 65536 значений в базе 2.Если вместо этого вы используете основание 10000, вы можете напечатать каждый атом как десятичное число с нулевой координатой слева и просто сложить все такие отпечатки вместе.

   Это также тратит часть памяти, но обычно не слишком много (если пропускная способность достаточновыбран), и вы можете использовать стандартные инструкции на целые числа.Только распространение Carry изменится немного ...

   , например, для 32-битных слов:

   2^32 = 4294967296 >= 1000000000
   

   , поэтому мы потратили log2(4.2949...) = ~2.1 бит на каждые 32 бита.Это намного лучше, чем BCD log2(16/10)*(32/4)= ~5.42 бит и, как правило, даже лучше с большей битовой шириной

Answer 3

Вы можете использовать метод «разделяй и властвуй» таким образом, чтобы части можно было преобразовать в строку, используя вашу стандартную библиотеку (что, как правило, весьма эффективно при этой работе).

Поэтому вместо деления на10 в каждой итерации, например, вы можете делить на 10 ** 15, и ваша библиотека преобразует куски в 15-значные строки.После не более чем трех шагов вы закончите.

Конечно, вы должны выполнить некоторые манипуляции со строками, касающиеся заполнения нулями.Но, возможно, ваша библиотека может помочь вам и здесь, если вы используете что-то вроде %015d формата с нулевым заполнением для всех нижних частей, а для самой высокой ненулевой части используйте формат без заполнения %d.