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

Текущая версия на 14:37, 20 мая 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'е преобразованием:

Имитация переполнения знакового регистра (N = 4)  

[править] Ссылки

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