
开发者用位运算优化复活节日期计算函数
来源标题:A faster Easter date function
一位开发者提出用位掩码和位移运算替代取模来快速计算复活节日期,并称该写法此前未见。该方法利用三月有31天、四月为2的幂的特性,用 % 32 截断日期,再加 v >> 7 修正溢出,避免出现4月0日这类不存在的日期。文章称这是受 Twitter/X 用户 Dirk Loss 用 ChatGPT 加速计算复活节的帖子启发而写。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
这个做法在讨论星期的文章中已经介绍并验证过,在讨论一天中时刻的那篇文章里则用得更为突出。
这里令 D = 30、c = 2,就得到可应用 MOD 32(等同于 & 31)的实用版本。
u32 v = j + m + 115 u32 month = v >> 5 u32 day = (v & 31) + (v >> 7)
最后这一步,我不确定以前是否有人完全这样做过。复活节只可能落在三月或四月(即月份 3 或 4),而幸运的是三月有 31 天,这意味着我们可以用 % 32 在那里截断日期。直接取模会让三月 32 溢出成四月 0,一个不存在的日期,所以我们加上 v >> 7 这一项,在溢出时把日期加一(这是个幸运的巧合,依赖于四月即月份 4 是 2 的幂)。
我以前见过用 % 31 做类似的事,但没见过这种干净利落的位掩码做法。
就是这样。折腾了一大堆,就为了做出一个简单流畅、几乎没法读……但很快的函数。
这篇文章的起因是 Twitter/X 用户 Dirk Loss 回复了我的一篇帖子,附上一个 ChatGPT 对话串的链接,他在其中用 AI 更快地计算复活节,并引用我的文章作为灵感。见 ChatGPT 对话串。
AI 其实做得相当不错。它利用了我先前博客文章里的经验来施加各种优化,但也对这些思路提出了新的变化。它产出的函数非常快,且在 1498–14,544 范围内准确。鉴于现代复活节规则在 1582 年之后才生效,而且其实没人需要那么久远未来的复活节,这个范围是个相当合理的选择。
出于一桩严重的「非我发明」综合征(代表全人类),我非得看看自己能不能打败 AI。我显然做到了,否则就不会有这篇博客文章。本文给出的更宽范围算法在测试过的各平台上吞吐量高出约 5-15%,延迟相近(尽管范围更宽)。
我的算法改编自《Calendrical Calculations》(Reingold 和 Dershowitz)中给出的那个。
我没有借鉴 ChatGPT 那个的任何经验,尽管我们最终采用了若干相似的步骤。
我怀疑这个函数还能进一步优化,因为它仍然带有那些可追溯到很久以前的现有算法的同一总体结构。
我花了一小会儿时间,试着用 Python 的「Z3 Theorem Prover」找一个捷径解,它找到了一种替代方案,比我主版本还快 15-20%,但只在很小的范围 [1894 .. 2199] 内准确。它放在测试用例仓库里。如果你能找到速度相近或更快、且范围更宽的版本,欢迎告诉我,我会更新仓库和本页面!
虽然这次我打败了 AI,但这是个相当温和的胜利,因为它只是个基础模型,用的算力也不多。令人难过的是,如果把前沿模型指向我在这个博客系列里一直在攻克的问题,它们大概会在一眨眼间挖出每一颗遗留的优化宝石。我希望在这个空间变得贫瘠之前,我还有时间多探索一番。
如果你喜欢这篇文章,应该在 X 上关注我,以便我在发表更多日期和算法相关文章时收到通知。
本文中声称的范围可以通过测试用例代码做穷尽验证:https://github.com/benjoffe/fast-world-calendars 。
同一个仓库也用于基准测试,其中一大批随机年份被加载到内存中进行测试。
所有结果都是通过以 -repeat=10 运行基准测试并记录中位数得到的。
-batch 标志会把每次计算运行 3 遍,再从内存加载下一条。这确保处理器不会受限于内存访问。
延迟结果使用同样的命令,但把 batch 标志换成 -latency。这个模式把每次计算的结果喂给下一次,因此没有并行化。
git clone https://github.com/benjoffe/fast-world-calendars.git cd fast-world-calendars cmake -B build -DCMAKE_BUILD_TYPE=Release cmake --build build -j ./build/bin/easter_test ./build/bin/easter_bench -batch ./build/bin/easter_bench -latency
小字号数字表示每次年份计算所需的纳秒数。
较大的数字是这些结果相对于 New 函数作为基线的比值。
注意:基准测试计算的是「自 3 月 22 日起的天数」(而非日和月),因为一些参考算法只返回这个值。
如果我对日/月这一步的优化是新颖的,那么加速幅度会比这里展示的更大。
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。