23

フロア除算とは、結果が0に向かってではなく、常に（-∞に向かって）フロアダウンされる場合です。

除算タイプ

C / C ++でフロアまたはユークリッド整数除算を効率的に実装することは可能ですか？

（明らかな解決策は、配当の符号を確認することです）

4

6 に答える 6

8

ここに提示されたアイデアをベンチマークするためのテストプログラムを作成しました。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <windows.h>

#define N 10000000
#define M 100

int dividends[N], divisors[N], results[N];

__forceinline int floordiv_signcheck(int a, int b)
{
    return (a<0 ? a-(b-1) : a) / b;
}

__forceinline int floordiv_signcheck2(int a, int b)
{
    return (a - (a<0 ? b-1 : 0)) / b;
}

__forceinline int floordiv_signmultiply(int a, int b)
{
    return (a + (a>>(sizeof(a)*8-1))*(b-1)) / b;
}

__forceinline int floordiv_floatingpoint(int a, int b)
{
    // I imagine that the call to floor can be replaced to a cast
    // if you can get FPU rounding control to work (I couldn't).
    return floor((double)a / b);
}

void main()
{
    for (int i=0; i<N; i++)
    {
        dividends[i] = rand();
        do
            divisors[i] = rand();
        while (divisors[i]==0);
    }

    LARGE_INTEGER t0, t1;

    QueryPerformanceCounter(&t0);
    for (int j=0; j<M; j++)
        for (int i=0; i<N; i++)
            results[i] = floordiv_signcheck(dividends[i], divisors[i]);
    QueryPerformanceCounter(&t1);
    printf("signcheck    : %9llu\n", t1.QuadPart-t0.QuadPart);

    QueryPerformanceCounter(&t0);
    for (int j=0; j<M; j++)
        for (int i=0; i<N; i++)
            results[i] = floordiv_signcheck2(dividends[i], divisors[i]);
    QueryPerformanceCounter(&t1);
    printf("signcheck2   : %9llu\n", t1.QuadPart-t0.QuadPart);

    QueryPerformanceCounter(&t0);
    for (int j=0; j<M; j++)
        for (int i=0; i<N; i++)
            results[i] = floordiv_signmultiply(dividends[i], divisors[i]);
    QueryPerformanceCounter(&t1);
    printf("signmultiply : %9llu\n", t1.QuadPart-t0.QuadPart);

    QueryPerformanceCounter(&t0);
    for (int j=0; j<M; j++)
        for (int i=0; i<N; i++)
            results[i] = floordiv_floatingpoint(dividends[i], divisors[i]);
    QueryPerformanceCounter(&t1);
    printf("floatingpoint: %9llu\n", t1.QuadPart-t0.QuadPart);
}

結果：

signcheck    :  61458768
signcheck2   :  61284370
signmultiply :  61625076
floatingpoint: 287315364

したがって、私の結果によると、サインをチェックするのが最速です。

(a - (a<0 ? b-1 : 0)) / b
于 2010-11-05T22:25:53.177 に答える
4

これは私にも関係があるので、5年後にこの質問を再検討します。x86-64の2つのpure-Cバージョンと2つのインラインアセンブリバージョンでいくつかのパフォーマンス測定を行いましたが、結果は興味深いかもしれません。

床除算のテストされたバリアントは次のとおりです。

  1. 私がしばらくの間使用している実装。
  2. 上に示したもののわずかな変形で、1つの区分のみを使用します。
  3. 前のものですが、インラインアセンブリで手動で実装されています。と
  4. アセンブリで実装されたCMOVバージョン。

以下は私のベンチマークプログラムです。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#ifndef VARIANT
#define VARIANT 3
#endif

#if VARIANT == 0
#define floordiv(a, b) (((a) < 0)?((((a) + 1) / (b)) - 1):((a) / (b)))
#elif VARIANT == 1
#define floordiv(a, b) ((((a) < 0)?((a) - ((b) - 1)):(a)) / (b))
#elif VARIANT == 2
#define floordiv(a, b) ({                                   \
    int result;                                             \
    asm("test %%eax, %%eax; jns 1f; sub %1, %%eax;"         \
        "add $1, %%eax; 1: cltd; idivl %1;"                 \
        : "=a" (result)                                     \
        : "r" (b),                                          \
          "0" (a)                                           \
        : "rdx");                                           \
    result;})
#elif VARIANT == 3
#define floordiv(a, b) ({                                           \
    int result;                                                     \
    asm("mov %%eax, %%edx; sub %1, %%edx; add $1, %%edx;"           \
        "test %%eax, %%eax; cmovs %%edx, %%eax; cltd;"              \
        "idivl %1;"                                                 \
        : "=a" (result)                                             \
        : "r" (b),                                                  \
          "0" (a)                                                   \
        : "rdx");                                                   \
    result;})
#endif

double ntime(void)
{
    struct timeval tv;

    gettimeofday(&tv, NULL);
    return(tv.tv_sec + (((double)tv.tv_usec) / 1000000.0));
}

void timediv(int n, int *p, int *q, int *r)
{
    int i;

    for(i = 0; i < n; i++)
        r[i] = floordiv(p[i], q[i]);
}

int main(int argc, char **argv)
{
    int n, i, *q, *p, *r;
    double st;

    n = 10000000;
    p = malloc(sizeof(*p) * n);
    q = malloc(sizeof(*q) * n);
    r = malloc(sizeof(*r) * n);
    for(i = 0; i < n; i++) {
        p[i] = (rand() % 1000000) - 500000;
        q[i] = (rand() % 1000000) + 1;
    }

    st = ntime();
    for(i = 0; i < 100; i++)
        timediv(n, p, q, r);
    printf("%g\n", ntime() - st);
    return(0);
}

これをGCC4.9.2を使用してコンパイルしたgcc -march=native -Ofastところ、Corei5-2400での結果は次のようになりました。結果は実行ごとにかなり再現可能です。少なくとも、常に同じ順序で着地します。

  • バリアント0：7.21秒
  • バリアント1：7.26秒
  • バリアント2：6.73秒
  • バリエーション3：4.32秒

したがって、CMOV実装は少なくとも他の人を水から吹き飛ばします。私が驚いたのは、バリアント2が純粋なCバージョン（バリアント1）をかなり大幅に上回っていることです。私は、コンパイラーが少なくとも私のものと同じくらい効率的にコードを出力できるはずだと思っていました。

比較のために、他のいくつかのプラットフォームを次に示します。

AMD Athlon 64 X2 4200 +、GCC 4.7.2：

  • バリアント0：26.33秒
  • バリアント1：25.38秒
  • バリエーション2：25.19秒
  • バリエーション3：22.39秒

Xeon E3-1271 v3、GCC 4.9.2：

  • バリアント0：5.95秒
  • バリアント1：5.62秒
  • バリエーション2：5.40秒
  • バリエーション3：3.44秒

最後に、このバージョンの見かけのパフォーマンス上の利点をCMOVあまり真剣に受け止めないように警告する必要があります。現実の世界では、他のバージョンの分岐はおそらくこのベンチマークほど完全にランダムではなく、分岐予測子の場合は合理的な仕事をすることができます、分岐バージョンはより良いことが判明するかもしれません。ただし、その現実は実際に使用されているデータにかなり依存するため、の一般的なベンチマークを試してみるのはおそらく無意味です。

于 2016-04-22T12:40:08.283 に答える
2

ブランチは高価であるため、符号に基づいて結果を修正するために、ブランチを自由に作成する方が効率的です。

サインにアクセスする方法については、Hacker'sDelightの第2章の20ffページを参照してください。

于 2010-11-05T06:55:00.963 に答える
1

注：x86sar命令は、2の累乗になるとフロア除算を実行します。

于 2012-01-14T05:38:18.143 に答える
0

IEEE-754は、必要な丸めモードの1つとして-infへの丸めを指定しているので、あなたの質問に対する答えは「はい」だと思います。しかし、コンパイラを作成している場合にプロシージャを実装する方法を知りたいのか、特定のコンパイラを使用して操作を実行する方法を知りたいのかを説明できるかもしれません。

于 2010-11-04T23:48:03.360 に答える
0

C / C ++で床または除法の整数除算を効率的に実装することは可能ですか？

はい。

（明らかな解決策は、配当の符号を確認することです）

私は完全に同意し、大幅に高速な代替手段が存在するとは信じがたいでしょう。

于 2010-11-05T02:53:31.180 に答える