Мод отрицательного числа тает мой мозг

189

Я пытаюсь изменить целое число, чтобы получить позицию массива, чтобы он зациклился. Выполнение i % arrayLengthработает хорошо для положительных чисел, но для отрицательных чисел все идет не так, как надо.

 4 % 3 == 1
 3 % 3 == 0
 2 % 3 == 2
 1 % 3 == 1
 0 % 3 == 0
-1 % 3 == -1
-2 % 3 == -2
-3 % 3 == 0
-4 % 3 == -1

так что мне нужна реализация

int GetArrayIndex(int i, int arrayLength)

такой, что

GetArrayIndex( 4, 3) == 1
GetArrayIndex( 3, 3) == 0
GetArrayIndex( 2, 3) == 2
GetArrayIndex( 1, 3) == 1
GetArrayIndex( 0, 3) == 0
GetArrayIndex(-1, 3) == 2
GetArrayIndex(-2, 3) == 1
GetArrayIndex(-3, 3) == 0
GetArrayIndex(-4, 3) == 2

Я делал это раньше, но почему-то сегодня мой мозг тает :(

Полковник паника
источник
См. Обсуждение математического модуля на math.stackexchange.com/questions/519845/…
PPC
blogs.msdn.microsoft.com/ericlippert/2011/12/05/… отличная статья
Самра

Ответы:

281

Я всегда использую свою собственную modфункцию, определенную как

int mod(int x, int m) {
    return (x%m + m)%m;
}

Конечно, если вам надоело иметь два вызова операции модуля, вы можете написать это как

int mod(int x, int m) {
    int r = x%m;
    return r<0 ? r+m : r;
}

или их варианты.

Причина, по которой это работает, заключается в том, что «x% m» всегда находится в диапазоне [-m + 1, m-1]. Поэтому, если он вообще отрицательный, добавление m к нему приведет к положительному диапазону, не меняя его значения по модулю m.

ShreevatsaR
источник
7
Примечание: для полной теоретико-числовой полноты вы можете добавить строку вверху с надписью "if (m <0) m = -m;" хотя в этом случае это не имеет значения, так как «arrayLength», по-видимому, всегда положителен.
ShreevatsaR
4
Если вы собираетесь проверить значение m, вы также должны исключить ноль.
billpg
6
@RuudLenders: Нет. Если x = -5 и m = 2, то r = x%mесть -1, после которого r+mесть 1. Цикл while не нужен. Дело в том, что (как я написал в ответе) x%mвсегда строго больше -m, поэтому вам нужно добавить mне более одного раза, чтобы сделать его положительным.
ShreevatsaR
4
@dcastro: Я действительно хочу -12 -10 мод , чтобы быть 8. Это наиболее общее соглашение в математике, что если выбирать представителя rпо aмодулю b, то такое , что 0 ≤ г <| B |.
ShreevatsaR
8
+1. Мне все равно, что любой отдельный язык делает для отрицательного модуля - «наименьший неотрицательный остаток» демонстрирует математическую закономерность и устраняет любую двусмысленность.
Бретт Хейл,
80

Обратите внимание, что оператор% C # и C ++ на самом деле НЕ является модулем, это остаток. Формула для модуля по вашему желанию в вашем случае:

float nfmod(float a,float b)
{
    return a - b * floor(a / b);
}

Вы должны перекодировать это в C # (или C ++), но это способ, которым вы получаете по модулю, а не остаток.

Петър Петров
источник
21
«Обратите внимание, что оператор% C ++ на самом деле НЕ по модулю, это остаток.» Спасибо, теперь это имеет смысл, всегда удивляюсь, почему он никогда не работал должным образом с отрицательными числами.
leetNightshade
2
«Обратите внимание, что оператор% C ++ на самом деле НЕ является модулем, это остаток.» Я не думаю, что это точно, и я не понимаю, почему модуль отличается от остатка. Это то, что также сказано на странице Википедии «Операция по модулю». Просто языки программирования по-разному относятся к отрицательным числам. Оператор по модулю в C #, очевидно, считает остатки «от» нуля (-9% 4 = -1, потому что 4 * -2 равен -8 с разницей -1), тогда как другое определение будет считать -9% 4 как +3, потому что -4 * 3 - это -12, остаток +3 (например, в функции поиска Google, не уверен, что там есть язык бэкэнда).
Tyress
18
Tyress, есть разница между модулем и остатком. Например: -21 mod 4 is 3 because -21 + 4 x 6 is 3. но -21 divided by 4 gives -5с собой remainder of -1. Для положительных значений разницы нет. Поэтому, пожалуйста, ознакомьтесь с этими различиями. И не доверяй Википедии все время :)
Петър Петров
2
Почему кто-то хотел бы использовать функцию остатка вместо модуля? Почему они сделали %остаток?
Аарон Франке
4
@AaronFranke - это наследие более ранних процессоров, у которых было оборудование для деления, чтобы быстро производить частное и остаток - и это то, что это оборудование делало с отрицательным дивидендом. Язык просто отражает оборудование. Большую часть времени программисты работали с положительными дивидендами и игнорировали эту причуду. Скорость была первостепенной.
ToolmakerSteve
16

Однострочная реализация, использующая %только один раз:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
Евгений Сергеев
источник
1
это верно? так как я не вижу, что это принято кем-то, ни каких-либо комментариев к нему. Например. mod (-10,6) вернет 6. Это правильно? не должно ли вернуться 4?
Джон Деметриу
3
@JohnDemetriou Ваши числа неверны: (A) он должен вернуть 2 и (B) он возвращает 2; попробуйте запустить код. Пункт (A): чтобы найти mod(-10, 6)вручную, вы либо добавляете, либо вычитаете 6 раз, пока ответ не окажется в диапазоне [0, 6). Это обозначение означает «включительно слева и исключительно справа». В нашем случае мы добавляем 6 дважды, давая 2. Код довольно прост, и легко видеть, что он прав: во-первых, он эквивалентен сложению / вычитанию, nкак указано выше, за исключением того, что он останавливается на одно nкороткое, если приближается отрицательная сторона. В таком случае мы это исправим. Там: комментарии :)
Евгений Сергеев
1
Кстати, вот причина, почему использование одного %может быть хорошей идеей. См. Таблицу « Что стоит в управляемом коде» в статье « Написание более быстрого управляемого кода: знайте, что стоит» . Использование так %же дорого, как int divуказано в таблице: примерно в 36 раз дороже, чем сложение или вычитание, и примерно в 13 раз дороже, чем умножение. Конечно, ничего страшного, если только это не лежит в основе того, что делает ваш код.
Евгений Сергеев
2
Но %дороже ли тест, чем тест и прыжок, особенно если его трудно предсказать?
Medinoc
6

Ответ ShreevatsaR не будет работать во всех случаях, даже если вы добавите «if (m <0) m = -m;», если вы учтете отрицательные дивиденды / делители.

Например, -12 мод -10 будет 8, и это должно быть -2.

Следующая реализация будет работать как для положительных, так и для отрицательных дивидендов / делителей и соответствует другим реализациям (а именно, Java, Python, Ruby, Scala, Scheme, Javascript и Google's Calculator):

internal static class IntExtensions
{
    internal static int Mod(this int a, int n)
    {
        if (n == 0)
            throw new ArgumentOutOfRangeException("n", "(a mod 0) is undefined.");

        //puts a in the [-n+1, n-1] range using the remainder operator
        int remainder = a%n;

        //if the remainder is less than zero, add n to put it in the [0, n-1] range if n is positive
        //if the remainder is greater than zero, add n to put it in the [n-1, 0] range if n is negative
        if ((n > 0 && remainder < 0) ||
            (n < 0 && remainder > 0))
            return remainder + n;
        return remainder;
    }
}

Тестовый набор с использованием xUnit:

    [Theory]
    [PropertyData("GetTestData")]
    public void Mod_ReturnsCorrectModulo(int dividend, int divisor, int expectedMod)
    {
        Assert.Equal(expectedMod, dividend.Mod(divisor));
    }

    [Fact]
    public void Mod_ThrowsException_IfDivisorIsZero()
    {
        Assert.Throws<ArgumentOutOfRangeException>(() => 1.Mod(0));
    }

    public static IEnumerable<object[]> GetTestData
    {
        get
        {
            yield return new object[] {1, 1, 0};
            yield return new object[] {0, 1, 0};
            yield return new object[] {2, 10, 2};
            yield return new object[] {12, 10, 2};
            yield return new object[] {22, 10, 2};
            yield return new object[] {-2, 10, 8};
            yield return new object[] {-12, 10, 8};
            yield return new object[] {-22, 10, 8};
            yield return new object[] { 2, -10, -8 };
            yield return new object[] { 12, -10, -8 };
            yield return new object[] { 22, -10, -8 };
            yield return new object[] { -2, -10, -2 };
            yield return new object[] { -12, -10, -2 };
            yield return new object[] { -22, -10, -2 };
        }
    }
dcastro
источник
Во-первых, modфункция обычно вызывается с положительным модулем (обратите внимание на переменную arrayLengthв исходном вопросе, на который здесь дан ответ, который, по-видимому, никогда не бывает отрицательным), поэтому на самом деле функцию не нужно заставлять работать для отрицательного модуля. (Вот почему я упоминаю трактовку отрицательного модуля в комментарии к моему ответу, а не в самом ответе.) (Продолжение ...)
ShreevatsaR
3
(... продолжение) Во-вторых, что делать для отрицательного модуля является вопросом соглашения. Смотрите, например, Википедию . «Обычно в теории чисел всегда выбирается положительный остаток», и так я его и выучил (в теории элементарных чисел Бертона ). Кнут также определяет это таким образом (в частности, r = a - b floor(a/b)всегда положительно). Даже среди компьютерных систем, например, Паскаль и Мэйпл, это всегда положительно.
ShreevatsaR
@ShreevatsaR Я знаю, что в евклидовом определении говорится, что результат всегда будет положительным, но у меня сложилось впечатление, что большинство современных реализаций модов будет возвращать значение в диапазоне [n + 1, 0] для отрицательного делителя «n», что означает, что -12 мод -10 = -2. Я изучил Google Calculator , Python , Ruby и Scala , и все они следуют этому соглашению.
dcastro
Также добавить в список: Схемы и Javascript
dcastro
1
Опять же, это все еще хорошее чтение. «Всегда положительное» определение (мой ответ) соответствует ALGOL, Dart, Maple, Pascal, Z3 и т. Д. «Знак делителя» (этот ответ) соответствует: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl и т. Д. Оба несовместимы с «признаком дивиденда», как в: AWK, bash, bc, C99, C ++ 11, C #, D, Eiffel, Erlang, Go, Java , OCaml, PHP, Rust, Scala, Swift, VB, сборка x86 и т. Д. Я действительно не понимаю, как можно утверждать, что одно соглашение является «правильным», а другие «неправильным».
ShreevatsaR
6

Добавление некоторого понимания.

По евклидову определению мод мод всегда должен быть положительным.

Пример:

 int n = 5;
 int x = -3;

 int mod(int n, int x)
 {
     return ((n%x)+x)%x;
 }

Вывод:

 -1
Корзина
источник
15
Я в замешательстве ... вы говорите, что результат всегда должен быть положительным, но затем перечислить вывод как -1?
Джефф Б
@JeffBridgman Я уже говорил об этом, основываясь на евклидовом определении. `есть два возможных варианта для остатка, один отрицательный, а другой положительный, и также есть два возможных варианта для частного. Обычно, в теории чисел, the positive remainder is always chosenно языки программирования выбирают в зависимости от языка и знаков a и / или n. [5] Стандартные Pascal и Algol68 дают положительный остаток (или 0) даже для отрицательных делителей, а некоторые языки программирования, такие как C90, оставляют его на усмотрение, когда любой из n или a отрицателен.
Abin
5

Сравнивая два преобладающих ответа

(x%m + m)%m;

и

int r = x%m;
return r<0 ? r+m : r;

На самом деле никто не упомянул тот факт, что первый может бросить, OverflowExceptionа второй нет. Хуже того, при непроверенном контексте по умолчанию первый ответ может вернуть неправильный ответ (см., mod(int.MaxValue - 1, int.MaxValue)Например). Таким образом, второй ответ не только кажется более быстрым, но и более правильным.

lilo0
источник
4

Просто добавьте свой модуль (arrayLength) к отрицательному результату%, и все будет в порядке.

starblue
источник
4

Для более эффективной работы разработчиков

uint wrap(int k, int n) ((uint)k)%n

Небольшое сравнение производительности

Modulo: 00:00:07.2661827 ((n%x)+x)%x)
Cast:   00:00:03.2202334 ((uint)k)%n
If:     00:00:13.5378989 ((k %= n) < 0) ? k+n : k

Что касается производительности стоимость приведения к Uint, посмотрите здесь

Маркус Козович
источник
3
Метинкс, который -3 % 10должен быть либо -3, либо 7. Так как нужен неотрицательный результат, 7 будет ответом. Ваша реализация вернет 3. Вы должны изменить оба параметра uintи удалить приведение.
Мне понравилось старое переполнение стека
5
Арифметика без знака эквивалентна только в том случае, если она nявляется степенью двойки, и в этом случае вы можете просто использовать логические и ( (uint)k & (n - 1)) вместо этого, если компилятор еще не сделал этого за вас (компиляторы часто достаточно умны, чтобы понять это).
j_schultz
2

Мне нравится трюк, представленный Питером Н. Льюисом в этой теме : «Если n имеет ограниченный диапазон, то вы можете получить желаемый результат, просто добавив известную постоянную, кратную [делителю], которая больше абсолютного значения минимум «.

Так что, если у меня есть значение d в градусах, и я хочу взять

d % 180f

и я хочу избежать проблем, если d отрицательно, то вместо этого я просто делаю это:

(d + 720f) % 180f

Это предполагает, что хотя d может быть отрицательным, известно, что оно никогда не будет более отрицательным, чем -720.

RenniePet
источник
2
-1: недостаточно общее (и очень легко дать более общее решение).
Евгений Сергеев
4
Это на самом деле очень полезно. когда у вас есть значимый диапазон, это может упростить вычисления. в моем случае math.stackexchange.com/questions/2279751/…
М.Казем Ахгари
Точно, просто использовал это для вычисления dayOfWeek (известный диапазон от -6 до +6), и он сохранил, имея два %.
NetMage
@EvgeniSergeev +0 для меня: не отвечает на вопрос ОП, но может быть полезным в более конкретном контексте (но все же в контексте вопроса)
Эрдал Г.
1

Вы ожидаете поведения, которое противоречит документированному поведению оператора% в c # - возможно, потому, что вы ожидаете, что оно будет работать так, как оно работает на другом языке, к которому вы более привыкли. Документация на C # государств (курсив мой):

Для операндов целочисленных типов результатом a% b является значение, создаваемое a - (a / b) * b. Знак ненулевого остатка такой же, как и у левого операнда

Требуемое значение можно рассчитать с помощью одного дополнительного шага:

int GetArrayIndex(int i, int arrayLength){
    int mod = i % arrayLength;
    return (mod>=0) : mod ? mod + arrayLength;
}
Андрей
источник
1

Однострочная реализация ответа dcastro (наиболее совместимого с другими языками):

int Mod(int a, int n)
{
    return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
}

Если вы хотите сохранить использование %оператора (вы не можете перегружать нативные операторы в C #):

public class IntM
{
    private int _value;

    private IntM(int value)
    {
        _value = value;
    }

    private static int Mod(int a, int n)
    {
        return (((a %= n) < 0) && n > 0) || (a > 0 && n < 0) ? a + n : a;
    }

    public static implicit operator int(IntM i) => i._value;
    public static implicit operator IntM(int i) => new IntM(i);
    public static int operator %(IntM a, int n) => Mod(a, n);
    public static int operator %(int a, IntM n) => Mod(a, n);
}

Вариант использования, оба работает:

int r = (IntM)a % n;

// Or
int r = a % n(IntM);
Эрдал Г.
источник
0

Все ответы здесь отлично работают, если ваш делитель положительный, но не совсем полный. Вот моя реализация, которая всегда возвращает диапазон[0, b) , такой, что знак выхода совпадает со знаком делителя, что позволяет использовать отрицательные делители в качестве конечной точки для выходного диапазона.

PosMod(5, 3)возвращает 2
PosMod(-5, 3)возвращает 1
PosMod(5, -3)возвращает -1
PosMod(-5, -3)возвращает-2

    /// <summary>
    /// Performs a canonical Modulus operation, where the output is on the range [0, b).
    /// </summary>
    public static real_t PosMod(real_t a, real_t b)
    {
        real_t c = a % b;
        if ((c < 0 && b > 0) || (c > 0 && b < 0)) 
        {
            c += b;
        }
        return c;
    }

(где real_tможет быть любой тип номера)

Аарон Франке
источник