Один из моих любимцев ненавидит C-производные языки (как математик) состоит в том, что
(-1) % 8 // comes out as -1, and not 7
fmodf(-1,8) // fails similarly
Какое лучшее решение?
С++ позволяет использовать шаблоны и перегрузку оператора, но для меня это мутные воды. примеры с благодарностью получены.
Прежде всего, я хотел бы отметить, что вы даже не можете полагаться на то, что (-1) % 8 == -1. единственное, на что вы можете положиться, это (x / y) * y + ( x % y) == x. Однако независимо от того, является ли остаток отрицательным, определяется реализация.
Теперь зачем использовать шаблоны здесь? Перегрузка для ints и longs будет делать.
int mod (int a, int b)
{
int ret = a % b;
if(ret < 0)
ret+=b;
return ret;
}
и теперь вы можете называть его как mod (-1,8), и он будет казаться 7.
Изменить: я обнаружил ошибку в моем коде. Он не работает, если b отрицательный. Поэтому я думаю, что это лучше:
int mod (int a, int b)
{
if(b < 0) //you can check for b == 0 separately and do what you want
return mod(a, -b);
int ret = a % b;
if(ret < 0)
ret+=b;
return ret;
}
Ссылка: С++ 03, пункт 5.6, раздел 4:
Двоичный/оператор дает частное, а бинарный оператор% дает остаток от деления первого выражения на второе. Если второй операнд/или% равен нулю, поведение undefined; в противном случае (a/b) * b + a% b равно a. Если оба операнда неотрицательны, то остаток неотрицателен; , если нет, знак остатка определяется реализацией.
Вот функция C, которая обрабатывает положительное ИЛИ отрицательное целое ИЛИ дробные значения для ОБОИХ ОПЕРАНДОВ
#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)
Это, безусловно, самое элегантное решение с математической точки зрения. Тем не менее, я не уверен, что он надежен в обработке целых чисел. Иногда возникают ошибки с плавающей точкой при преобразовании int → fp → int.
Я использую этот код для не-int s, и отдельную функцию для int.
ПРИМЕЧАНИЕ: нужно ловить N = 0!
Код тестера:
#include <math.h>
#include <stdio.h>
float mod(float a, float N)
{
float ret = a - N * floor (a / N);
printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);
return ret;
}
int main (char* argc, char** argv)
{
printf ("fmodf(-10.2, 2.0) = %f.1 == FAIL! \n\n", fmodf(-10.2, 2.0));
float x;
x = mod(10.2f, 2.0f);
x = mod(10.2f, -2.0f);
x = mod(-10.2f, 2.0f);
x = mod(-10.2f, -2.0f);
return 0;
}
(Примечание: вы можете скомпилировать и запустить его прямо из CodePad: http://codepad.org/UOgEqAMA)
Выход:
fmodf (-10.2, 2.0) = -0.20 == FAIL!
10.2 мод 2.0 = 0.2
10,2 мод -2.0 = -1.8
-10.2 мод 2.0 = 1,8
-10.2 mod -2.0 = -0.2
Я только что заметил, что Bjarne Stroustrup называет % как оператор остаток, а не оператор modulo.
Я бы поспорил, что это его формальное имя в спецификациях ANSI C и С++, и что злоупотребление терминологией закралось. Кто-нибудь знает это для факта?
Но если это так, то функция C fmodf() (и, возможно, другие) очень вводит в заблуждение. они должны быть помечены как fremf() и т.д.
Для целых чисел это просто. Просто сделайте
(((x < 0) ? ((x % N) + N) : x) % N)
где я предполагаю, что N положителен и представим в типе x. Ваш любимый компилятор должен иметь возможность оптимизировать это, так что он заканчивается только одной операцией mod в ассемблере.
Лучшим решением для математика является использование Python.
Перегрузка оператора С++ имеет мало общего с этим. Вы не можете перегружать операторов для встроенных типов. То, что вы хотите, просто функция. Конечно, вы можете использовать С++ templating для реализации этой функции для всех соответствующих типов всего за 1 кусок кода.
Стандартная библиотека C предоставляет fmod, если я правильно помню имя для типов с плавающей запятой.
Для целых чисел вы можете определить шаблон функции С++, который всегда возвращает неотрицательный остаток (соответствующий евклидову делению) как...
#include <stdlib.h> // abs
template< class Integer >
auto mod( Integer a, Integer b )
-> Integer
{
Integer const r = a%b;
return (r < 0? r + abs( b ) : r);
}
... и просто напишите mod(a, b) вместо a%b.
Здесь тип Integer должен быть объявленным целым типом.
Если вы хотите, чтобы общее математическое поведение, когда знак остатка совпадает с знаком делителя, вы можете сделать, например,
template< class Integer >
auto floor_div( Integer const a, Integer const b )
-> Integer
{
bool const a_is_negative = (a < 0);
bool const b_is_negative = (b < 0);
bool const change_sign = (a_is_negative != b_is_negative);
Integer const abs_b = abs( b );
Integer const abs_a_plus = abs( a ) + (change_sign? abs_b - 1 : 0);
Integer const quot = abs_a_plus / abs_b;
return (change_sign? -quot : quot);
}
template< class Integer >
auto floor_mod( Integer const a, Integer const b )
-> Integer
{ return a - b*floor_div( a, b ); }
& hellip; с тем же ограничением на Integer, что это подписанный тип.
¹ Поскольку целочисленное деление Python округляется до отрицательной бесконечности.
Простейшей общей функцией для поиска положительного по модулю было бы это - Он будет работать как с положительными, так и с отрицательными значениями х.
int modulo(int x,int N){
return (x % N + N) %N;
}
О, я ненавижу% design для этого тоже....
Вы можете конвертировать дивиденд в unsigned так:
unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider
result = (offset + dividend) % divider
где смещение ближе всего к (-INT_MIN), кратное модулю, поэтому добавление и вычитание не изменятся по модулю. Обратите внимание, что он имеет неподписанный тип, и результат будет целым. К сожалению, он не может правильно преобразовать значения INT_MIN... (- offset-1), поскольку они вызывают арифметическое переполнение. Но этот метод имеет преимущество только одной дополнительной арифметики за операцию (и никаких условностей) при работе с постоянным делителем, поэтому ее можно использовать в DSP-подобных приложениях.
В частном случае, когда делитель равен 2 N (целая мощность двух), для которых по модулю можно вычислить с использованием простой арифметической и поразрядной логики в качестве
dividend&(divider-1)
например
x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15
Более распространенным и менее сложным способом является использование этой функции по модулю (работает только с положительным делителем):
int mod(int x, int y) {
int r = x%y;
return r<0?r+y:r;
}
Это правильный результат, если он отрицательный.
Также вы можете обмануть:
(p% q + q)% q
Он очень короткий, но используйте два% -ых, которые обычно медленны.
Я считаю, что другим решением этой проблемы будет использование переменных типа long вместо int.
Я просто работал над некоторым кодом, в котором оператор% возвращал отрицательное значение, что вызвало некоторые проблемы (для генерации однородных случайных величин на [0,1] вам действительно не нужны отрицательные числа:)), но после переключения переменные, чтобы напечатать long, все работало гладко, и результаты соответствовали тем, которые я получал при запуске одного и того же кода в python (важно для меня, поскольку я хотел иметь возможность генерировать одни и те же "случайные" числа на нескольких платформах.
/* Warning: macro mod evaluates its arguments' side effects multiple times. */ #define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)
... или просто привыкнуть к получению любого представителя для класса эквивалентности.
Вот новый ответ на старый вопрос, основанный на этом Microsoft Research paper и ссылки на него.
Обратите внимание, что из C11 и С++ 11 семантика div стала усечением в сторону нуля (см. [expr.mul]/4). Кроме того, для D, деленного на D, С++ 11 гарантирует следующее о quotient qT и остатке rT
auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));
где signum отображается в -1, 0, +1, в зависимости от того, является ли его аргумент <, ==, > чем 0 (см. этот Q & A для исходного кода).
С усеченным делением знак остатка равен знаку дивиденда D, т.е. -1 % 8 == -1. С++ 11 также предоставляет функцию std::div, которая возвращает структуру с членами quot и rem в соответствии с усеченным делением.
Возможны другие определения, например. так называемое разделение на пол может быть определено в терминах встроенного усеченного деления
auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));
При делении на пол, знак остатка равен знаку делителя D. На таких языках, как Haskell и Oberon, есть встроенные операторы для разделения полов. В С++ вам нужно написать функцию, используя приведенные выше определения.
Другим способом является евклидово деление, которое также может быть определено в терминах встроенного усеченного деления
auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);
С евклидовым делением знак остатка всегда положителен.
Пример шаблона для С++
template< class T >
T mod( T a, T b )
{
T const r = a%b;
return ((r!=0)&&((r^b)<0) ? r + b : r);
}
С помощью этого шаблона возвращаемый остаток будет равен нулю или будет иметь тот же знак, что и делитель (знаменатель) (эквивалент округления к отрицательной бесконечности), вместо того, чтобы поведение С++ остатка равнялось нулю или имело тот же знак, что и дивиденд (числитель) (эквивалент округления к нулю).
Просто (х + мод)% мод
define MOD(a, b) ((((a)%(b))+(b))%(b))
unsigned mod(int a, unsigned b) {
return (a >= 0 ? a % b : b - (-a) % b);
}
Это решение (для использования при mod положительно) позволяет избежать всех операций с отрицательным делением или остатком:
int core_modulus(int val, int mod)
{
if(val>=0)
return val % mod;
else
return val + mod * ((mod - val - 1)/mod);
}
Я бы сделал:
((-1)+8) % 8
Это добавляет последнее число к первому, прежде чем делать по модулю предложение 7 по желанию. Это должно работать для любого числа до -8. Для -9 добавить 2 * 8.