2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Равенство с целочисленными функциями и логарифмами
Сообщение18.03.2019, 16:20 
Для заданного положительного числа $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$. Интересуют остальные случаи.

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

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение18.03.2019, 16:31 
kisupov в сообщении #1382698 писал(а):
В тривиальном случае, когда $a = 2^n$, где $n$ - целое, ответом будет $b = a$, так как любое число, превышающее $a$, приведет к увеличению на единицу $\lceil \log_2 a \rceil$.

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

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

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение18.03.2019, 16:40 
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$.

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение18.03.2019, 17:13 
kisupov в сообщении #1382705 писал(а):
Возник вопрос, при какой максимальной погрешности в $b$ (то есть максимальной разнице $b-a$) я получу правильный результат, вычисляя $q = \lceil \log_2 b \rceil$.

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

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

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение18.03.2019, 18:52 
Для того, чтобы ошибки не было, необходимо $\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$.

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение26.02.2023, 12:01 
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$

 
 
 
 Re: Равенство с целочисленными функциями и логарифмами
Сообщение26.02.2023, 20:20 
Аватара пользователя
Полагая, что знак означает "минимальное целое, большее аргумента", видим, что надо брать максимальное b, для которого
$\lceil \log_2 a \rceil  = \lceil \log_2 b \rceil$
то есть $b=2^{\lceil \log_2 a \rceil}$

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group