11.11.2015 Взять и поделить или деление по модулю

Версия 16:21, 12 февраля 2016

Есть некоторая неуверенность в результатах работы функций взятия модуля, для борьбы с которой составлена эта памятка.

Лично я привык к работе функции mod(a, b) в MATLAB, которая приводит a к диапазону [0 b] или [b 0] (в зависимости от знака b) путем прибавления/вычитания целого числа b к/из a. Что выражается в формуле:

mod(a, b) = a - floor(a ./ b)*b,

где функция floor - округление в сторону минус бесконечности.

Операция взятия остатка по модулю замечательна своими свойствами:

(a+b)mod n = [a(mod n) + b(mod n)]mod n

(a-b)mod n = [a(mod n) - b(mod n)]mod n

(a*b)mod n = [a(mod n) * b(mod n)]mod n

[c*(a+b)]mod n = [c*a(mod n) + c*b(mod n)]mod n

Как оказалось, делить можно по-разному, в зависимости от функции, которую мы используем для округления^[1]:

• truncated division modulo - используется функция fix() - округление в сторону нуля, в результате имеем остаток от деления абсолютных значений аргументов, знак используем от первого.
• floored division modulo - используется функция floor() - округление в сторону минус бесконечности, в результате приводим число к интервалу [0 b] для положительных b или [b 0] для отрицательных.
• и т.д.

Для себя я теперь разделяю понятия остатка от деления (remainder after devision) и приведения числа по модулю (modulus after devision) соответственно.

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

Так какие функции и операторы реализуют остаток от деления, какие взятие по модулю, и как они зависят от типов аргументов? Ниже представлены результаты, полученные на Oryx 161, компилятор из Xilinx SDK 2014.4 ( gcc version 4.8.3 20140320 (prerelease) (Sourcery CodeBench Lite 2014.05-23)).

Оператор %

Следует обратить внимание:

• int a % uint b = mod(*(uint*(&a)), b) - результаты для -13%(int 7) и -13%(uint 7) различаются; если брать int % uint, то int интерпретируется как uint, например, -1 превращается в 2^32-1.
• uint a % int b = b<0 ? a : mod(a, b) - взятие uint % отрицательного числа - холостая операция, результат - исходный uint
• int a % int b = sign(a) * mod(|a|, |b|) - как подсказывает стандарт, до C (ISO 1999) и C++ (ISO 2011) знак зависел от реализации, теперь же применяется знак делимого
• int a % int b = (MATLAB)rem(a, b) - ведет себя как функция rem() в MATLAB: rem(a, b) = a - fix(a/b)*b, где fix() - функция округления в сторону нуля
• int a % int b ведет себя как функция mod() в MATLAB только при совпадении знаков аргументов, иначе есть смещение на b (за исключением точек, в которых результат ноль)

Выводы:

• Оператор % дает в нашей системе остаток от деления (truncated division modulo)
• Функция mod() в MATLAB производит floored modulo, функция rem() в MATLAB - truncated modulo.

Для наглядности построены графики (доступен fig):

Оператор %, MATLAB mod()  

Функция fmod

Функция^[2]:

возвращает остаток от деления в виде числа с плавающей точкой (numer - tquot * denom), где tquot - результат округления в сторону нуля дроби numer/denom. Иначе говоря, функция использует truncated division или функцию fix(). От знака второго аргумента результат не зависит. Буква f в названии функции - отсылка к float, а не floored!

fmod() /доступны fig/  

Функция remainder

Функция^[3]:

аналогична fmod(), но использует округление к ближайшему целому, то есть функцию round вместо fix. От знака второго аргумента результат не зависит.

remainder() /доступны fig/  

Макрос umod

Для имитации matlab'овского mod() для целых чисел у нас существует макрос umod:

При положительных y она работает как и ожидается - реализует floored modulo, при отрицательных есть проблемы.

umod() /доступны fig/  

Кроме того, если в неё мешать использование uint и int, то можно получить интересные эффекты, описанные выше.

Макрос ufmod

Аналогичен umod, но использовался для чисел типа double. Вызывал ошибки, поэтому сейчас не используется.

Графики показывают, что макрос дает ошибочные значения для отрицательных чисел.

ufmod() /доступны fig/  

Кроме того, если в неё мешать использование uint и int, то можно получить интересные эффекты, описанные выше.

Функция flmod(int, int)

Для исправления недостатков макроса umod создана функция flmod(int, int):

Результаты её выполнения совпадают с MATLAB mod(), она реализует floored modulo:

flmod(int, int) /доступны fig/  

Функция flumod(unsigned int, int)

Функция возвращает floored modulo для пары (unsigned int, int)

Результаты её выполнения совпадают с MATLAB mod():

flumod(unsigned int, int)  

Результаты тестов на большие входные значения:

Функция flmod2POW32(int)

Функция возвращает floored modulo для пары (2^32, int)

Результаты тестов (совпадают с octave):

Функция flfmodstep(double, double)

При переполнениях возникает задача сделать один шаг операции floored mod, прибавить или удалить только один base

flfmodstep(double, double) /доступны fig/  

double flfmodstep(double x, double y){
    if (y > 0) {
        if (x < 0)
            return x + y;
        else {
            if (x < y)
                return x;
            else
                return x - y;
        }
    } else if (y < 0) {
        if (x > 0)
            return x + y;
        else {
            if (x > y)
                return x;
            else
                return x - y;
        }
    } else {
        return 0.0;
    }
}

Симуляция переполнения знакового регистра

Пусть есть регистр, значение которого интерпретируется как число в доп.коде. Тогда переполнение регистра можно имитировать в MATLAB'е преобразованием:

Имитация переполнения знакового регистра  

Ссылки

1. ↑ Wiki: Modulo operation
2. ↑ http://www.cplusplus.com/reference/cmath/fmod/
3. ↑ http://www.cplusplus.com/reference/cmath/remainder/