Golden-Section Search 黃金比例搜尋法

依朋友們的要求，我實作了黃金比例搜尋法(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 的關係這部份，在有時間的時候我也會整理出來。