Tag: programming

2016 年的文章，不過算是經典的題目，所以最近又冒出來了。要怎麼找數列的平均值：「Calculating the mean of a list of numbers」。

You have a list of floating point numbers. No nasty tricks - these aren’t NaN or Infinity, just normal “simple” floating point numbers.

Now: Calculate the mean (average). Can you do it?

你有一串浮點數 (沒有 NaN 與 Infinity)，要怎麼找出平均值。要考慮的包括：

• 第一個要處理的就是設計演算法時各種會 overflow 的情況。
• 降低誤差。
• 合理的計算量。

好像很適合拿來 data team 面試時互相討論的題目？因為「平均值」是個商業上本來就有意義的指標，而且從 time-series events 灌進來的資料量有機會產生各種 overflow 情境，或是精確度問題，所以這個問題其實是個在真實世界上會遇到的情境。

想了一下，如果是 integer 的確是簡單很多 (可以算出正確的值)，但如果是 float 類型真的難很多：

It also demonstrates a problem: Floating point mathematics is very hard, and this makes it somewhat unsuitable for testing with Hypothesis.

馬上想到的地雷是在 IEEE 754 的 float 世界裡，2^24 + 1 還是 2^24：

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

int main(void)
{
    int i;
    float a;

    for (i = 0; i < 32; i++) {
        a = pow(2, i);
        printf("2^%d     = %f\n", i, a);

        a += 1;
        printf("2^%d + 1 = %f\n", i, a);
    }
}

然後在這邊可以看出差異：

2^23     = 8388608.000000
2^23 + 1 = 8388609.000000
2^24     = 16777216.000000
2^24 + 1 = 16777216.000000