是否有算法只用很小的因子找到最接近的数字？

Question

我需要做一些实时DFT,当我可以将样本数量分解成小因子时,我使用的算法效率最高.

假设我有一个数字n和因素2, 3, 5.如何找到最接近的数字(相比较n),其素数因子化除了没有数字2,3,5？

n几乎总是在下面,50,000所以粗暴的强迫可能是一个好主意.

Answer 1

因子对的快速算法

这并不能完全解决所陈述的问题——给定某个整数 x，它只会找到最接近的大于或等于除 2 和 3（或任何其他给定的一对因子）之外没有因子的数字。但我认为它很可爱，因为它在 O(log x) 时间和 O(1) 空间中运行，所以无论如何它可能很有用！它在概念上与 Bresenham 线算法类似。在伪代码中：

1. 从 b = y = 2^RoundUp(log2(x)) 开始，这确保 b = y >= x。
2. 如果 y < x，则设置 y = y * 3 并转到 2。
3. 如果 y < b，则设置 b = y。（b 记录迄今为止最好的候选者。）
4. 如果 y 是奇数则停止并返回 b。
5. 否则，设置 y = y / 2 并转到 2。

正确性

为什么这有效？请注意，在任何时候，对于某些 i、j >= 0，我们都有 y = 2^i*3^j，并且随着时间的推移，i 只会减少，而 j 只会增加。我们在进入步骤 2 时保持的不变量是“任何具有 a > i 或 b < j 的值 z = 2^a*3^b 都被认为是无趣的（即，无效或不比某些已经发现的解决方案更好），所以不需要考虑”。当我们第一次到达步骤 2 时，这显然是正确的，因为 y 是 2 的幂并且已经 >= x，因此任何数字 z = 2^a*3^b 且 a > i 都将至少为 2*y （不管 b）哪一个比 y 更差；并且 y 中的整数 z 不能小于 3 的 j = 0 次方。

（陈述这个不变量的另一种方式是“要么我们已经找到了最优解，要么它是某个数字 z = 2^a*3^b，其中 a <= i 且 b >= j。”）

如果满足第 2 步的条件“y < x”，则 y = 2^i*3^j 不是有效解，因为它太低了。更强烈的是，很明显，对于任何 a <= i，2^a*3^j 也不能是有效的解决方案，因为任何此类解决方案至少与 y 一样低。所以现在我们知道（从不变量）任何满足（a > i OR b < j）的对（a，b）都是无趣的，并且我们从刚刚成功的“y < x”测试中知道任何对（a，b） b) 满足 (a <= i AND b = j) 也无趣。现在考虑满足稍微不同的条件 (a > i OR b < j+1) 的任何对 (a, b)：如果 (a, b) 不满足无趣的第一个条件（来自不变量），那么我们有 ( (a > i OR b < j+1) AND !(a > i OR b < j))，简化为 ((a > i OR b < j+1) AND (a <= i AND b >= j )) 通过德摩根规则，然后到 (b < j+1 AND a <= i AND b >= j) （因为使 (a <= i AND b >= j) true 需要 (a <= i) 到为真，迫使 (a > i) 为假，从而允许从 OR) 中消除它，这显然与 (a <= i AND b = j) 相同——但这正是我们有的条件刚刚通过“y < x”测试的成功建立了第二种无趣性。因此，这表明任何满足 (a > i OR b < j+1) 的对 (a, b) 都是无趣的——在递增 j 后，它恰好成为我们想要保留的不变量。

在步骤 5 中递减 i 的理由几乎相同，但相反，因此我不会详细介绍它。细微的差别是，如果我们进行到步骤 5，我们不会得到一个无效的解，而是得到一个至少与 b 中的最佳解一样高的解（请注意，如果有必要，我们会更新 b，这样就会继续保持），所以它和每一个更高的解决方案（从现在开始）对我们来说都是无趣的。

该算法生成的每个 y 值要么比任何先前生成的值少一个 2 因子，要么多一个 3 因子，因此很明显，所有生成的 y 值都是不同的。前面段落中的推理表明，唯一未生成的 y 值是那些已被证明无趣的 y 值。因此，如果算法总是在有限时间内停止，那么它就是正确的。下一节将暗示情况确实如此。

运行时间

第 5 步（具有将 i 减 1 的效果）执行的次数不会超过 log2(x)+1 次，因为 i 从该值或更小值开始，没有其他因素影响 i，并且当 i 达到 0 时，y 将为奇数，导致步骤 4 终止该函数。但是步骤 2 中将 j 加 1 的条件可以触发多少次？

最初 y >= x，因此要实现步骤 2 触发所需的 y < x 条件，需要执行步骤 5。但是，一旦通过执行步骤 5 实现 y < x，它就会在下一次执行时立即撤消第 2 步：这是因为为了执行第 5 步，我们必须有 y >= x，并且如果我们将 y 除以 2（在第 5 步），然后将其乘以 3（在下一步） 2)，它必然至少与之前一样大，这意味着 y >= x 再次，反过来意味着步骤 2 永远不会在中间不执行步骤 5 的情况下连续触发两次。因此，步骤 2 最多会触发与步骤 5 一样多的次数，即最多 log2(x)+1 次。这将算法的整体运行时间限制在 O(log x)。

笔记

• 您可以通过将步骤 1 中的 log2() 替换为循环来避免浮点运算，该循环从 1 开始 y 并不断将其加倍，直到 >= x。这是 O(log x)，因此不会影响时间复杂度。
• 您可以使用任何其他因素对。唯一真正的变化是，如果 f 是代码中“替换”2 的因子，则步骤 4 应在 y % f != 0 时停止。