2008年1月9日 星期三

Golden-Section Search 黃金比例搜尋法

Standard
依朋友們的要求,我實作了黃金比例搜尋法(Golden-Section Search) 的程式,用來尋找一個 f(x) 的最小值。這程式非常的簡短,是短短時間內寫出來的,所以並沒有考慮到效能、流程優化的部份,就像是 x 在某些狀況可以直接沿用到下次的 x1 或 x2,不需要將 x1、 x2 完全重新計算的這部份也是值得去探討的。

原始程式碼:

#include <stdio.h>
#include <math.h>

#define F(x) ((pow(x,2)/10)-2*sin(x))

void main()
{
int i, n;
double range_min = 0;
double range_max = 4;
double d, x1, x2;

printf("Number of lines:");
scanf("%d", &n);

printf("i xl f(xl) x2 f(x2) x1 f(x1) xu f(xu) d\n");
for (i=1;i<=n;i++) {
d = 0.61803*(range_max - range_min);
x1 = range_min + d;
x2 = range_max - d;
printf("%d %6.4f %6.4f %6.4f %6.4f %6.4f %6.4f %6.4f %6.4f %6.4f\n", i,
range_min, F(range_min),
x2, F(x2),
x1, F(x1),
range_max, F(range_max),
d);
if (F(x2)>F(x1)) { /* 取右邊 */
range_min = x2;
x2 = x1;
} else { /* 取左邊 */
range_max = x1;
x1 = x2;
}
}


後記

談到程式優化的話題雖扯遠了,但我們不可以忽略掉它,因為這是一個專業程式人員該時時省思的課題。程式優化的層面很廣,除了流程上的優化,更還有考慮到硬體結構的優化改進。最近就正在整理一些關於優化程式的議題:如何更有效率的運用 CPU 暫存器,運用更少的指令和時鐘(Clock)完成任務等。

更多從優化衍生出來的議題,如透過組合語言(Asembly)去了解 CPU 等硬體的運作,並了解 C 語言或各種 Low-level library 對應的 CPU 指令效能,都是很值得我們去研究的。所以,分析各種高階語言與 ASM、CPU command 的關係這部份,在有時間的時候我也會整理出來。