algorithm - 将数字的各个数字部分相加/求和的最快方法

Question

不久前，我在数学论坛上看到一个问题，有人在讨论一遍又一遍地将数字中的数字相加，直到获得一位数。 (即“362”会变成“3+6+2”，然后会变成“11”……然后“11”会变成“1+1”会变成“2”，因此“362”会返回2……我写了一些很好的代码来得到这个答案并发布它只是被一个用户超越，他建议模 9 中的任何数字都等于这个“无限数字和”，我检查了它，他是对的......好吧几乎是正确的，如果返回零，您必须用“9”将其关闭，但这是一个非常快速的解决方案......

362 = 3+6+2 = 11 = 1+1 = 2

或者...

362%9 = 2

无论如何，mod9 方法非常适用于无限地添加数字的总和，直到只剩下一个数字......但是只做一次怎么样(即 362 只会返回“11”)......谁能想到快速算法？

Answer 1

有一个很酷的技巧可以用二进制和固定宽度的整数对 1 位进行求和。在每次迭代中，您将每个数字的一​​半分成两个值，向下移动一个值，然后相加。第一次迭代，分隔其他数字。第二次迭代，数字对，依此类推。

鉴于 27 是 00011011 作为 8 位二进制，过程是...

00010001 + 00000101 = 00010110  <-  every other digit step
00010010 + 00000001 = 00010011  <-  pairs of digits
00000011 + 00000001 = 00000100  <-  quads, giving final result 4

你可以用十进制做一个类似的技巧，但它会比一个简单的循环效率低，除非你有一个十进制数的直接表示，快速操作将选定的数字归零并进行数字移位。所以对于 12345678 你得到...

02040608 + 01030507 = 03071115  <-  every other digit
00070015 + 00030011 = 00100026  <-  pairs
00000026 + 00000010 = 00000036  <-  quads, final result

所以 1+2+3+4+5+6+7+8 = 36，这是正确的，但只有当你的数字表示是固定宽度的小数时，你才能有效地做到这一点。它总是需要 lg(n) 次迭代，其中 lg 表示以二为底的对数，然后向上取整。

为了稍微扩展一下(基于评论中的讨论)，让我们假装这是理智的，有点......

如果你计算个位数的加法，实际上这里的工作比简单的循环还要多。与计数位的按位技巧一样，这个想法是对这些加法重新排序(使用关联性)，然后并行计算尽可能多的数，使用单个全角加法来实现两个半角加法，四个四分之一宽度加法等。数字清除和数字移位操作的开销很大，如果将其作为循环实现(计算或查找每个步骤的数字掩码和移位距离值)，则开销更大。 “循环”可能应该完全展开，并将这些掩码和移位距离作为常量包含在代码中以避免这种情况。

支持 Binary Coded Decimal (BCD) 的处理器可以处理这个问题。数字掩码和数字移位将使用位掩码和移位来实现，因为每个十进制数字将被编码为 4(或更多)位，独立于其他数字的编码。

一个问题是，如今 BCD 支持非常罕见。它曾经在 8 位和 16 位时代相当普遍，但据我所知，现在仍然支持它的处理器主要是为了向后兼容。原因包括...

非常早期的处理器不包括硬件乘法和除法。这些操作的硬件支持意味着现在将二进制转换为十进制更容易、更高效。现在几乎所有东西都使用二进制，而 BCD 大多被遗忘了。

库中有十进制数表示形式，但很少有高级语言为硬件 BCD 提供可移植支持，因此由于汇编程序不再是大多数开发人员的实际选择，因此 BCD 支持只是停止使用。

随着数字变大，即使打包的 BCD 打包效率也很低。以 10^x 为基数的数字表示具有以 10 为基数的最重要的属性，并且很容易解码为十进制。 Base 1000 每三位只需要 10 位，而不是 12 位，因为 2^10 是 1024。这足以表明您获得了 32 位的额外十进制数字 - 9 位而不是 8 位 - 而且您还剩下 2 位，例如对于符号位。

问题是，要使这种数字总计算法完全值得，您需要使用可能至少为 32 位(8 位)的固定宽度小数。这为(完全展开的)简单循环提供了 12 个操作(6 个掩码、3 个移位、3 个加法)而不是 15 个加法。不过，这是一个临界增益 - 代码中的其他问题很容易意味着它实际上更慢。

64 位(16 位十进制数字)的效率增益更明显，因为仍然只有 16 个操作(8 个掩码、4 个移位、4 个加法)而不是 31 个，但找到支持 64 位 BCD 操作的处理器的几率似乎很小。即使你这样做了，你多久需要一次？似乎不太可能值得付出努力并失去便携性。