Fermat的因式分解C++

爲了好玩，我一直在用C++實現一些數學方面的東西，而且我一直試圖實現Fermats Factorisation Method，但是，我不知道我明白它應該返回什麼。我有這個實現，返回105對於維基百科文章中給出的示例編號5959。Fermat的因式分解C++

在維基百科中的僞像這樣：

一個嘗試的各種值，希望是一個正方形。

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？

EDIT

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; 
}

來源

2012-05-06 Tony The Lion

'static_cast （b2）'？有沒有原因在那裏？另外'compare_doubles'是如何定義的？ – jli

@jli'b2'是我早期實現的'int'，讓我改變它，它沒有更多理由存在 –

我會爲'tmp'和'b2'使用整數類型。爲了讓測試通過，無論如何你都需要一個整數平方根「b2」。實際上，所有局部變量的ints實現都返回101. :) – vhallac

請注意，您應該對整數類型進行所有計算，而不是浮點類型。這會更簡單得多（也可能更正確）。

您的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）。

您還需要撥打round函數0作爲「地點」，因爲vhallac指出 - 小數點後您不應舍入到一位數。

您鏈接到的維基百科文章有一個等效方方式可以使您識別N和a-b中的b。

來源

2012-05-06 21:18:37 Mat

呵呵，我錯過了int diff錯誤。 :) – vhallac

增加了參考，使CW爲集體努力;-) – Mat

的兩個因素是：（a + b）和（A-B）。它正在返回其中之一。你可以很容易地得到其他人。

N = (a+b)*(a-b) 
a-b = N/(a+b)

來源

2012-05-06 20:57:32

我該如何輕鬆地從'a + b'獲得另一個？ –

我已經延長了我的回答。 –

有在你的代碼的兩個問題：

compare_doubles還真當他們是足夠接近。所以，while循環條件反轉。
round函數需要小數點後的位數。所以你應該使用round(x, 0)。

正如我所建議的那樣，爲您的數據類型使用int更容易。 Here's使用整數實現的工作代碼。

來源

2012-05-06 21:18:29 vhallac

該死的，錯過了圓蟲:) – Mat

:)你的答案更全面。隨意添加到你的，以便它可以被選爲正確的。 – vhallac

Fermat的因式分解C++

回答

相關問題