Как проверить, является ли данное число делимым на 15 самым быстрым способом?
Деление в процессоре занимает много времени, поэтому я хочу спросить, как наиболее быстро проверить, делится ли число на некоторое другое число, в моем случае мне нужно проверить, делится ли число на 15.
Также я просматривал сеть и нашел веселье способы проверить, делится ли число на некоторое число, но я ищу быстрый вариант.
НОТА: так как деление занимает много времени, я ищу ответ без / а также %,
Решение
Умножение занимает меньше времени, чем деление, поэтому вы можете попробовать это:
inline bool divisible15(unsigned int x)
{
//286331153 = (2^32 - 1) / 15
//4008636143 = (2^32) - 286331153
return x * 4008636143u <= 286331153u;
}
Этот способ работает, потому что 2^32-1 (максимальное 32-битное значение) делится на 15, однако, если вы возьмете, например, 7, это будет выглядеть как работа, но не будет работать во всех случаях.
РЕДАКТИРОВАТЬ: Увидеть этот, это доказывает, что это решение (на некоторых компиляторах) быстрее, чем модуль.
РЕДАКТИРОВАТЬ: Вот это объяснение и обобщение.
Другие решения
Обязательный ответ для других учеников, которые могут прийти, чтобы найти ответ.
if (number % n == 0)
В самый случаев, вы всегда можете сделать это, доверяя умным современным компиляторам.
Это не значит, что вы разочаровываетесь в изучении забавных способов. Проверьте эти ссылки.
Просто используйте i % 15 == 0
-
Поскольку компилятор может легко увидеть, что 15 никогда не изменится, он может свободно вносить любые необходимые изменения в работу мода. Это задача авторов компиляторов — делать такого рода оптимизацию, если они не подумали о лучшем способе сделать это, чего вы не сделаете.
-
Например, очень легко проверить, делится ли число на 2, потому что вы просто проверяете первый бит. Авторы компиляторов знают это, и вы можете написать код самостоятельно, чтобы проверить первый бит, но особенно зрелый компилятор заставит людей задуматься над этими вещами годами. Этот тип оптимизации сделать очень просто, так как для этого нужно всего лишь изменить инструкцию или 2, а достичь таких оптимизаций, как лучшее распределение регистров, гораздо сложнее.
-
Еще одна вещь, которую следует учитывать, это то, что ваш компилятор был написан для той системы, в которой он работает, код, с другой стороны, везде одинаков, если вы пишете какой-то странный код, который может быть столь же быстрым в одной системе (возможно, все же не быстрее). ) но в другой системе, которая имеет специальную аппаратную оптимизацию, ваш код может потерять на порядок. Поскольку вы написали некоторый эзотерический код для проверки делимости, компилятор вряд ли поймет, что он может оптимизироваться под одну аппаратную операцию, поэтому написание очевидных вещей делает жизнь лучше и проще для компилятора.
-
Поскольку вы на самом деле не проверяли, что скорость имеет значение при написании кода, странный способ сделает код очень трудным для чтения для следующего человека и более подвержен ошибкам ( преждевременная оптимизация — корень зла)
-
Он по-прежнему работает независимо от того, является ли ввод 16, 32 или 64 битами, поскольку он не зависит от битовых манипуляций.
-
Даже если автор компилятора не реализовал это, вполне возможно, что кто-то может реализовать это (даже сам)
В относительно современном процессе деление на 15 не должно быть таким ужасным. Руководство по оптимизации AMD определяет его на основе отношения (значение, которое делится), и оно занимает 8 + разрядную позицию старшего значащего бита отношения. Так что, если у ваших чисел установлен 63-й бит, вы получите 71 цикл — это довольно длинная инструкция, конечно. Но для 32-битного числа с несколькими нулями в старших битах мы говорим 30-40 циклов. Если число вписывается в 16-битное значение, у нас максимум составляет 23 цикла.
Чтобы получить остаток, это еще один тактовый генератор.
Если вы делаете это ВСЕ время, конечно, вы можете обнаружить, что это время довольно длительное, но я не уверен, что есть тривиальный способ избежать этого.
Как уже говорили другие, компилятор может заменить его чем-то лучшим. Но 15, насколько мне известно, не имеет очевидного быстрого решения (если у вас есть 16 вместо 15, то мы можем использовать хитрость x & 15).
Если это ограниченный диапазон, вы можете построить таблицу [vector<bool> например, который будет хранить 1 бит на запись], но вы довольно скоро столкнетесь с проблемой, заключающейся в том, что доступ к некэшированной памяти занимает столько же времени, сколько операция деления …
Есть несколько интересных способов выяснить, делится ли число на 3, 5 и т. Д., Суммируя цифры, но, к сожалению, они работают только на основе десятичных цифр, что включает в себя длинную последовательность делений.
Вот еще один подход, который, вероятно, медленнее, чем другие, но использует только сложение, поразрядно и смещение:
int divisible15(unsigned int x) {
if (x==0) return 1;
x = (x & 0x0f0f0f0f) + ((x&0xf0f0f0f0)>>4);
x = (x & 0x00ff00ff) + ((x&0xff00ff00)>>8);
x = (x & 0x0000ffff) + ((x&0xffff0000)>>16);
x = (x & 0x0f) + ((x&0xf0)>>4);
return x==15;
}
Идея состоит в том, что деление на 15 в базе 16 похоже на деление на 9 в базе 10 — сумма цифр должна делиться на 15.
Таким образом, код суммирует все шестнадцатеричные цифры (аналогично тому, как вы подсчитываете биты), и сумма должна равняться 15 (кроме 0).
Ну, это очень легко сделать в вашей голове, если у вас есть шестнадцатеричное представление. Просто сложите все цифры, пока не получите одну цифру. Если ответ «0xf», он делится на 15.
пример 0x3a98 : 3 + 0xa + 9 + 8 = 0x1e = 1 + 0xe = 0xf, так что это делится на 15.
Это работает для всех факторов на X-1, где X — основа, используемая для представления числа. (Для факторов меньшего размера последняя цифра должна делиться на коэффициент).
Не ожидайте, что это будет быстро в коде, хотя.