整数を3で割る最も速い方法は何ですか？
https://stackoverflow.com/questions/171301
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
int x = n / 3; // <-- make this faster
// for instance
int a = n * 3; // <-- normal integer multiplication
int b = (n << 1) + n; // <-- potentially faster multiplication
解決
これは、出力プロセッサに依存する場合にコンパイラが最適化するため、最速です。
int a;
int b;
a = some value;
b = a / 3;
他のヒント
「コンパイラに任せる」と言った男正解でしたが、「評判」はありません。彼を修正したりコメントしたりします。 int test（int a）{return a / 3;をコンパイルするようにgccに依頼しました。 } ix86の場合は、出力を逆アセンブルします。アカデミックな興味のためだけに、それは0x55555556を大まかに乗算し、その結果の64ビット結果の上位32ビットを取得します。次のようにして、これを自分で実証できます：
$ ruby -e 'puts(60000 * 0x55555556 >> 32)' 20000 $ ruby -e 'puts(72 * 0x55555556 >> 32)' 24 $
モンゴメリー部門のウィキペディアのページは読みにくいですが、幸運なことにコンパイラーたちはそれを行っています必要はありません。
値の範囲がわかっている場合、たとえば符号付き整数を3で除算し、除算する値の範囲が0〜768であることがわかっている場合は、より高速な方法があります。それを係数で乗算し、2のべき乗でその係数を3で割った値で左にシフトできます。
eg。
範囲0-＆gt; 768
10ビットのシフトを使用できます。これは1024倍になり、3で除算するため、乗数は1024/3 = 341になります。
これで、（x * 341）＆gt;＆gt;を使用できるようになりました10
（符号付き整数を使用する場合、シフトが符号付きシフトであることを確認してください）、また、シフトがビットROLLではなく実際のシフトであることを確認してください
これにより、値3が効果的に除算され、標準のx86 / x64 CPUで3による自然除算の約1.6倍の速度で実行されます。
もちろん、コンパイラーができないときにこの最適化を行うことができる唯一の理由は、コンパイラーがXの最大範囲を知らないため、この決定を行うことができないためですが、プログラマーとしては可能です。
値をより大きな値に移動してから同じことを行う方が有利な場合もあります。フルレンジのintがある場合、64ビット値にしてから、3で割る代わりに乗算とシフトを行うことができます。
最近、画像処理を高速化するためにこれを行う必要がありました。各色チャネルがバイト範囲（0〜255）である3つの色チャネルの平均を見つける必要がありました。赤、緑、青。
最初は単純に使用しました：
avg =（r + g + b）/ 3;
（各チャネルはバイト0から255であるため、r + g + bの最大値は768、最小値は0です）
数百万回の反復後、操作全体に36ミリ秒かかりました。
行を次のように変更しました：
avg =（r + g + b）* 341＆gt;＆gt; 10;
それで22ミリ秒になりました。少し工夫すれば驚くほど素晴らしいことです。
最適化を有効にし、IDEを介さずにデバッグ情報なしでプログラムをネイティブに実行していても、この高速化はC＃で発生しました。
プラットフォームおよびCコンパイラに応じて、使用するだけのようなネイティブソリューション
y = x / 3
高速にすることも、非常に低速にすることもできます（除算が完全にハードウェアで実行される場合でも、DIV命令を使用して実行される場合、この命令は最新のCPUでの乗算よりも約3〜4倍遅くなります）。最適化フラグがオンになっている非常に優れたCコンパイラは、この操作を最適化できますが、確認したい場合は、自分で最適化することをお勧めします。
最適化のためには、既知のサイズの整数を持つことが重要です。 Cでは、intのサイズは不明であるため（プラットフォームおよびコンパイラによって異なる場合があります！）、C99固定サイズ整数を使用する方が適切です。以下のコードは、符号なし32ビット整数を3で除算し、Cコンパイラが約64ビット整数を知っていることを前提としています（注：32ビットCPUアーキテクチャでも、ほとんどのCコンパイラは64ビット整数だけを処理できます罰金）：
static inline uint32_t divby3 (
uint32_t divideMe
) {
return (uint32_t)(((uint64_t)0xAAAAAAABULL * divideMe) >> 33);
}
これは聞こえるかもしれませんが、上記の方法は確かに3で除算します。そうするために必要なのは、単一の64ビット乗算とシフトです（先ほど言ったように、乗算は除算の3から4倍速いかもしれませんCPUで）。 64ビットアプリケーションでは、このコードは32ビットアプリケーションよりもはるかに高速になります（32ビットアプリケーションでは、2つの64ビット数を乗算すると、32ビット値で3回の乗算と3回の加算がかかります）-ただし、 32ビットマシンでの除算。
一方、コンパイラが非常に優れており、定数による整数除算を最適化する方法を知っている場合（最新のGCCはチェックしました）、とにかく上記のコードを生成します（GCCは正確に作成します）少なくとも最適化レベル1を有効にする場合は、「/ 3」のこのコード。他のコンパイラについては...この方法はインターネット上で非常によく文書化され言及されていても、そのようなトリックを使用することを期待することはできません。
問題は、定数に対してのみ機能し、変数には機能しないことです。あなたは常にマジックナンバー（ここでは0xAAAAAAAB）と乗算後の正しい操作（ほとんどの場合シフトおよび/または加算）を知る必要があり、両方はあなたが除算したい数に応じて異なり、両方ともCPU時間がかかりすぎますオンザフライで計算します（ハードウェア部門よりも遅くなります）。ただし、コンパイラーは、コンパイル時にこれらを計算するのは簡単です（1秒前後のコンパイル時間はほとんど役割を果たしません）。
本当に 掛け算や割り算をしたくない場合はどうしますか？ここに私がちょうど発明した近似があります。 （x / 3）=（x / 4）+（x / 12）なので動作します。しかし、（x / 12）=（x / 4）/ 3なので、十分に良くなるまでプロセスを繰り返す必要があります。
#include <stdio.h>
void main()
{
int n = 1000;
int a,b;
a = n >> 2;
b = (a >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
b = (b >> 2);
a += b;
printf("a=%d\n", a);
}
結果は330です。b=（（b + 2）＆gt;＆gt; 2）;を使用して、より正確にすることができます。丸めを考慮します。
乗算が できる場合は、2のべき乗の除数で（1/3）の適切な近似値を選択します。たとえば、n *（1/3）〜= n * 43/128 =（n * 43）＆gt;＆gt; 7。
この手法は、インディアナで最も有用です。
高速かどうかはわかりませんが、ビットごとの演算子を使用してバイナリ除算を実行する場合は、このページ：
- 商を0に設定
- 被除数と除数の左端の桁を揃える
- 繰り返し：
- 除数の上の被除数の部分が除数以上の場合：
- 次に、配当のその部分から除数を引き、
- 商の右端に連結1
- それ以外の場合、商の右端に0を連結します
- 除数を1つ右にシフトします
- 配当が除数より小さくなるまで：
- 商は正しい、配当は剰余である
- 停止
64ビットの数値の場合：
uint64_t divBy3(uint64_t x)
{
return x*12297829382473034411ULL;
}
ただし、これは予想される切り捨て整数除算ではありません。 数値がすでに3で割り切れる場合は正常に動作しますが、そうでない場合は巨大な数値を返します。
たとえば、たとえば11で実行すると6148914691236517209が返されます。これはゴミのように見えますが、実際には正しい答えです。3を掛けると11が返されます！
切り捨てる除算を探している場合は、単に/演算子を使用します。私はあなたがそれよりずっと速く得ることができることを非常に疑います。
理論：
64ビット符号なし算術は、モジュロ2 ^ 64算術です。
これは、2 ^ 64モジュラス（本質的にすべて奇数）と互いに素な整数ごとに、除算の代わりに乗算に使用できる乗法逆数が存在することを意味します。このマジックナンバーは、拡張ユークリッドアルゴリズムを使用して 3 * x + 2 ^ 64 * y = 1 方程式を解くことで取得できます。
整数部、しかし学問的なメリットしかありません...その種のトリックの恩恵を受ける実際に実行する必要がある興味深いアプリケーションになります。
非常に大きな整数の除算（たとえば、64ビットより大きい数値）の場合、数値をint []として表現し、一度に2桁を取得して3で除算することにより、除算を非常に高速に実行できます。次の2桁など。
eg。 11004/3あなたが言う
11/3 = 3、残り= 2（11-3 * 3から）
20/3 = 6、剰余= 2（20-6 * 3から）
20/3 = 6、剰余= 2（20-6 * 3から）
24/3 = 8、剰余= 0
結果 3668
internal static List<int> Div3(int[] a)
{
int remainder = 0;
var res = new List<int>();
for (int i = 0; i < a.Length; i++)
{
var val = remainder + a[i];
var div = val/3;
remainder = 10*(val%3);
if (div > 9)
{
res.Add(div/10);
res.Add(div%10);
}
else
res.Add(div);
}
if (res[0] == 0) res.RemoveAt(0);
return res;
}
簡単な計算...最大n回の反復（nはユーザーのビット数）：
uint8_t divideby3(uint8_t x)
{
uint8_t answer =0;
do
{
x>>=1;
answer+=x;
x=-x;
}while(x);
return answer;
}
ルックアップテーブルアプローチは、一部のアーキテクチャでも高速になります。
uint8_t DivBy3LU(uint8_t u8Operand)
{
uint8_t ai8Div3 = [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ....];
return ai8Div3[u8Operand];
}
