Лингвофорум

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

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

знаю конкретную задачу: сколько цифр в 2^100. сказать?

Кажи.

вобшем. 2^10 это 1024. можно считать за =10^3, потому что 24 это достаточно мало. (2^10)^10=10^30. 30 нулей и одна единица. и того 31.

вдруг пригодитса. 

Максимальное число, состоящее из n бит, равно 2ⁿ-1.
Максимальное число, состоящее из m десятичных цифр, равно 10^m-1.
Если мы хотим записать n-битное число в десятичной форме, то максимальное двоичное должно умещаться в максимальном десятичном:
2ⁿ-1 ≤ 10^m-1
2ⁿ ≤ 10^m
m ≥ log₁₀2ⁿ
m ≥ n•log₁₀2 ≈ n•0,30102999566398119521373889472449
Остается найти наименьшее целое число, соответствующее этому условию.

Интересненько.

Нагуглил вот чё:

Цитата: http://php.net/manual/en/function.log.php

#--------------------------------------------------------
#     How many digits does an integer have?
#--------------------------------------------------------

function digit_count($n, $base=10) {

  if($n == 0) return 1;

  if($base == 10) {
    # using the built-in log10(x)
    # might be more accurate than log(x)/log(10).
    return 1 + floor(log10(abs($n)));
  }else{
    # here  logB(x) = log(x)/log(B) will have to do.
   return 1 + floor(log(abs($n))/ log($base));
  }
}

Т.е. для дестятичного:
m = E(log₁₀|n|)+1

Интересно почему это отличается от вашего вывода.

Цитата: Python от марта 14, 2011, 13:07
m ≥ n•log₁₀2 ≈ n•0,30102999566398119521373889472449
Остается найти наименьшее целое число, соответствующее этому условию.

Если грубо округлить то m = n/3. Выходит у вас функция линейная.

Там же функция логарифмическая, что интуитивно более реально.

А зочем тебе?

В логарифмической функции n — не количество разрядов, а само число.

Цитата: RawonaM от марта 14, 2011, 15:07
Если грубо округлить то m = n/3.

Дык, правильно: 2³ ≈ 10¹.

3/10 гораздо точнее, сохраняя краткость ^^
2¹⁰ ≈ 10³ - с этим уже можно на производство.

Нельзя. Дробную часть необходимо округлить к верхнему пределу — т.е., прибавить единицу, иначе 1000...1023 вылезет з пределы.

Цитата: basta от марта 14, 2011, 15:31
3/10 гораздо точнее, сохраняя краткость ^^

А кто просил точнее?

Вроде, так:

Если
— число знаков в двоичной записи,
— число знаков в десятичной записи,
тогда:

Цитата: myst от марта 14, 2011, 15:26

ЦитироватьЕсли грубо округлить то m = n/3.

Дык, правильно: 2³ ≈ 10¹.

Это для восмеричной системы получается. Впрочем, в практических целях это возможно лучший вариант, но в теории неточный.

Ничо нипонил. Ты чего хочешь-то?

Цитата: myst от марта 15, 2011, 09:19
Ничо нипонил. Ты чего хочешь-то?

Точную формулу. 2³ = 8¹, а не 10.

Цитата: RawonaM от марта 15, 2011, 09:46
Точную формулу.

Тебе же выше её дали.

Цитата: RawonaM от марта 15, 2011, 09:46
2³ = 8¹, а не 10.

Я какбэ в курсе. Хочешь большего приближения, возьми
2³⁰ и 10⁹, например.

9/30 сократимая дробь.

Цитата: basta от марта 15, 2011, 10:28
9/30 сократимая дробь.

Спасибо Кэп.

Цитата: RawonaM от марта 15, 2011, 09:46
Точную формулу.

Очевидно, что минимальное натуральное число, которое имеет -ичную запись из символов — это , а максимальное — .
Следовательно, число символов для записи числа в -ичной системе оценивается так:

то есть,

(Это точное равенство)

Пусть у нас есть две системы счисления: и , и известно, что в системе число записывается знаками. Найдём число — число знаков в записи   в системе :





Обе оценки достижимы. Нижнюю оценку по-другому можно записать как .

Если надо верхнюю оценку записать в такой форме, её придётся чуть-чуть ухудшить. Она перестанет быть достижимой:

Точная формула — берем количество бит, умножаем на log₁₀2 (который можно посчитать в калькуляторе. Можно запомнить приблизительное значение — 0.30103, как правило, этого достаточно), округляем к верхнему пределу (точно не помню, какие закорючки придумали математики для этой операции, в некоторых языках есть функция ceiling; поскольку дробная часть в иррациональном числе будет всегда, можно просто выделить целую часть и прибавить единицу). PROFIT.

Вот-вот, целую страницу формулами зафлудили по чём зря.

Спасибо всем за участие
Вообще какбе осталось непонятно, интересны людям такие теоретическо-практические вопросы или это только я один такой?