Верхняя граница количества цифр большого целого числа в другом основании

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

Пример:

Число 640 bit имеет 640 цифр в base 2, но только десять цифр в base 2^64, поэтому мне придется выделить десять целых 64 bit чисел для хранения результата.

Функция, которую я сейчас использую:

int get_num_digits_in_different_base(int n_digits, double src_base, double dst_base){
    return ceil(n_digits*log(src_base)/log(dst_base));
}

Где src_base находится в {2, ..., 10 + 26}, а dst_base находится в {2^8, 2^16, 2^32, 2^64}.

Я не уверен, что результат всегда будет правильно округлен. log2 было бы проще рассуждать, но я читал, что старые версии Microsoft Visual C++ не поддерживают эту функцию. Его можно было эмулировать как log2(x) = log(x)/log(2), но теперь я вернулся к тому, с чего начал.

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


c floating-point floating-accuracy floating-point-precision
person John    schedule 28.02.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

Далее пусть dst_base будет равно 2^w, src_base будет равно b, а n_digits будет равно n.

Пусть k(b,w)=max {j | b^j ‹ 2^w}. Это представляет наибольшую степень b, которая гарантированно помещается в двоичное (неотрицательное) целое число шириной w. Из-за относительно небольшого количества исходных и целевых баз эти значения можно предварительно вычислить и найти в таблице, но математически k(b,w)=[w log 2/log b] (где [.] обозначает целую часть.)

Для данного n пусть m=ceil( n / k(b,w)). Тогда максимальное количество dst_base цифр, необходимых для хранения числа меньше b^n, равно:

ceil(log (b^n-1)/log (2^w)) ≤ ceil(log (b^n) / log (2^w) ) ≤ ceil( m . log (b^k(b< /em>,w)) / log (2^w) ) ≤ m.

Короче говоря, если предварительно вычислить значения k(b,w), можно быстро получить верхнюю границу (которая не точна!) путем деления n на k, округление вверх.

person halfflat    schedule 28.02.2015
comment
Я предполагаю, что src_base — это b вместо n, а n — это n_digits в src_base. m = ceil(n / k(b, w)) = ceil(n / (w log(2) / log(b))) = ceil(n * log(b) / (w log(2))) = ceil(n * log(b) / log(2^w) ) = ceil(n_digits * log(src_base) / log(dst_base)) так что это действительно вывод моей формулы. Однако я не уверен, действительно ли это доказывает, что оно округлено правильно? - person John; 28.02.2015
comment
Конечно, правильно насчет моей неправильной маркировки: я отредактирую, чтобы исправить. Хитрость в том, что k(b,w) = floor ( w log(2) / log(b) ), а не ровно w * log(2)/log(b). С одной стороны, это означает, что вы можете точно вычислить k(b,w) (либо взяв аппроксимацию с плавающей запятой и при необходимости откорректировав ее, либо выполнив поиск j в целочисленной области для случая, когда 2^_w_ - b_^_j становится отрицательным), а с другой стороны, это означает, что значение m, полученное выше, является верхней границей, а не точным. - person halfflat; 28.02.2015

arrow_upward
0
arrow_downward

Я не уверен в округлении с плавающей запятой в этом случае, но это относительно легко реализовать, используя только целые числа, поскольку log2 — это классический шаблон манипулирования битами, а целочисленное деление можно легко округлить. Следующий код эквивалентен вашему, но использует целые числа:

// Returns log2(x) rounded up using bit manipulation (not most efficient way)
unsigned int log2(unsigned int x)
{
    unsigned int y = 0;
    --x;
    while (x) {
        y++;
        x >>= 1;
    }
    return y;
}

// Returns ceil(a/b) using integer division
unsigned int roundup(unsigned int a, unsigned int b)
{
    return (a + b - 1) / b;
}

unsigned int get_num_digits_in_different_base(unsigned int n_digits, unsigned int src_base, unsigned int log2_dst_base)
{
    return roundup(n_digits * log2(src_base), log2_dst_base);
}

Обратите внимание, что:

  • Эта функция возвращает результаты, отличные от ваших! Однако в каждом случае, который я смотрел, оба были правильными (меньшее значение было более точным, но ваше требование — это всего лишь верхняя граница).
  • Целочисленная версия, которую я написал, получает log2_dst_base вместо dst_base, чтобы избежать переполнения для 2^64.
  • log2 можно повысить эффективность с помощью таблиц поиска.
  • Я использовал unsigned int вместо int.
person André Sassi    schedule 28.02.2015
comment
Это тоже отличное решение. Мне сейчас плохо, потому что мне нельзя принимать два ответа сразу. - person John; 28.02.2015