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 (リンク) などのアルゴリズムを効率的に実行できるようにするために、配列にパディングするゼロの数を見つけることです。指定されたリンクでは、小さな素数に因数分解できる長さの入力に対してアルゴリズムが最適であることが説明されています。

この質問へのコメントで示唆されているように、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 まで大きくなり、それを単純に保ちながら余分なスペースをできるだけ少なくしたい場合は、x よりも小さい 7 の最大乗数を選択することもできます。最大の 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) の次に大きい数を見つけるために高度に最適化されていない可能性がありますが、コードがこれらの力の 1 つを持つ最大数。

アルゴリズムは、最初に数値が {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 に答える