我正在寫幾個方法的實現,使用C中的GMP來查找數字的自然日誌。我有兩個函數,這兩個函數都可以工作,但其中一個函數比另一個運行得慢很多。問題在於,我認爲這是最快速度最慢的那個。爲什麼我的一個函數運行速度太慢?
以下是兩個相關功能,可以找到int main
的完整文件here,而所需的ln_2.txt
文件爲here。
void taylor_log(mpf_t R,
const mpf_t N,
const mpf_t T)
{
mpf_t x, y, r, pr, tmp, d;
int n = 1;
mpf_init(x);
mpf_init(y);
mpf_init(tmp);
mpf_init(d);
mpf_sub_ui(x, N, 1);
mpf_init_set(y, x);
mpf_init_set(r, x);
mpf_init_set_ui(pr, 0);
mpf_sub(d, r, pr);
mpf_abs(d, d);
while(mpf_cmp(d, T) > 0)
{
mpf_set(pr, r);
mpf_mul(y, y, x);
mpf_div_ui(tmp, y, ++n);
mpf_sub(r, r, tmp);
mpf_mul(y, y, x);
mpf_div_ui(tmp, y, ++n);
mpf_add(r, r, tmp);
mpf_sub(d, r, pr);
mpf_abs(d,d);
}
printf("%d\n", n);
mpf_set(R, r);
}
void hyperbolic_log(mpf_t R,
const mpf_t N,
const mpf_t T)
{
mpf_t x, x2, r, pr, tmp, d;
int n = 1;
mpf_init(x);
mpf_init(x2);
mpf_init(tmp);
mpf_init(d);
mpf_sub_ui(x, N, 1);
mpf_add_ui(tmp, N, 1);
mpf_div(x, x, tmp);
mpf_init_set(r, x);
mpf_init_set_ui(pr, 0);
mpf_mul(x2, x, x);
mpf_sub(d, r, pr);
mpf_abs(d,d);
while(mpf_cmp(d, T) > 0)
{
mpf_set(pr, r);
++n;
mpf_mul(x, x, x2);
mpf_div_ui(tmp, x, ++n);
mpf_add(r, r, tmp);
mpf_sub(d, r, pr);
mpf_abs(d,d);
}
printf("%d\n", n);
mpf_mul_ui(R, r, 2);
}
現在第二個功能應,至少在理論上,跑得快一點,因爲它有每個環路更少的指令和執行通常由於更快的收斂較少的循環。這不是我在實踐中看到的情況,因爲當我在計算中使用至少33296位計算ln(2)到10000小數位數時,兩者都給出了正確的結果,但第一種方法在大約0.150秒內完成,而第二種方法需要大約1秒。
我不知道是什麼導致一個函數運行比其他更慢,任何幫助將不勝感激。
編輯: 爲了清楚起見,我忘了提及,在傳遞給函數之前,值被歸一化到範圍[0.5,1)。對於我已經證實這在程序中起作用的兩個函數,這是一樣的,所以技術上我的問題是當0.5提供給算法。
你的argv值是多少?我查看了你的粘貼,我會下載並構建,因爲我有一些性能分析例程可以插入。但是,我不得不猜測argv的值。而且,一個愚蠢/侮辱性的問題:你能證明你已經正確實施了兩個標準嗎?作爲一般規則,我會添加更多註釋(例如,文件頂部的方程式,以及與行列式相關的逐行註釋,這樣做可能會發現您在gmp中發現了一個微不足道的錯誤調用(例如,多線程和div等),還提到了時序,但是沒有提供每個循環的計數 –
另外,它似乎只有一個測試編號,多個編號會有幫助嗎?您保證是算法不可知的一個?當我做這樣的測試時,我通常會嘗試一些邊緣情況下的測試數字,比如對algA有好處,對algB不好(反之亦然)。你可能會變得「幸運」。再多幾個數字可能有助於證明/反駁這個 –
「每個循環的指令數少」......好吧,對於arb-prec,指令在成本上差別很大,例如,較慢的數字是否更大? – imallett