5

楽しみのために、私はC ++でいくつかの数学を実装し、フェルマーの素因数分解法を実装しようとしましたが、それが何を返すのか理解していないのです。私が持っているこの実装は105、ウィキペディアの記事に記載されている例番号5959を返します。

ウィキペディアの擬似コードは次のようになります。

それが正方形であることを期待して、aのさまざまな値を試します。

FermatFactor(N): // N should be odd
    a → ceil(sqrt(N))
    b2 → a*a - N
    while b2 isn't a square:
        a → a + 1    // equivalently: b2 → b2 + 2*a + 1
        b2 → a*a - N //               a → a + 1
    endwhile
    return a - sqrt(b2) // or a + sqrt(b2)

私のC++実装は、次のようになります。

int FermatFactor(int oddNumber)
{
    double a = ceil(sqrt(static_cast<double>(oddNumber)));
    double b2 = a*a - oddNumber;
    std::cout << "B2: " << b2 << "a: " << a << std::endl;

    double tmp = sqrt(b2);
    tmp = round(tmp,1);
    while (compare_doubles(tmp*tmp, b2))  //does this line look correct?
    {
        a = a + 1;
        b2 = a*a - oddNumber;
        std::cout << "B2: " << b2 << "a: " << a << std::endl;
        tmp = sqrt(b2);
        tmp = round(tmp,1);
    }

    return static_cast<int>(a + sqrt(b2));
}

bool compare_doubles(double a, double b)
{
    int diff = std::fabs(a - b);
    return diff < std::numeric_limits<double>::epsilon();
}

何が返ってくるの？戻ってきたばかりのようですが、これは？a + bの要因ではありません。5959

編集

double cint(double x){
    double tmp = 0.0;
    if (modf(x,&tmp)>=.5)
        return x>=0?ceil(x):floor(x);
    else
        return x<0?ceil(x):floor(x);
}

double round(double r,unsigned places){
    double off=pow(10,static_cast<double>(places));
    return cint(r*off)/off;
}
4

3 に答える 3

3

コードには2つの問題があります。

  1. compare_doublesそれらが十分に接近しているときにtrueを返します。したがって、whileループ条件は逆になります。
  2. このround関数には、小数点以下の桁数が必要です。したがって、を使用する必要がありますround(x, 0)。

私が提案したようintに、データ型には使用する方が簡単です。整数を使用して実装された作業コードを次に示します。

于 2012-05-06T21:18:29.213 に答える
3

これらの計算はすべて、浮動小数点型ではなく整数型で行う必要があることに注意してください。それははるかに単純です（そしておそらくもっと正確です）。

あなたのcompare_doubles機能は間違っています。diffである必要がありdoubleます。

それを修正したら、テストラインを修正する必要があります。compare_doubles入力が「ほぼ等しい」場合はtrueを返します。それらが「ほぼ等しくない」間はループする必要があります。

それで：

bool compare_doubles(double a, double b)
{
    double diff = std::fabs(a - b);
    return diff < std::numeric_limits<double>::epsilon();
}

と：

while (!compare_doubles(tmp*tmp, b2))  // now it is
{

101そして、この入力に対して正しい結果（）が得られます。

また、 vhallacがround指摘しているように、関数を0「場所」として呼び出す必要があります。小数点以下1桁に丸めないでください。

bリンクするウィキペディアの記事には、Nとを識別できる方程式が含まれていますa-b。

于 2012-05-06T21:18:37.143 に答える
2

2つの要因は（a + b）と（ab）です。それらの1つを返しています。あなたは簡単に他を得ることができます。

N = (a+b)*(a-b)
a-b = N/(a+b)
于 2012-05-06T20:57:32.613 に答える