分工的劳动(第一集)

主要观点:

  • 介绍在 C 语言中如何用特定方法将无符号整数除以 13 及对应的 x64 汇编代码,其中涉及“魔法数”1321528399 用于替代除法的乘法操作。
  • 详细阐述通过证明找到合适的“魔法数”来近似除法,包括推导过程、精度选择、算法实现等,还提到对于特定除数可改进算法以找到更高效的“魔法数”。
  • 说明每个除数都有“魔法数”,多数有多个,运行时通过乘“魔法数”再除以 2 的幂来实现除法,运气好时“魔法数”可在 32 位内,否则可用 33 位。

关键信息:

  • 无符号整数除以 13 的 C 语言代码和 x64 汇编代码。
  • “魔法数”的定义及作用,如 1321528399 用于乘法替代除法。
  • 证明过程中涉及的各种变量和等式,如 $m_{exact} = \\frac {2^k} d$ 等。
  • 精度 k 的选择及对“魔法数”m 的影响,如 $k = 32 + \\lceil \\log\_2 d \\rceil$ 。
  • 针对特定除数改进算法的方法,如尝试不同幂的 2 找到更高效的“魔法数”。

重要细节:

  • x64 汇编代码中 mulhwu 指令的含义及操作。
  • 证明中对不同情况的分析,如向下取整和向上取整 m 时的结果差异。
  • 算法实现的各个步骤,如预处理 p、计算 m、q 等。
  • 对于特定除数如 11 和 641 时算法的优化及代码示例。
  • 提及对传奇人物 Guy Steele Henry Warren及其著作的引用。
阅读 7
0 条评论