Как преобразовать строковое представление целого числа произвольной длины в заданной базе в десятичное?

Question

Мне было интересно, как бы вы конвертировали целое число произвольной длины в некоторую базу b , представленную строкой, в строковое представление в базе 10.

Например, еслиЯ посылаю строку «4552», а также отправляю, что она находится в базе 8, и я хочу преобразовать эту строку в базу 10 и вернуть строку, но я не могу использовать такие вещи, как atoi или strtol, потому что если яd отправить 312434324324324324324324 Это было бы невозможно, я сначала подумал, что вы можете использовать как классический рекурсивный алгоритм, который выполняет рекурсивную операцию с number % 10 до последней цифры, а затем наоборот вводит число в строку.

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

char *to_base_10(char *nb, int base)
{
    int size = my_strlen(nb);
}

Answer 1

Для числовой строки без знака n длины L , содержащей цифры b , решение "ручка и бумага":

n _dec = n ₀ xb ^L-1 + n ₁ xb ^L-2 + ... + n _L-1 xb ⁰

(где n ₀ является самой значимой, т. Е. Левой цифрой, а n _L-1 самой младшей цифрой, т. Е. Индексы совпадают с порядком массива C).

Таким образом, разбивая его на операции, вы должны реализовать произвольную длину целого числа операций для:

• Вычисление (x ^y )
• Умножение
• Сложение

Поскольку в самом грубом (и я предлагаю вам начать с него) умножение может быть выполнено путем повторного сложения и возведения в степень путем повторного умножения, вам нужно толькореализовать сложение . Улучшения производительности, такие как длинное умножение и возведение в квадрат в квадрате , могут подождать, пока у вас не появятся основные принципы (и установлено, что простое решение даже слишком медленное). «ручное и бумажное» решение относительно сложения относительно простое (для A + B итерация цифр от n = от LSD до MSD + 1 при выполнении A _n + B _n + Carry _n-1 ) и может быть реализован в коде для строк произвольной длины.

Исходя из этого, реализовать умножение на повторноедобавление (изначально), в свою очередь возведение в степень путем повторного умножения.

Затем, наконец, реализовать выражение с десятичным числом n _dec = ... как указано выше с итерацией от n ₀ до n _L-1 с использованием произвольной длиныцелое число операций.

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