Неограниченное базовое преобразование? - PullRequest
Новая
       21

Неограниченное базовое преобразование?

7 голосов
/ 04 мая 2011

Я пытаюсь реализовать тип 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 действительно получит big , я не смогу конвертировать, добавив больше. Как я могу преобразовать массив base-x в массив base-y?

Ответы [ 2 ]

1 голос
/ 04 мая 2011

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

В итоге:

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

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

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

0 голосов
/ 04 мая 2011

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

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

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

...