1

我想在 24 位 dsp 上移植 32 x 32 位无符号乘法（它是一个线性同余生成器，所以我不允许截断，我也不想用 24 位替换当前的 LCG ）。可用的数据类型为 24 位和 48 位整数。

只需要最后 32 LSB。你知道有什么技巧可以比通常的方式以更少的乘法、掩码和班次来实现吗？

该行如下所示：

//val is an int(32 bit)
val = (1664525 * val) + 1013904223;
4

2 回答 2

0

大纲将是（以我当前的编译器样式）：

static uint48_t val = SEED;
...
val = 0xFFFFFFFFUL & ((1664525UL * val) + 1013904223UL);

并希望编译器能够识别：

  • 它可以使用乘法和累加命令
  • 由于常数的“高位字”为零，它只需要一个简化的乘法算法
  • AND 可以通过重置高位或乘以常数并恢复来实现
  • ...其他东西取决于你的 {mystery dsp} 目标

请注意 ，如果您将系数放大 2^16，则可以免费截断，但由于缺乏信息，您将不得不探索/决定总体上是否更好。

于 2014-08-09T07:11:34.630 回答
0

（这更详细说明了为什么两次乘法24×24→n, 31<n 就足够了 32×32→min(n, 40)。）
这个问题几乎没有揭示在以下位置构建方法
32×21→32 in fewer [24×24] multiplies, masks and shifts than the usual way的能力：
24 and 48 bit ints& DSP（我读的是高吞吐量，非高延迟24×24→48）。
就确实存在24×24→48乘法（甚至24×24+56→56 MAC）并且一个因子小于 24 位而言，这个问题毫无意义，第二个乘法是令人信服的解决方案。

24<n<48×24<m<48→24<p从24×24→48相乘的通常组合使用后者中的三个；编译器应该和编码器一样知道“第四次乘法”会产生意义/位置超过因子较低部分的组合长度的位。
那么，是否可以仅使用第二个24×24→48生成“长产品” ？
让（字节的）因子分别为w_xyz和W_XYZ；如果解释为 24 位整数，则下划线表示“<em>Ws”是较高重要性字/整数中的较低重要性位。第一个24×24→48给出了
  <strong>的总和

xX yYzZ
 x YyZ xZ
  ，需要（胖）是
 w Z +
 z W。这可以使用((w<<16)|(z & 0xff)) × ((W<<16)|(Z & 0xff))的一个组合乘法
来计算。（不要介意 wZ+zW “运行”到 wW 的第 17 位。） （在这个答案的第一个修订版中，我愚蠢地分别生成了wZ和zW - 无论如何，它们的总和最终是想要的。） （令人讨厌的是，这是关于24×24→24作为基本运算你所能做的一切——除了这个“组合乘法”之外，你需要四个而不是一个。）


另一个探索的角度是选择不同的 PRNG。它可能必须大于 24 位（告诉！）。
在 24 位机器上，XorShift*（甚至 XorShift+）48/32似乎值得一看。

于 2018-01-01T16:40:23.387 回答