部分的な、またはラップされた乗算 - 誰でもこの関数を識別できますか？

Question

私は部分的な乗算のように見えるものを洞察することを望んでいます。

#define LOW(x) ((x)&0xffffffff) 
#define HIGH(x) ((x)>>32) 
unsigned long long NotMultiply(unsigned long long x, unsigned long long y) 
{ 
    return HIGH(x)*HIGH(y) + LOW(x)*LOW(y); 
} 

次のようにこの機能は、複数回繰り返される。

unsigned long long DoBusyWork(unsigned long long x, unsigned long long y, int n) 
{ 
    while (n--) 
      x = NotMultiply(x,y); 
    return x; 
} 

は、この結果を計算するための任意のショートカットはありますか？
x == yの場合はどうなりますか？

の詳細情報へのリンクは

Answer 1

LOWが底部のみ32ビットを取るしようとしています。..役立つだろう。 Highは次の32ビットを32ビット下に移動します。 NotMultiplyルーチン全体は、xとyの下位32ビットを複数倍にして上位32ビットに加算しようとしています。 DoBusyWorkはそれを行うn回。

x == yの場合、HIGH（x）² + LOW（x）²になります。

なぜ彼らはそれをやりたいのか分かりません。それは、xとyの上半分と下半分を一緒にマッシュすることです。

Answer 2

奇妙なハッシュ計算のように見えます。 2つの数字の下位32ビットを受け取り、それらを乗算し、上位32ビットを取り出し（それらを下位の場所に移動させ）、それらを乗算し、その和を返します。

私はあなたがそれをもっと簡単にすることはできないと思っていますが、おそらくもっと速くなると思います。同じ値を再び返す場合は、whileループを中断することができます。

unsigned long long DoBusyWork(unsigned long long x, unsigned long long y, int n) 
{ 
    long long previousX = x; 
    while (n--) 
    { 
      x = NotMultiply(x,y); 
      if (x == previousX) break; 
      previousX = x; 
    } 
    return x; 
} 

ループを早期に終了する可能性が高いかどうかはわかりません。

Answer 3

DoBusyWork（@RBerteigが示唆しているように、名前は赤いフラグです）は、ビジターループを最適化しないようコンパイラに指示する方法です。

これらのダンプされたコンパイラは、「ああ、あなたはループを必要としません！私はあなたが計算しようとしているものを見ています！プログラマとしてのあなたの本当の関心にもかかわらず。

Answer 4

これは、初期の形式の乱数生成器で、しばしばミニコンピュータや小さなメインフレームで使用されます。 は、このように一度呼んで、キーボードやいくつかの類似した真の乱数が、遅い方法をタイミングにより

unsigned long long seedold = 0xA5A5A5A5A5A5A5A5; 
unsigned long long seednew = 0X5A5A5A5A5A5A5A5A; 
unsigned long long lltmp; 
int finetune; 

ランダム化finetune：

lltmp = DoBusyWork(seedold, seednew, finetune); 
seedold = seednew; 
seednew = lltmp; 

その後PRNGとしてそれを使用するコールは次のようになります。

lltmp = DoBusyWork(seedold, seednew, 1); 
seedold = seednew; 
seednew = lltmp; 

シードニューをPRNとして使用します。

フォン・ノイマンは、この種の「モンテカルロ」テストアプリケーションのためにこの種の計算を提唱しましたが、後でPRNGの出力解析についてもっと学んだときに彼の心を変えました。

-A1。