c - 最快计算总和 x^5 + x^4 + x^3...+x^0 (按位可能？) x=16

Question

对于利用缓存行预取的树布局(读取_next_缓存行 很便宜)，我需要以非常快的方式解决地址计算。我能够将问题归结为:

newIndex = nowIndex + 1 + (localChildIndex*X)

x 例如:X = 4⁵ + 4⁴ + 4³ + 4² +4⁰。

注:4为分支因子。实际上它是 16，所以是 2 的幂。这对使用按位的东西应该有用吗？

如果它需要一个循环来计算 X(performancewise)和诸如除法/乘法之类的东西，那将是非常糟糕的。这看起来是一个有趣的问题，但我无法想出一些好的计算方法。

由于它是树遍历的一部分，因此有 2 种模式是可能的:绝对计算，独立于先前的计算和增量计算，从将高 X 保存在变量中开始，然后在每个更深的层次上对其进行一些最小的东西的树。

我希望我能够弄清楚数学应该做什么。不确定是否有一种方法可以快速且无循环地执行此操作 - 但也许有人可以想出一个非常聪明的解决方案。我要感谢大家的帮助 - StackOverflow 在过去一直是我的好老师，我希望在未来随着我知识的增长能够回馈更多。

Answer 1

我将以越来越复杂和普遍的方式回答这个问题。

• 如果 x 固定为 16 则只需使用常量值 1118481 .万岁! (命名，使用魔法数字是不好的做法)

• 如果您在编译时知道一些情况，请使用一些常量甚至定义，例如:

  #define X_2 63
  #define X_4 1365
  #define X_8 37449
  #define X_16 1118481
  ...
  

• 如果您在执行时有多个已知案例，请初始化并使用以指数索引的查找表。

  int _X[MAX_EXPONENT]; // note: give it a more meaningful name :)
  

  初始化它，然后在执行时使用已知的 2^exp 指数访问。

  newIndex = nowIndex + 1 + (localChildIndex*_X[exp]);
  

• 这些值是如何预先计算的，或者如何实时有效地计算它们:总和X = x^n + x^(n - 1) + ... + x^1 + x^0是 geometric serie其有限和为:

  X = x^n + x^(n - 1) + ... + x^1 + x^0 = (1-x^(n + 1))/(1-x)
  

• 关于按位运算，如 Oli Charlesworth 所述，如果 x 是 2 的幂(二进制 0..010..0)x^n也是2的幂，2的不同次幂之和相当于OR运算。因此我们可以这样表达:

  让exp是指数，使 x = 2^exp。 (对于 16，exp = 4)。然后，

  X = x^5 + ... + x^1 + x^0
  X = (2^exp)^5 + ... + (2^exp)^1 + 1
  X = 2^(exp*5) + ... + 2^(exp*1) + 1
  

  现在使用按位，2^n = 1<<n

  X = 1<<(exp*5) | ... | 1<<exp | 1
  

  在 C 中:

  int X;
  int exp = 4; //for x == 16
  X = 1 << (exp*5) | 1 << (exp*4) | 1 << (exp*3) | 1 << (exp*2) | 1 << (exp*1) | 1;
  

• 最后，我忍不住要说:如果您的表达式更复杂并且您必须计算任意多项式 a_n*x^n + ... + a_1*x^1 + a_0在 x 中，不是实现明显的循环，而是使用 Horner's rule 来计算多项式的更快方法。 .