Как округлить число в меньшую сторону кратное числу?

Question

[GRO24]

Уверен что мое решение не самое изящное.
Есть количество участвующих: допустим, 187.
Есть количество победителей: например, 5.

Мне нужно округлить количество участвующих так, чтобы на выходе при делении этого числа постоянно 2 я получил число 5 в итоге
В данном примере получается число 160; (160/2=80/2=40/2=20/2=10/2=5) - надеюсь тут не запутал.

Я решил это с помощью цикла:

$input = 187;
$output = 5;
while (true) {
	if($output > $input):
		$output = $output/2;
		break;
	endif;
	$output = 2*$output;

}
	echo $output;

А как бы сделали вы?

Comments

[GRO24]

John Didact, то 96)

[John Didact]

А если input = 4?

[FanatPHP]

John Didact, запусти программку-то, она тебе посчитает

[FanatPHP]

ни о какой "кратности" тут речь не идёт
тебе нужен максимальный результат геометрической прогрессии, которые меньше заданного числа

[GRO24]

FanatPHP, я честно старался сформулировать, не вышло)

[John Didact]

GRO24, не, не... Я не так написал, по-другому написал потом. А если input = 4.

[John Didact]

FanatPHP, я не умею запускать. Я нуб.

[GRO24]

John Didact, там по другому условию нет возможности что инпут может быть меньше аута
Не рассматривал даже этот вариант

[John Didact]

FanatPHP, ты не прав, ему нужен дедушка.

[John Didact]

GRO24, а если бы у бабушки был пипиндр? М?

[FanatPHP]

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

while ($output*2 < $input) {
    $output *= 2;
}
echo $output;

но это потенциально неоптимально, поскольку само вычисление может быть сложным, и делать его два раза тоже не фонтан
можно добавить промежуточную переменную

$limit = 187;
$input = 4;
do {
    $output = $input;
} while (($input *= 2) < $limit);
echo $output;

[GRO24]

FanatPHP, Спасибо за развернутый ответ)

Answer 1

[Adamos]

Деление пополам могло навести на более компьютерные мысли.
Алгоритм нахождения такого числа для N участников при количестве победителей X:
Нацело поделить N на X, оставить в результате только старший значащий бит, умножить это на X.
187 / 5 = 37 = 100101b
100000b * 5 = 160

Comments

[Talgat_Sat]

вау ,классная мысль

[Karpion]

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

[Adamos]

Karpion, выделить "найти старший значащий бит" в вашем комментарии, щелкнуть по выделению правой кнопкой, выбрать "искать в Гугле", на первой же странице выдачи увидеть, например, статью на Хабре.

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

Answer 2

[Talgat_Sat]

Легче сделать математически ,

<?php
$input = 187;
$output = 5;
$buf=log ( intdiv($input, $output ),2 );
echo(round ( $buf, 0 ,  PHP_ROUND_HALF_UP ) );

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

Comments

[GRO24]

Не знаю на сколько легче, конечно) Но, интересно) Спасибо)

[Илья]

Ваш код выводит 5, а должно получиться 160.

sandbox.onlinephpfunctions.com/code/f59658cd7f897b...

[Talgat_Sat]

можно через рекурсию
GRO24,

[Talgat_Sat]

Илья, возведите 2 в ответ b умножьте на 5 , т.е 5*(2^5)=160

[Илья]

Talgat_Sat, Да, только что дошло. Не сказать что проще для понимая, но вполне себе вариант. Единственное, у вас округление по мат. правилам, а автору, насколько я понял, нужно в меньшую сторону:

function ($input = 1, $output = 4) {

	$sqrt = floor(log(intdiv($input, $output), 2));

	return 2 ** $sqrt * $output;
}