Вопрос по c#, math, modulo – Мод отрицательного числа тает мой мозг

160

Я пытаюсь изменить целое число, чтобы получить позицию массива, чтобы он зацикливался. дела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

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

Смотрите обсуждение оmathematical модуль наmath.stackexchange.com/questions/519845/… PPC
blogs.msdn.microsoft.com/ericlippert/2011/12/05/… это отличная статья Samra

Ваш Ответ

10   ответов
13

Однострочная реализация с использованием% только однажды:

int mod(int k, int n) {  return ((k %= n) < 0) ? k+n : k;  }
это правильно? так как я не вижу, что это принято кем-то, ни каких-либо комментариев к нему. Например. mod (-10,6) вернет 6. Это правильно? не должно ли вернуться 4?
Кстати, вот причина, почему использование одного% может быть хорошей идеей Смотри таблицуWhat things cost in managed code в статьеWriting Faster Managed Code: Know What Things Cost, С помощью% так же дорогоint div приведены в таблице: примерно в 36 раз дороже, чем сложение или вычитание, и примерно в 13 раз дороже, чем умножение. Конечно, ничего страшного, если только это не лежит в основе того, что делает ваш код.
Но это один% более дорогой, чем тестирование и прыжок, особенно если это трудно предсказать?
@JohnDemetriou Ваши числа неверны: (A) он должен вернуть 2 и (B) он возвращает 2; попробуйте запустить код. Предмет (A): найтиmod(-10, 6) вручную, вы либо добавляете, либо вычитаете 6 раз, пока ответ не окажется в диапазоне[0, 6), Это обозначение означает «включительно слева и эксклюзивно справа». В нашем случае мы добавляем 6 дважды, что дает 2. Код довольно прост, и легко видеть, что он прав: во-первых, он эквивалентен сложению / вычитаниюn как указано выше, за исключением того, что он останавливает одинn Короче, если подходить с отрицательной стороны. В таком случае мы это исправим. Там: комментарии :)
5

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

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 посмотретьВот

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

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

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

d % 180f

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

(d + 720f) % 180f

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

Это на самом деле очень полезно. когда у вас есть значимый диапазон, это может упростить вычисления. в моем случаеmath.stackexchange.com/questions/2279751/…
-1: недостаточно общее (и очень легко дать более общее решение).
5

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

ОтЕвклидово определение Результат мода должен быть всегда положительным.

Пример:

 int n = 5;
 int x = -3;

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

Выход:

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

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

(x%m + m)%m;

а также

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

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

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 может быть любого типа номера)

245

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

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

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

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

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

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

@billpg: мод не определен для m = 0, так что на самом деле ничего такого, что функция может ожидать в этом случае, не ожидается. IMHO, это обязанность вызывающего абонента проверить это. (Никто не должен дажеwant что-то мод 0.) OTOH, модis определено для отрицательного m, поэтому я предложил исправить эту ошибку в коде, если функция может быть вызвана с отрицательным m. В любом случае, где проверка ошибок / обработка должна быть сделана, это постоянный вопрос: p
@RuudLenders: Нет. Если x = -5 и m = 2, тоr = x%m является-1, после которогоr+m является1, Цикл while не нужен. Дело в том, что (как я написал в ответе)x%m всегда строго больше, чем-mтак что вам нужно добавитьm максимум один раз, чтобы сделать это положительным.
Примечание: для полной теоретико-числовой полноты вы можете добавить строку вверху, в которой говорится "if (m & lt; 0) m = -m;" хотя в этом случае это не имеет значения как «arrayLength» предположительно всегда положительный.
+1. Меня не волнует, что любой отдельный язык делает для отрицательного модуля - «наименьшего неотрицательного остатка»; проявляет математическую закономерность и устраняет любую неопределенность.
Если вы собираетесь проверить значение m, вы также должны исключить ноль.
66

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

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

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

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

Ответ ShreevatsaR не будет работать для всех случаев, даже если вы добавите «if (m & lt; 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 };
        }
    }
(... продолжение) Во-вторых, что делать для отрицательного модуля является вопросом соглашения. Увидетьe.g. Wikipedia, «Обычно в теории чисел всегда выбирается положительный остаток», и так я его и выучил (в Burton'sElementary Number Theory). Кнут также определяет это таким образом (в частности,r = a - b floor(a/b) всегда позитивно). Даже среди компьютерных систем, например, Паскаль и Мэйпл, это всегда положительно.
@ShreevatsaR Я знаю, что в евклидовом определении говорится, что результат всегда будет положительным, но у меня сложилось впечатление, что большинство современных реализаций модов будет возвращать значение в диапазоне [n + 1, 0] для отрицательного делителя & quot; n & quot; , что означает, что -12 мод -10 = -2. Я смотрел вGoogle Calculator, Python, Ruby а такжеScalaи все они следуют этому соглашению.
Также добавить в список:Scheme а такжеJavascript
Во-первых,mod функция обычно вызывается с положительным модулем (обратите внимание на переменнуюarrayLength в исходном вопросе, на который здесь дан ответ (который, по-видимому, никогда не является отрицательным), так что функция действительно не должна работать для отрицательного модуля. (Вот почему я упоминаю обработку отрицательного модуля в комментарии к моему ответу, а не в самом ответе.) (Продолжение ...)
Снова,this все еще хорошее чтение. & Quot; Всегда положительный & quot; определение (мой ответ) согласуется с ALGOL, Dart, Maple, Pascal, Z3 и т. д. «Знак делителя» (этот ответ) соответствует: APL, COBOL, J, Lua, Mathematica, MS Excel, Perl, Python, R, Ruby, Tcl и т. д.Both несовместимы с «признаком дивидендов»; как в: AWK, bash, bc, C99, C ++ 11, C #, D, Eiffel, Erlang, Go, Java, OCaml, PHP, Rust, Scala, Swift, VB, сборка x86 и т. д. Я действительно не понимаю узнайте, как можно утверждать, что одно соглашение является "правильным" и другие "неправильно".
4

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

Похожие вопросы