Неограниченная базовая конверсия?

Я пытаюсь реализовать тип BigInt в JavaScript, используя массив целых чисел. На данный момент у каждого есть верхняя граница 256. Я закончил реализацию всех целочисленных операций, но я не могу понять, как преобразовать BigInt в его строковое представление. Конечно, простой способ заключается в следующем:

BigInt.prototype.toString = function(base) {
    var s = '', total = 0, i, conv = [
        ,,
        '01',
        '012',
        '0123',
        '01234',
        '012345',
        '0123456',
        '01234567',
        '012345678',
        '0123456789',
        ,
        ,
        ,
        ,
        ,
        '0123456789abcdef'
    ];
    base = base || 10;

    for(i = this.bytes.length - 1; i >= 0; i--) {
        total += this.bytes[i] * Math.pow(BigInt.ByteMax, this.bytes.length - 1 - i);
    }

    while(total) {
        s = conv[base].charAt(total % base) + s;
        total = Math.floor(total / base);
    }

    return s || '0';
};

Но когда BigInts действительно станет большим, я не смогу конвертировать, добавив больше. Как я могу преобразовать массив base-x в массив base-y?

2 ответа

Решение

Посмотрите пример, который я дал в этом ответе на аналогичный вопрос недавно (он предназначен для базовых-10-базовых-3, но принцип должен быть переносимым): C Быстрое базовое преобразование из десятичного в троичное.

В итоге:

Перебирать входные цифры от низкого до высокого. Для каждой позиции цифры сначала вычислите, что 1000....000 (base-256) будет в выходном представлении (это 256x от предыдущей степени 256). Затем умножьте этот результат на цифру и накапливайте в выходное представление.

Вам понадобятся процедуры, которые выполняют умножение и сложение в выходном представлении. Процедура умножения может быть написана в терминах процедуры сложения.

Обратите внимание, что я не утверждаю, что этот подход в любом случае быстр (я думаю, что это O(n^2) в количестве цифр); Я уверен, что есть алгоритмически более быстрые подходы, чем этот.

Если вы готовы надеть на себя математический предел больше, чем я сейчас, то, кажется, кто-то объяснил, как преобразовать цифровые представления с использованием треугольника Паскаля:

http://home.ccil.org/~remlaps/DispConWeb/index.html

Внизу есть ссылки на исходный код. Они скорее на языке Java, чем на JavaScript, но если вы прикладываете усилия, чтобы разобраться с математикой, вы, вероятно, можете придумать собственную реализацию или приложить усилия для переноса кода...

Другие вопросы по тегам