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

Question

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

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是几何系列,其有限总和是:

  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的幂,并且两个不同幂的和等于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的规则.