Архив по месяцу Апрель, 2012

Остаток от деления на 2s-1

При программировании на старых процессорах, на которых операции умножения и деления чисел выполнялись медленно, программисты прибегали к трюкам, позволявшим ускорить вычисления. Так, битовый трюк, позволяющий получить остаток от деления на число, равное точной степени двойки, остаётся актуальным и сейчас. Операция типа a&((1<<s)−1) всё ещё работает быстрее обычного деления (в том случае, когда компилятор не имеет возможности выполнить соответствующую оптимизацию). Но с тех времён забытым остался трюк, позволяющий похожим набором операций заменить вычисление остатка от деления на число, на единицу меньшее степени двойки. Рассмотрим, как он работает.

Читать далее

Конкурс по обращению матрицы завершён. Победителем объявляется неоднократный участник моих конкурсов alexBlack.

Читать далее

После вынужденного перерыва продолжаем проводить любительские конкурсы по программированию. На этот раз конкурс связан с одним из предыдущих конкурсов, посвященных точному решению целочисленной системы уравнений. Первым шагом при использовании алгоритма, основанного на p-адических аппроксимациях, является обращение исходной матрицы по модулю простого числа P. Требуется максимально ускорить эту операцию. С этой целью и проводится конкурс. В качестве P выбрано число 231-1 (максимальное простое число, которое умещается в 32 бита со знаком).

Читать далее