寻找数字的力量 [英] finding power of a number

问题描述

我有一个很大的数字，它是几个小素数的乘积.我知道人数，也知道主要因素，但我不知道他们的力量.例如:

I have a very big number which is a product of several small primes. I know the number and also I know the prime factors but I don't know their powers. for example:

(2^a)x(3^b)x(5^c)x(7^d)x(11^e)x .. = 2310

现在，我想以非常快速有效的方式恢复指数.我想在FPGA中实现它.

Now I want to recover the exponents in a very fast and efficient manner. I want to implement it in an FPGA.

此致

推荐答案

问题是当您应该进行二进制搜索时，您正在进行线性搜索以获取正确的幂.以下是显示p的幂为10(p ^ 10)的情况的示例.此方法以O(log N)除法而不是O(N)求幂.

The issue is that you are doing a linear search for the right power when you should be doing a binary search. Below is an example showing how to the case where the power of p is 10 (p^10). This method finds the power in O(log N) divisions rather than O(N).

首先通过快速增加功率直到它变得太高来找到上限，这在步骤5发生.然后它使用二进制搜索来找到实际功率.

First find the upper limit by increasing the power quickly until it's too high, which happens at step 5. Then it uses a binary search to find the actual power.

1. 通过p检查除数.有效.
2. 通过p ^ 2检查除数.有效.
3. 通过p ^ 4检查除数.有效.
4. 通过p ^ 8检查除数.有效.
5. 通过p ^ 16检查除数.不起作用撤消/忽略这个.
6. 通过p ^((8 + 16)/2)= p ^ 12检查除数.不起作用撤消/忽略这个.
7. 通过p ^((8 + 12)/2)= p ^ 10检查除数.可行，但可能太低了.
8. 通过p ^((10 + 12)/2)= p ^ 11检查除数.不起作用撤消/忽略这个.
9. 因为(((10 + 11)/2)= 10.5不是整数，所以幂最大是低端，即10.

请注意，有一种方法实际上是将p除以p，而在第4步中，您实际上是将数字除以p ^(1 + 2 + 4 + 8)= p ^ 15，但要多一些很难解释二进制搜索部分.但是，被除数的大小会变小，因此除法运算会更快.

Note, there is a method where you actually divide by p, and at step 4, you've actually divided the number by p^(1+2+4+8)=p^15, but it's a bit more difficult to explain the binary search part. However, the size of the number being divided gets smaller, so division operations are faster.

这篇关于寻找数字的力量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！