3

我想编写一个函数，它给定一个无符号整数作为输入参数，并返回可以分解为素数 {2、3、5、7} 的下一个最高数字。这是一个简短的代码片段，显示了我想要做什么。

unsigned int getHigherNumber(unsigned int x)
{
    // obtain the next highest number that can be factored into
    // prime numbers (2, 3, 5, and 7)
    if (~(x % 2 || x % 3 || x % 5 || x % 7))
        return  x;
    else
    {
         // ???
    }  
} // end

此函数的目的是查找应填充数组的零的数量，以确保 FFTW ( link ) 等算法能够以有效的方式运行。给定的链接讨论了该算法对于可以分解为小素数的长度的输入是最佳的。

正如对该问题的评论中所建议的，如果 FFTW 算法是最优的，那么似乎只允许 2^a * 3^b * 5^c * 7^d 形式的数字。

4

3 回答 3

5

例如，标准 FFTW 分布对于大小可以分解为小素数（2、3、5 和 7）的数组最有效，否则它使用较慢的通用例程。

真的，你不需要下一个最高的，而只是相当接近的东西。最简单的方法是选择最接近的 2 的幂。这最多会浪费原始数组的大小。

为此，找到最高有效位并将其乘以 2。

找到最高有效位的明显方法：


    unsigned int v; // 32-bit word to find the log base 2 of  
    unsigned int r = 0; // r will be most significant bit

    while (v >>= 1)   
    {  
        r++;
    }
于 2012-11-25T23:19:21.100 回答
2

基于先前的答案，如果数组将非常大 ~ 2 ^ 10，并且您希望在保持简单的同时尽可能少地使用额外空间，您还可以选择 7 的最大幂次于 x，相乘5的最大幂，以此类推。那是

unsigned int getHigherNumber(unsigned int x)
{
    unsigned int ans=1;
    unsigned int primes[4]={2,3,5,7};
    for(int i=3; i>=0; i--)
    {
        for(int j=0; ; j++)
        {
            if(pow(primes[i],j)>x)
            {
                ans*=pow(7,j-1);
                if(i==0)
                    ans*=2;
                break;
            }
        }
    }
    return ans;
}

（未经测试）。我认为这应该让你得到一个比最接近的 2 次方更小的数字，但会牺牲一些速度。但这绝对不是最佳的。

于 2012-11-25T23:39:31.173 回答
0

以下算法和源代码可能没有经过高度优化以找到一般形式的下一个最高数（2^a * 3^b * 5^c * 7^d），但它很有用，因为代码将返回具有这些权力之一的最高人数。

该算法首先检查数字是否是 {2,3,5,7} 的幂。如果是，则简单地返回该数字。如果不是，则算法找到高于输入数的最小功率。

更复杂的方法将使用素数分解算法和搜索/排序，或者可能是硬编码的查找表，但这些解决方案对于此应用程序可能过于复杂。

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

// http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3
// Checks if n^x
int powerOf(int n, int x)
{
    while (n % x == 0) 
    {
        n /= x;
    }
return n == 1;
}

unsigned int hN(unsigned int x, unsigned int base)
{
    double exponent = std::ceil( std::log(x) / std::log(base) );
    double num = std::pow(base, exponent);
return static_cast<unsigned int>(num);
}

unsigned int getHigherNumber(unsigned int n)
{
    unsigned int rv = n;
    const int pnum = 4;

    // 1) Is the number a power of {2,3,5,7}?
    // If it is, then simply return it
    if(powerOf(n,2)) return rv;
    if(powerOf(n,3)) return rv;
    if(powerOf(n,5)) return rv;
    if(powerOf(n,7)) return rv;

    // 2) If not, then find next highest power of {2,3,5,7} that is the smallest
    // number higher than n
    unsigned int num0 = hN(n, 2);
    unsigned int num1 = hN(n, 3);
    unsigned int num2 = hN(n, 5);
    unsigned int num3 = hN(n, 7);

    std::vector<unsigned int>v(pnum);
    v[0] = num0;
    v[1] = num1;
    v[2] = num2;
    v[3] = num3;
    rv = *std::min_element(v.begin(),v.end());

    // 3) TODO: More sophisticated methods would use prime-factorization
    // algorithms and searching/sorting, or perhaps a look-up table, 
    // but these may be too complex for this application

 return rv;
} // end


int main()
{
    // const unsigned int num = 64;
    // const unsigned int num = 18;
    const unsigned int num = 2234;
    std::cout << "num = " << num << std::endl;
    std::cout << "higher number = " << getHigherNumber( num ) << std::endl;

} // end
于 2012-11-26T03:01:53.877 回答