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

Я работаю с числами в разных базах (base-10, base-8, base-16 и т. Д.). Я пытаюсь подсчитать количество символов в каждом номере.

пример

Номер: ABCDEF

Количество цифр: 6

Я знаю о методе, основанном на логарифмах, но я столкнулся с некоторыми проблемами.

  1. Этот скрипт Python выводит, что ему не удалось правильно вычислить количество цифр в 3996 номерах из 1 000 000.

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

Ссылки:

  • Эта программа C должна быть очень медленной (что, если у меня очень большое число?). Он также не может иметь дело с числами в разных базах (например, base-16).

  • Не обманывать это, поскольку там ОП спрашивал только о базе-10


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

Edit2: source-basebase-10, а базой для преобразования в может быть любая другая база.


Как мы можем вычислить количество цифр в числах в разных базах?

Если я знаю номер в базе 10, как я могу вычислить количество цифр в том же количестве, которое было преобразовано в base-16 (base-8 и т. Д.) Без выполнения преобразования ?

Примечание : некоторые Python или C-код будут оценены

Логарифмы не должны быть медленными. И вы можете легко вычислить логарифмы в любой базе по этой формуле: logBaseN(x)=logBaseA(x)/logBaseA(N) – вы можете использовать ln (Base e = 2.718 …) или logBase10 или что угодно. Таким образом, вам действительно не нужна программа, формальный должен это сделать:

 num_digets(N, base) = 1 + floor(log(N) / log(base)) 

где N – ваш номер и base базы, в которой вы хотите, чтобы это число.

Для более подробного объяснения смотрите здесь: http://www.mathpath.org/concepts/Num/numdigits.htm

Обратите внимание, что ваша NumToStr() в вашем коде Python неверна из-за выключения на вашей базе, это должно быть:

 def NumToStr(num): str='' while num: str+=alpha[(num)%base] num=(num)/base return ''.join(list(reversed(str))) от def NumToStr(num): str='' while num: str+=alpha[(num)%base] num=(num)/base return ''.join(list(reversed(str))) 

Обратите внимание, что проверка того, что эта функция вернет правильный результат, нашла бы ошибку (например, используйте alpha="0123456789" ).

С помощью этого исправления мы получаем правильное количество цифр, используя указанную формулу:

 nDigits = int(ceil(log(nmb, base))) 

кроме точной мощности базы ( base**0 , base**1 , base**2 и т. д.), где она ровно одна меньше, чем она должна быть. Это можно исправить, слегка изменив forumla:

 nDigits = 1 + floor(log(nmb, base)) 

Обратите внимание, что даже это может показаться неудачным для некоторых входов (например, для преобразования с base-10 на base-10 он неправильно указывает 3 цифры для 1000 и 6 цифр для 1000000). Это, по-видимому, связано с присущей inprecision float, например:

 print floor(log(1000, 10)) 

выходы 2 вместо ожидаемых 3 .

Что касается вашего упоминания о производительности, я бы не стал беспокоиться о проблемах с производительностью для такого тривиального кода, пока вы не выполнили профилирование / бенчмаркинг, который показывает, что это проблема. Например, ваш «очень медленный» C-код будет занимать не более 38 делений на 10 для 128-битного номера. Если вам нужна более высокая производительность, чем это, вы столкнетесь с той же проблемой с любым тривиальным методом, упомянутым здесь. Самая быстрая вещь, о которой я могу думать, – это пользовательская функция log() использующая комбинацию таблицы поиска и линейной интерполяции, но вы должны быть осторожны с полученной точностью.

Я не уверен, что понимаю ваш вопрос. Когда вы говорите, что ваше начальное число находится в базе b1, означает ли это, что вы представляете его как строку в базе b1? Возможно, вы хотите построить некоторую таблицу, которая сообщает вам, какое число в базе b1 соответствует b2, b2 ^ 2, b2 ^ 3, … и затем сравните свой номер с этими числами, чтобы увидеть, где он подходит.

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

Вход: ваше целое число x, база b2, которую вы хотите подсчитать цифры.

 int number_of_digits (int x, int b2) { int n = 0; while (x >0) { x/=b2; n++; } return n; } 

Оба метода являются только линейными по n.

EDIT : если вы хотите быть быстрее, вы можете реализовать это как двоичный поиск. Тогда вы можете получить O (log (n)).