找到一个大整数是十的幂的最快方法是什么？

Question

我可以在循环中使用除法和模数,但对于非常大的整数来说这很慢.该数字存储在基数2中,可能大到2 ^ 8192.我只需要知道它是否是10的幂,所以我认为可能有一个快捷方式(除了使用查找表).

Answer 1

如果您的数字x是10的幂

x = 10^y

对于某些整数y,这意味着

x = (2^y)(5^y)

因此,将整数向右移动直到不再有尾随零(应该是一个非常低成本的操作)并计算移位的位数(称为k).现在检查剩余数量是否为5 ^ k.如果是,那么你的原始数字是10的幂.否则,它不是.由于2和5都是素数,因此这将始终有效.