Разделить и получить остаток одновременно?

Очевидно, x86 (и, вероятно, множество других наборов инструкций) помещает как частное, так и остаток от операции деления в отдельные регистры.

Теперь мы, вероятно, можем доверять компиляторам оптимизацию такого кода, чтобы использовать только один вызов для разделения:

( x / 6 )
( x % 6 )

И они, вероятно, так и поступают. Тем не менее, поддерживают ли какие-либо языки (или библиотеки, но в основном ищущие языки) выдачу результатов как разделения, так и по модулю одновременно? Если да, то каковы они и как выглядит синтаксис?


person Ben    schedule 09.10.2010    source источник
comment
Ваш фрагмент кода не является примером чего-то, что можно было бы оптимизировать таким образом ...   -  person Oliver Charlesworth    schedule 09.10.2010
comment
Я только что понял, что у меня неправильный фрагмент кода. Обновил.   -  person Ben    schedule 09.10.2010
comment
Отличные отзывы от всех. Отстой, что я могу выбрать только один в качестве ответа, когда многие из них являются действительными.   -  person Ben    schedule 12.10.2010


Ответы (9)


В C есть div и ldiv. Создают ли они отдельные инструкции для частного и остатка, будет зависеть от конкретной реализации стандартной библиотеки и настроек компилятора и оптимизации. Начиная с C99, у вас также есть lldiv для больших чисел.

person bta    schedule 09.10.2010
comment
Удивительно, почему этот ответ не принят - он в точности соответствует тому, что было задано. - person toriningen; 18.02.2013
comment
Интересно отметить, что один только модуль modulo не реализован с div в 4.8: stackoverflow.com/questions/4361979/ - person Ciro Santilli 新疆再教育营六四事件ۍ 20.10.2015
comment
Пошел вперед и принял этот ответ. Я знаю, что здесь все еще есть много правильных ответов, поэтому трудно сказать, что один из них «более правильный», чем другие, но C - хорошая отправная точка для разговора об этих вещах. - person Ben; 02.12.2015
comment
Не используйте это с текущими компиляторами, особенно для деления на константу: это не оптимизирует. См. godbolt.org/g/ydL27q: div(var, 10) компилируется в фактический вызов функции и div реализацию библиотеки не имеет информации о том, что делитель является константой 10. Поэтому он не может использовать мультипликативный обратный. Даже с делителем переменной времени выполнения вы получаете больший размер кода и вызов функции не в строке на x86. - person Peter Cordes; 25.08.2017
comment
Если бы эти функции были необходимы или часто использовались, компиляторы имели бы встроенные версии их (как они делают для memcpy), но это не так, поэтому они не оптимизируются почти так хорошо, как могли бы. Таким образом, гораздо лучше просто использовать n / d и n % d рядом с точно такими же n и d, чтобы компилятор мог надежно оптимизировать деление на постоянную информацию, постоянное распространение и информацию о диапазоне. (например, компилятор знает, что результат деления на 10 имеет меньший диапазон, чем полный диапазон int, что, возможно, позволит оптимизировать его позже.) - person Peter Cordes; 25.08.2017
comment
В любом случае, это хороший ответ на этот вопрос, но важно отметить, что на самом деле вам не следует использовать эту часть языка, если вы сначала не реализуете быструю поддержку для нее в используемом компиляторе. Для 64-битного деления на 32-битной машине или в других случаях, когда нельзя просто встроить что-то крошечное, gcc уже вызывает внутреннюю функцию libgcc.a, поэтому вы, вероятно, никогда даже не сохраните размер кода с помощью этих функций. - person Peter Cordes; 25.08.2017
comment
@PeterCordes Будьте осторожны, чтобы не делать чрезмерных обобщений. Будет ли что-то оптимизировано или нет, зависит от реализации вашего конкретного компилятора и / или стандартной библиотеки. Я видел реализации с оптимизированным div и другие без него. Всегда проверяйте вашу конкретную реализацию, прежде чем предполагать, что что-то оптимизировано или не оптимизировано. - person bta; 24.10.2017
comment
@bta: Справедливо, я имел в виду текущие компиляторы x86 (и предоставил ссылку Godbolt для тестирования gcc / clang / ICC / MSVC). Существуют ли какие-либо реализации, в которых вы получаете лучший код от вызова div, чем от написания r = x%y; q = x/y;? Это обычное явление, поэтому большинство хороших компиляторов оптимизируют его, если анализ псевдонимов не останавливает работу CSE (например, x и y не являются простыми локальными переменными). Если вызов div - лучший способ на этой платформе, то это могут делать компиляторы для % и / с открытым кодом. Конечно, это хорошо для тестирования, но я предполагаю, что открытое кодирование является более безопасной ставкой для большего количества реализаций. - person Peter Cordes; 24.10.2017
comment
Я определенно видел вызов функции div(), оптимизированный для получения обоих результатов из одной инструкции DIV, где отдельные инструкции / и % эффективно выполняют все вычисления дважды (я не помню, какой компилятор, хотя это была встроенная платформа). Если x равно volatile, ваши результаты могут измениться по совершенно другим причинам. Опять же, всегда проверяйте поведение, зависящее от реализации, с вашим конкретным вариантом использования, прежде чем оптимизировать для него / вокруг него. - person bta; 25.10.2017

Python делает.

>>> divmod(9, 4)
(2, 1)

Что странно, потому что Python - язык высокого уровня.

Как и Руби:

11.divmod(3) #=> [3, 2]

* ИЗМЕНИТЬ *

Следует отметить, что цель этих операторов, вероятно, не в том, чтобы выполнять работу максимально эффективно, скорее всего, функции существуют по причинам корректности / переносимости.

Для тех, кто заинтересован, я считаю, что это код Python реализация для целочисленного divmod:

static enum divmod_result
i_divmod(register long x, register long y,
     long *p_xdivy, long *p_xmody)
{
long xdivy, xmody;

if (y == 0) {
    PyErr_SetString(PyExc_ZeroDivisionError,
                    "integer division or modulo by zero");
    return DIVMOD_ERROR;
}
/* (-sys.maxint-1)/-1 is the only overflow case. */
if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
    return DIVMOD_OVERFLOW;
xdivy = x / y;
/* xdiv*y can overflow on platforms where x/y gives floor(x/y)
 * for x and y with differing signs. (This is unusual
 * behaviour, and C99 prohibits it, but it's allowed by C89;
 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
 * LONG_MAX, y = -5.)  However, x - xdivy*y is always
 * representable as a long, since it lies strictly between
 * -abs(y) and abs(y).  We add casts to avoid intermediate
 * overflow.
 */
xmody = (long)(x - (unsigned long)xdivy * y);
/* If the signs of x and y differ, and the remainder is non-0,
 * C89 doesn't define whether xdivy is now the floor or the
 * ceiling of the infinitely precise quotient.  We want the floor,
 * and we have it iff the remainder's sign matches y's.
 */
if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
    xmody += y;
    --xdivy;
    assert(xmody && ((y ^ xmody) >= 0));
}
*p_xdivy = xdivy;
*p_xmody = xmody;
return DIVMOD_OK;
}
person Eloff    schedule 09.10.2010
comment
divmod выполняет только одну операцию? Какой код стоит за этой функцией? - person BrunoLM; 09.10.2010
comment
Обыграй меня. divmod () - встроенная функция Python. - person Russell Borogove; 09.10.2010
comment
@BrunoLM Я готов поспорить, что большое количество [вставьте любимый напиток] divmod просто выполняет обе операции отдельно и упаковывает результаты, но не могу предложить никаких доказательств. - person Andrew Barber; 09.10.2010
comment
@BrunoLM: виртуальная машина вызывает встроенную функцию, которая, я надеюсь, выполняет встроенную инструкцию div. - person Russell Borogove; 09.10.2010
comment
@ Рассел: хе-хе; на самом деле я неправильно сформулировал свою потенциальную ставку! Я имел в виду, что я не думаю, что он пытается использовать какие-либо низкоуровневые «уловки», чтобы сделать операцию эффективной, но вместо этого это просто способ сэкономить несколько нажатий клавиш для разработчика. :-П - person Andrew Barber; 09.10.2010
comment
Разве целочисленное деление со знаком Python не всегда дает положительный модуль? В отличие от C и x86 asm div, где остаток может быть отрицательным остатком. Поэтому он определенно не может просто использовать x86 div, даже если целое число Python является единичным фрагментом (а не bignum). Вот почему реализация C использует /, но не %. - person Peter Cordes; 22.11.2020

В C # /. NET у вас есть Math.DivRem: http://msdn.microsoft.com/en-us/library/system.math.divrem.aspx

Но, согласно этой ветке, это не такая уж большая оптимизация.

person Stringer    schedule 09.10.2010

В Java (начиная с версии 1.5) класс BigDecimal выполняет операцию divideAndRemainder, возвращающую массив из 2 элементов с результатом и остатком от деления.

BigDecimal bDecimal = ...
BigDecimal[] result = bDecimal.divideAndRemainder(new BigDecimal(60));

Документация Javadoc: https://docs.oracle.com/javase/8/docs/api/java/math/BigDecimal.html#divideAndRemainder-java.math.BigDecimal-

person Iván    schedule 25.08.2017

Common Lisp делает: http://www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm

person Pedro Rodrigues    schedule 09.10.2010

В платформе .NET есть Math.DivRem:

int mod, div = Math.DivRem(11, 3, out mod);
// mod = 2, div = 3

Хотя DivRem - это просто оболочка примерно такого:

int div = x / y;
int mod = x % y;

(Я понятия не имею, может ли джиттер оптимизировать такие вещи в одну инструкцию.)

person LukeH    schedule 09.10.2010

Как упомянул Стрингер Белл, существует DivRem, который не оптимизирован до .NET 3.5. .

В .NET 4.0 используется NGen.

Результаты, которые я получил с Math.DivRem (отладка; выпуск = ~ 11000 мс)

11863
11820
11881
11859
11854

Результаты, которые я получил с MyDivRem (отладка; выпуск = ~ 11000 мс)

29177
29214
29472
29277
29196

Проект ориентирован на x86.


Math.DivRem Пример использования

int mod1;
int div1 = Math.DivRem(4, 2, out mod1);

Сигнатуры методов

DivRem(Int32, Int32, Int32&) : Int32
DivRem(Int64, Int64, Int64&) : Int64

Код .NET 4.0

[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a / b);
}

.NET 4.0 IL

.custom instance void System.Runtime.TargetedPatchingOptOutAttribute::.ctor(string) = { string('Performance critical to inline across NGen image boundaries') }
.maxstack 8
L_0000: ldarg.2 
L_0001: ldarg.0 
L_0002: ldarg.1 
L_0003: rem 
L_0004: stind.i4 
L_0005: ldarg.0 
L_0006: ldarg.1 
L_0007: div 
L_0008: ret 

Справочник MSDN

person BrunoLM    schedule 09.10.2010
comment
Этот ответ немного вводит в заблуждение, поскольку время, которое вы бросаете, кажется, показывает, что Math.DivRem оптимизирован в .Net 4.0, но, как вы немного заметили в стороне, на самом деле он вообще не оптимизирован. Фактически, в моих тестах Math.DivRem () немного МЕДЛЕНнее, чем простой div и mod ops во всех версиях .Net. Другими словами, он совсем не оптимизирован. - person Chris Moschini; 28.07.2014
comment
Это потому, что это тестовый режим отладки, поэтому все в вашем собственном коде будет ужасным по сравнению с вызовом уже скомпилированной библиотечной функции. В нем упоминается, что время выпуска примерно одинаково, и это важно. (Но я думаю, что оптимизация в этом случае означает не хуже, чем позволить компилятору CSE x/y и x%y в версия с открытым кодом, а в .NET3.5 могло быть и хуже?) - person Peter Cordes; 22.11.2020

FWIW, в Haskell есть как divMod и quotRem последний из которых соответствует непосредственно машинной инструкции (согласно интегральным операторам quot против div), а divMod может нет.

person Jon Wolski    schedule 11.01.2016

person    schedule
comment
Компилятор уже может сделать эту оптимизацию. Использование неуклюжего плохого встроенного asm MSVC таким образом просто заставляет несколько циклов сохранения / перезагрузки. Кроме того, вы выполняете беззнаковое деление, поэтому переменные должны быть unsigned, а не int. Кроме того, никогда не используйте div для известной степени двойки, например 4. Используйте _4 _ / _ 5_, чтобы получить частное и остаток. - person Peter Cordes; 22.11.2020