есть быстрый алгоритм, аналогичный мощности 2, который можно использовать с 3, т. Е. N% 3. Возможно, что-то, что использует тот факт, что если сумма цифр делится на три, то число также делится.Быстрое modulo 3 или алгоритм деления?
Это приводит к следующему вопросу. Каков быстрый способ добавления цифр в число? То есть 37 -> 3 +7 -> 10 Я ищу что-то, что не имеет условными, как те, как правило, подавляют векторизации
благодаря
4 % 3 == 1, поэтому (4^k * a + b) % 3 == (a + b) % 3. Вы можете использовать этот факт для оценки х% 3 для 32-разрядных х:
x = (x >> 16) + (x & 0xffff);
x = (x >> 10) + (x & 0x3ff);
x = (x >> 6) + (x & 0x3f);
x = (x >> 4) + (x & 0xf);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
x = (x >> 2) + (x & 0x3);
if (x == 3) x = 0;
(. Непроверенные - вы, возможно, потребуется несколько больше сокращений) Является ли это быстрее, чем аппаратное обеспечение может сделать х% 3? Если да, то, вероятно, это не так много.
Это действительно быстрее, чем 'x% 3'? См. Https://godbolt.org/g/aRbqrW – plasmacel
Не уверен, что ваш первый вопрос, но для второго, вы можете взять преимущество % оператора и целочисленного деления:
int num = 12345;
int sum = 0;
while (num) {
sum += num % 10;
num /= 10;
}
Это работает, потому что 12345 % 10 = 5, 12345/10 = 1234 и продолжайте идти до num == 0
+1 Ницца # 2. решение. –
Да, это то очевидное решение. Однако деление и по модулю очень дорогие операции, порядка ста циклов на моей платформе. Меня больше интересует то, что не связано с ними. Я должен сказать, что это вопрос чисто любопытства. – Anycorn
Это comp.compilers item имеет конкретную рекомендацию для вычисления по модулю 3.
альтернатива, особенно если размер Maximium дивидендов является скромным, это умножить на величину, обратную 3 в качестве значения с фиксированной точкой, с достаточно бит точности для обработки максимального размера дивиденда для вычисления частного, а затем вычесть 3 * quotient из дивиденда, чтобы получить остаток. Все эти умножения могут быть реализованы с фиксированной последовательностью сдвигов и добавлений. Количество инструкций будет зависеть от битовой диаграммы обратного. Это работает очень хорошо, когда размер дивиденда max является скромным по размеру.
Что касается добавления цифр числа ... если вы хотите добавить десятичные цифры, вы будете в конечном итоге делает то, что составляет число преобразующая-к-десятичного знака, который включает в себя деление на 10 где-то , Если вы готовы согласиться на добавление цифр в base2, вы можете сделать это с помощью простого переключения смены и добавления. Различные хитроумные трюки можно использовать для этого в кусках N бит, чтобы ускорить его.
Добавление цифр не будет работать в этом случае, потому что вам придется преобразовать число сначала в десятичное число, которое занимает _much_ больше времени, чем просто деление. –
Что вы на самом деле пытаетесь достичь? Если это не теоретическое любопытство, я сомневаюсь, что эта конкретная проблема может быть узким местом применения в реальном мире ... –
это и практическое, и теоретическое. вопрос возникает из-за попытки распределить несколько вложенных циклов над декартовыми центрами среди потоков (Cuda конкретно, но это не важно). Я уже решил проблему по-другому, но все же хотел бы знать, есть ли способ. Это реальное узкое место, поскольку целочисленное деление и модуляция намного дороже, чем реальные операции с плавающей запятой, которые я пытаюсь сделать параллельными. – Anycorn