Сколько цифр в этой базе?

Question

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

Например: Десятичное число 100006 может быть представлено 17,11,9,8,7,6,8 цифрами в базах 2,3,4,5,6,7,8 соответственно.

Итак, формула, которую я до сих пор получил, выглядит следующим образом: (log10 (num) / log10 (base)) + 1.

в C / C ++ Я использовал эту формулу для вычисления приведенных выше результатов.

long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;

Но, к сожалению, формула не дает правильного ответа в некоторых случаях, например:

Number 8 in  base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 64 in  base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6

Number 64 in  base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 125 in  base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 128 in  base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7

Number 216 in  base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3

Number 243 in  base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5

Number 343 in  base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3

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

Редактировать: В соответствии со спецификацией ввода мне приходится иметь дело со случаями, такими как 10000000000, т.е. 10 ^ 10, я не думаю, что log10 () в C / C ++ может обрабатывать такие случаи? Поэтому любая другая процедура / формула для этой проблемы будет высоко оценена.

Answer 1

В настройках компилятора есть быстрые плавающие операции. Вам нужны точные операции флотации. Дело в том, что log10 (8) / log10 (2) всегда 3 в математике. Но, может быть, ваш результат 2.99999, например. Это плохо. Вы должны добавить небольшую добавку, но не 0,5. Это должно быть около .00001 или что-то в этом роде.

Почти верная формула:

int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);

Действительно верное решение

Вы должны проверить результат своей формулы. Сложность O(log log n) или O(log result)!

int fast_power(int base, int s)
{
    int res = 1;
    while (s) {
        if (s%2) {
            res*=base;
            s--;
        } else {
            s/=2;
            base*=base;
        }
    }
    return res;
}

int digits_size(int n, int base)
{
    int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
    return fast_power(base, s) > n ? s : s+1;
}

Эта проверка лучше теста грубой силы с умножением base.

Answer 2

Будет работать любое из следующих действий:

>>> from math import *
>>> def digits(n, b=10):
...     return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
...     return int(ceil(log(n + 1, b))) if n else 1
... 

Первая версия описана на mathpath.org . Во второй версии + 1 необходимо для получения правильного ответа для любого числа n , которое является наименьшим числом с d цифрами в базе b . То есть те числа, которые написаны 10 ... 0 в базе b . Обратите внимание, что ввод 0 должен рассматриваться как особый случай.

Десятичные примеры:

>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3

Binary:

>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11

Редактировать : OP указывает, что решение log может не работать для больших входов. Я не знаю об этом, но если так, следующий код не должен ломаться, потому что он использует только целочисленную арифметику (на этот раз в C):

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 0;
  while (d++, n /= b);
  return d;
}

Этот код, вероятно, будет менее эффективным. И да , это было написано для максимальных точек незаметности. Он просто использует наблюдение, что каждое число имеет хотя бы одну цифру, и что каждое деление на b, которое не дает 0, подразумевает существование дополнительной цифры. Более читаемая версия выглядит следующим образом:

unsigned int 
digits(unsigned long long n, unsigned long long b)
{
  unsigned int d = 1;
  while (n /= b) {
    d++;
  }
  return d;
}

Answer 3

Количество цифр цифры в данной базе

Answer 4

Поскольку ваша формула верна (я только что попробовал), я думаю, что это ошибка округления в вашем делении, в результате чего число будет чуть меньше целочисленного значения, которое должно быть. Поэтому, когда вы усекаете целое число, вы теряете 1. Попробуйте добавить дополнительные 0,5 к вашему окончательному значению (чтобы усечение было на самом деле круглой операцией).

Answer 5

Требуется потолок (= наименьшее целое число, не превышающее) log _b (n + 1), а не то, что вы рассчитываете прямо сейчас, floor (1 + log _{b *) 1004 * (п)).}

Вы можете попробовать:

int digits = (int) ceil( log((double)(n+1)) / log((double)base) );

Answer 6

Как уже отмечали другие, у вас есть ошибка округления, но предложенные решения просто перемещают опасную зону или уменьшают ее, но не устраняют. Если ваши числа целые, то вы можете проверить - , используя целочисленную арифметику - что одна степень основания меньше или равна вашему числу, а следующая выше него (первая степень - это число цифр). Но если вы будете использовать арифметику с плавающей запятой где-нибудь в цепочке, то вы будете подвержены ошибкам (если ваша база не является степенью двойки, а может быть, даже тогда).

EDIT:
Вот грубое, но эффективное решение в целочисленной арифметике. Если ваши целочисленные классы могут содержать числа, большие как базовое *, это даст правильный ответ.

  size = 0, k = 1;
  while(k&lt=num)
    {
      k *= base;
      size += 1;
    }

Answer 7

Используя вашу формулу,

log(8)/log(2) + 1 = 4

проблема в точности вычисления логарифма. Использование

ceil(log(n+1)/log(b)) 

должен решить эту проблему. Это не совсем то же самое, что

ceil(log(n)/log(b)) 

потому что это дает ответ 3 для n = 8 b = 2, и при этом он не совпадает с

log(n+1)/log(b) + 1

, поскольку это дает ответ 4 для n = 7 b = 2 (при расчете с полной точностью).

Я на самом деле получаю несколько любопытных результатов в результате реализации и компиляции первой формы с помощью g ++:

double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);

терпит неудачу (IE дает ответ 3), в то время как,

double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);

успешно (дает ответ 4). Глядя на это еще немного, я думаю, что третья форма

ceil(log(n+0.5)/log(b)) 

будет более стабильным, потому что он избегает «критического» случая, когда n (или n + 1 для второй формы) является целой степенью b (для целых значений n).

Answer 8

static int numInBase(int num, int theBase)
{
   if(num == 0) return 0;
   if (num == theBase) return 1;
   return 1 + numInBase(num/theBase,theBase);
}

Answer 9

Вот решение в bash:

% digits() { echo $1 $2  opq | dc | sed 's/ .//g;s/.//' | wc -c; }


% digits 10000000000 42
7

Answer 10

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