Существует ли функция c ++ (встроенная или иная), которая дает результаты целочисленного и модульного деления без повторения операции? - PullRequest
Новая
       6

Существует ли функция c ++ (встроенная или иная), которая дает результаты целочисленного и модульного деления без повторения операции?

5 голосов
/ 15 сентября 2011

Вы могли бы написать что-то вроде: 

int i = 3;
int k = 2;
int division = i / k;
int remainder = i % k;

Кажется, что на низком уровне это попросило бы АЛУ выполнить две операции зрения: одна возвращает частное, а другая возвращает остаток.Тем не менее, я считаю, что ALU, скорее всего, будет рассчитывать оба в одной операции.Если это так, то это не оптимально эффективно.

Есть ли более эффективный способ сделать это, не прося ЦП рассчитывать дважды?Другими словами, можно ли сделать это за одну операцию из C ++?

Ответы [ 5 ]

9 голосов
/ 15 сентября 2011

На самом деле код, который вы написали, не будет генерировать никаких инструкций деления, так как компилятор может выяснить результаты во время компиляции. Я написал небольшую тестовую программу и настроил компилятор (VC ++ 10SP1) для генерации списка кода сборки. 

#include <iostream>

using namespace std;

struct result {
    long quotient, remainder;
};

result divide(long num, long den) {
    result d = { num / den, num % den };
    return d;
}

int main() {
    result d = divide(3, 2);
    d = divide(10, 3);
    cout << d.quotient << " : " << d.remainder << endl;
    return 0;
}

Я должен был написать это таким образом и явно указать компилятору не включать какие-либо функции. В противном случае компилятор с удовольствием оптимизировал бы большую часть кода. Вот результирующий ассемблерный код для функции деления. 

; 8    : result divide(long num, long den) {

  00000 55       push    ebp
  00001 8b ec        mov     ebp, esp

; 9    :     result d = { num / den, num % den };

  00003 99       cdq
  00004 f7 7d 08     idiv    DWORD PTR _den$[ebp]

; 10   :     return d;
; 11   : }

  00007 5d       pop     ebp
  00008 c3       ret     0

Он достаточно умен, чтобы генерировать одну инструкцию IDIV и использовать сгенерированные ею частное и остаток. Современные компиляторы C и C ++ действительно хорошо справились с такой оптимизацией. Если у вас нет проблем с производительностью и вы не профилировали свой код, чтобы определить узкое место, не пытайтесь угадать компилятор.

5 голосов
/ 15 сентября 2011

ISO C99 имеет функцию ldiv: 

#include <stdlib.h>

ldiv_t ldiv(long numer, long denom);

The ldiv() function computes the value numer/denom (numerator/denominator).
It returns the quotient and remainder in a structure named ldiv_t that contains
two long members named quot and rem.

На уровне FPU, который сводится к одной операции, я не могу сказать.

5 голосов
/ 15 сентября 2011

Конечно: 

int i = 3;
int k = 2;
int division = i / k;
int remainder = i - division * k;

Кроме того, если вы действительно хотите это сделать, посмотрите на div, хотя я сомневаюсь, что это быстрее, так же, как мое решение выше.

1 голос
/ 15 сентября 2011

Я не знаю ничего встроенного, но вы можете смоделировать это с умножением вместо деления: 

int division = i / k;
int remainder = i - (division * k);
0 голосов
/ 15 сентября 2011

Когда вы спрашиваете себя, что является самым быстрым, обычно хорошей идеей является его тестирование (мне нравится это делать).Итак, я взял ответы отсюда, написал крошечную программу бенчмаркинга и бросил ее на gcc (аналогичные результаты можно ожидать для g++, я думаю) на -O0 (на -O1 он все оптимизирует, и мой тестне работает).

Я выполнил 2^28 прогонов (i и k с 1 до 2^14) на моем ноутбуке и получил следующие прогоны: 

division = 0;
remainder = 0;
// this test is only there to measure the constant overhead!

1,667 с 

division = i/k;
remainder = i%k;

24,614 с 

division = i/k;
remainder = i - division*k;

15,009 с 

ldiv_t d = ldiv(i,k);
division = d.quot;
remainder = d.rem;

18,845 с

Как можно видеть, там - это разница, и ваш лучший шанс - это умножение.Подход ldiv тоже подойдет, но я считаю его немного громоздким по сравнению с другими.

...