Что является эффективным способом, чтобы преобразовать структуру типа bignum в удобочитаемой строкой?

У меня небольшая проблема. Чтобы расширить свои знания языка Си, я решил попробовать реализовать базовую библиотеку bigint.

Ядром структуры bigint будет массив 32-битных целых чисел, выбранных потому, что они поместятся в регистр. Это позволит мне выполнять операции между цифрами, которые будут переполняться 64-битным целым числом (которое также поместится в регистр, так как я на x86-64), и я могу немного сдвинуть каждую часть результата. Я реализовал базовое дополнение, и чтобы проверить чтобы он работал, я должен распечатать массив. Для моих собственных целей тестирования, это нормально, если я использую printf() и выводить каждую цифру в шестнадцатеричном формате. Я прекрасно могу это прочесть.

Однако большинство людей не могут читать гекс. Поскольку число хранится в (по существу) базе 2^32, печать представляет собой небольшую проблему. Какой был бы хороший способ перейти на базу 10?

Правка:

Речь идет не о том, чтобы знать, как конвертировать из базы в базу, а о хорошем способе реализации этого. Я думал примерно так. сделать еще один бигинт с другой базой с конверсией для печати.

4 4
c99 biginteger

4 ответа:

Во-первых, вы не можете сделать ввод-вывод разумным способом без основных операций(например, деления и модуля). Чтобы обеспечить эффективную реализацию преобразования bigint в строку base-10, я исследую две возможные оптимизации:

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

Во-вторых, как бы вы выбрали, на какую степень из десяти делить? Десять, 100, 1000, 10000 и т. д...
Кажется, есть хороший выбор, который является максимальной мощностью десяти, которая может поместиться в вашем слове (32-бит). К счастью, вы можете реализовать деление / модуль одним словом гораздо эффективнее, чем когда речь заходит о двух "bigint" s.

Я не дал реализацию, потому что я все еще исследую проблему в свободное время, потому что я реализовал основные операции в моей библиотеке, и I/O-это следующий шаг, надеюсь;)

5

Деление на наибольшую степень 10, которая будет соответствовать вашему базовому типу, - Это лучший способ начать. В вашем случае это будет деление на 10^9. Этот код должен быть общего назначения, так как вы сможете повторно использовать его для части вашего общего кода деления/модуля.

Время выполнения будет O (n^2) (то есть, если ваше число в два раза больше, преобразование будет говорить в четыре раза дольше), но оно должно быть достаточно быстрым для чисел среднего размера.

Для очень больших значений вы захотите кэш больших степеней 10, скажем 10^1000, 10^2000, 10^4000, 10^8000, ...., а затем разделить на степень 10, которая больше или равна 1/2 числа, которое вы пытаетесь преобразовать. Повторяйте этот процесс до тех пор, пока числа не станут достаточно малы для быстрого преобразования с помощью деления на 10^9. В зависимости от того, насколько эффективен ваш алгоритм деления, этот подход не может быть быстрее, пока вы не столкнетесь с числами, превышающими миллион цифр или более.

Если вы пишете интерактивный калькулятор, где каждое число будет отображаться, тогда использование базы 10^9 будет быстрее для отображения (это будет O (n), т. е. если ваше число в два раза больше, преобразование займет только в два раза больше времени).

1

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

Очевидный быстрый способ состоит в том, чтобы иметь предварительно вычисленные массивы бигинтов, соответствующие значению каждой цифры в каждой позиции. Затем вы можете выполнить двоичный поиск и относительно дешевые сравнения/вычитания, чтобы найти цифру ms, а затем каждую цифру по очереди.

Вы можете вернуться к делению на 10, когда дойдете до последних 32 (или 64) бит.

0

Самый эффективный алгоритм, который я могу придумать, заключается в следующем. Он должен иметь сложность выполнения в O (n·(log n) 2·log log n), в отличие от наивного алгоритма, который имеет квадратичную сложность выполнения.

    Предположим без потери общности, что число A равно 2 n+1 битам длины. Он может иметь ведущие нули.
  1. вычислите десятичные представления чисел 22я ... для i до n путем повторного возведения в квадрат, если это самая верхняя рекурсия уровень.
  2. разбейте последовательность битов входного числа на две части B и C. часть с менее значимыми битами, C, содержит 2n наименее значимых битов A, а часть B-оставшиеся более значимые биты.
  3. преобразуйте B и C в их десятичные представления, либо используя квадратичный алгоритм выполнения, если они достаточно коротки, или рекурсивно вызывая этот алгоритм.
  4. умножьте десятичное представление B на кэшированное десятичное представление из 22n и добавьте десятичное представление C, чтобы получить десятичное представление A.

В шагах 2 и 5 вам понадобится алгоритм десятичного умножения. Для чисел с десятками тысяч цифр следует использовать версию алгоритма Шенхаге-Штрассена, который работает в базе 10. Это приведет к сложности выполнения, указанной выше. Для более коротких чисел, в зависимости от их длины, алгоритм Тум-Кука, алгоритм Карацуба или длинное умножение должны быть использованный. Однако в настоящее время я не могу сказать, как реализовать алгоритм Шенхаге-Штрассена в базе 10, поскольку все полные описания этого алгоритма, которые я смог найти, относятся к базе 2, и я не знаю достаточно теории чисел, чтобы вывести его самостоятельно.

0