Равенство с целочисленными функциями и логарифмами

[kisupov]

Для заданного положительного числа $a$ нужно найти максимальное положительное число $b$, $b \ge a$, при котором выполняется следующее равенство:

$$ \lceil \log_2 a \rceil = \lceil \log_2 b \rceil. $$

В тривиальном случае, когда $a = 2^n$, где $n$ - целое, ответом будет $b = a$, так как любое число, превышающее $a$, приведет к увеличению на единицу $\lceil \log_2 a \rceil$. Интересуют остальные случаи.

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

[ewert]

kisupov в сообщении #1382698 писал(а):

В тривиальном случае, когда $a = 2^n$, где $n$ - целое, ответом будет $b = a$, так как любое число, превышающее $a$, приведет к увеличению на единицу $\lceil \log_2 a \rceil$.

Если это так, то имелось в виду округление вверх (а для стандартного округления, т.е. вниз, задача и некорректна).

Я так понял, что Вас затрудняет запись ответа. Наиболее разумный вариант: "если $a\in[2^n;2^{n+1})$, то...". Можно, конечно, повозиться с записью через разные целые части и логарифмы, но это, на мой вкус, будет извращением.

[kisupov]

ewert в сообщении #1382701 писал(а):

kisupov в сообщении #1382698 писал(а):

В тривиальном случае, когда $a = 2^n$, где $n$ - целое, ответом будет $b = a$, так как любое число, превышающее $a$, приведет к увеличению на единицу $\lceil \log_2 a \rceil$.

Если это так, то имелось в виду округление вверх (а для стандартного округления, т.е. вниз, задача и некорректна).

Я так понял, что Вас затрудняет запись ответа. Наиболее разумный вариант: "если $a\in[2^n;2^{n+1})$, то...". Можно, конечно, повозиться с записью через разные целые части и логарифмы, но это, на мой вкус, будет извращением.

Задачка возникла из практики. Есть некоторая величина $q$, точное значение которой определяется так: $q = \lceil \log_2 a \rceil$, где $a$ - некоторое положительное число. Но $a$ вычислить сложно, и вместо него я использую приближенный аргумент $b$, причем известно, что $b \ge a$. Возник вопрос, при какой максимальной погрешности в $b$ (то есть максимальной разнице $b-a$) я получу правильный результат, вычисляя $q = \lceil \log_2 b \rceil$.

[ewert]

kisupov в сообщении #1382705 писал(а):

Возник вопрос, при какой максимальной погрешности в $b$ (то есть максимальной разнице $b-a$) я получу правильный результат, вычисляя $q = \lceil \log_2 b \rceil$.

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

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

[LMA]

Для того, чтобы ошибки не было, необходимо $\log_2 b \leq q$. Это можно переписать так: $b \leq 2^{\lceil \log_2 a \rceil}$. Т.е. максимальная разница $2^{\lceil \log_2 a \rceil} - a$. Например, для $a=3.99$ эта разница равна $0.01$.

[wrest]

kisupov в сообщении #1382705 писал(а):

Есть некоторая величина $q$, точное значение которой определяется так: $q = \lceil \log_2 a \rceil$, где $a$ - некоторое положительное число. Но $a$ вычислить сложно, и вместо него я использую приближенный аргумент $b$, причем известно, что $b \ge a$. Возник вопрос, при какой максимальной погрешности в $b$ (то есть максимальной разнице $b-a$) я получу правильный результат, вычисляя $q = \lceil \log_2 b \rceil$.

Максимально будет $b-a=a$. Пример. Пусть $a=2^{63}+1$ тогда $\lceil \log_2 a\rceil =64$ и тогда при $b=2^{64}$ получаем $\lceil \log_2 b\rceil=64$ и $b-a=2^{63}-1=9223372036854775807$

[Евгений Машеров]

Полагая, что знак означает "минимальное целое, большее аргумента", видим, что надо брать максимальное b, для которого
$\lceil \log_2 a \rceil = \lceil \log_2 b \rceil$
то есть $b=2^{\lceil \log_2 a \rceil}$