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