栗子現場直播 千篇一栗
有很多簡單的道理,若不是被遺忘,不是察覺不到,就是知易行難。

2010年2月14日 星期日

加數加數加加數

  很無聊的數。
  因為涉及到太多的技術說明,所以一切從略。看明白就好,看不明白也罷。

  電腦學上,如果使用浮點數進行加法,就極容易有誤差。小的誤差可以接受,大的誤差不可以接受。
  如果我們把很多很多很多個 1 加起來。當總和高到一個水平,然後再繼續加一的時候,就很容易出現誤差,亦且把誤差積累下來。這樣的誤差積累有時是可以十分可怕。

  為了解決這個問題,其中最簡單的思維,是用 divide and conquer 。例如 1+2+3+4 ,就變成 (1+2)+(3+4) 。這樣的結果是好一點。但如果情況是,在一條加數上,出現一個極大數,和極大量的極小數。這樣在加數的過程中,還是會有相當多的小數會撞到大數,也會製造出誤差。

  近來想到一個比較複雜的方法。
  例如,我們要把 1-100 加起來。做之前,必需先把所有數字排序一次。
  1+2+3+4+...+100
  然後從最左計起,得到的數,依序插入數列中。
  (1+2)+3+4+...+100
  3+(3)+4+...+100
  (3+3)+4+...+100
  4+5+6+(6)+7+...+100
  (4+5)+6+6+7+...+100
  6+6+7+8+9+(9)+10+...+100
  如此類推。
  這樣做的話,即使真的出現小數撞大數而出現誤差,也因為可以保證以後不會出現其他小數,而可以安全地把小數抹殺掉。

  計算的成本是 O(n ln (n))。這比一般的加法高相當多。至於這個方法是不是好方法,或者是不是最好的方法,我不知道。找個讀數的人或許能証明些甚麼出來。

沒有留言: