3

我希望深入了解看起来像部分乘法的东西。

#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 的情况呢？

任何指向更多信息的链接都会有所帮助..

4

4 回答 4

1

DoBusyWork（正如@RBerteig 所建议的那样，名称是一个危险信号）可能是一种强制编译器不优化繁忙循环的方法。

这些该死的编译器变得如此聪明，以至于有时他们会决定，“哦！你不需要循环！我知道你要计算什么了！” 尽管您作为程序员真正感兴趣。

于 2009-04-29T01:01:29.997 回答
1

看起来像一个奇怪的哈希计算。它取两个数字的低 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;
}

我不知道是否有很大的机会提前完成循环。

于 2009-04-28T19:59:03.873 回答
1

这是随机数生成器的早期形式，通常用于小型计算机和小型大型机。调用可能如下所示：

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;

使用 seednew 作为 PRN。

Von Neumann 曾经提倡将这种计算用于“Monte-Carlo”测试应用程序，但后来当他了解更多关于分析 PRNG 的输出时改变了主意。

-阿尔。

于 2009-04-29T20:58:07.610 回答
0

LOW 试图只取低 32 位。High 将接下来的 32 位向下移动 32 位。整个 NotMultiply 例程试图将 x 和 y 的底部 32 位相乘，并将它们添加到顶部 32 位。DoBusyWork 做了n次。

如果 x==y，则得到 HIGH(x)²+LOW(x)²。

不过，我不知道他们为什么要这样做。这有点像将 x 和 y 的上半部分和下半部分混合在一起。

于 2009-04-28T19:52:59.177 回答