algorithm - 2的幂得到一个整数

Question

我需要一种(相当)快速的方法来为我的代码获取以下内容。背景:我必须处理数字的幂及其乘积，所以我决定使用对数。现在我需要一种方法将日志转换回整数。

我不能只取 2^log_val(我正在使用对数基数 2)，因为答案太大了。事实上，我需要为给定的 M 给出答案 mod M。

我试过这样做。我将 log_val 写成 p+q，其中 q 是一个 float ，q < 1 并且 p 是一个整数。现在我可以使用 log n 求幂和模数非常快速地计算 2^p，但是我不能用 2^q 做任何事情。我想做的是找到 2 的第一个整数幂，比如 x，这样 2^(x+q) 非常接近整数，然后计算 2^p-x。

这对我来说太长了，因为在最坏的情况下我会采取 O(p) 步。有没有更好的办法？

Answer 1

虽然使用大量数字作为日志通常是一种好方法，但在这里行不通。问题是在日志空间中工作会丢弃最低有效数字，因此您丢失了信息，并且无法返回。在 mod 空间中工作也会丢弃信息(否则你的数字会变大，正如你所说)，但它会丢弃最重要的信息。

对于您的特定问题 POWERMUL，我要做的是计算从 1 到 N 的数字的质因数分解。您必须小心操作，因为您的 N 相当大。

现在，如果你的数字是 k 并且素数分解 {2: 3, 5: 2} 你得到 k^m 由 {2: m*3, 5:m*2}。除法同样变成减法。

一旦有了 f(N)/(f(r)*f(N-r)) 的质因数分解表示，您就可以结合模乘和求幂重新创建整数。后者是一种很酷的查找技术。 (事实上​​ ，像 python 这样的语言内置了 pow(3, 16, 7)=4。

玩得开心:)