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

Логарифмы не должны быть медленными. И вы можете легко вычислить логарифмы в любой базе по этой формуле: 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)).