Tag: ieee

IEEE 也宣佈禁用 Lenna 圖了

Lenna (Lena) 是個經典的標準測試圖片，一方面是因為有很多細節可以觀察 image-related algorithm 的情況，另外一方面也是因為這張圖是取自 1972 年的 Playboy 雜誌：

Lenna (or Lena) is a standard test image used in the field of digital image processing starting in 1973, but it is no longer considered appropriate by some authors.

To explain why the image became a standard in the field, David C. Munson, editor-in-chief of IEEE Transactions on Image Processing, stated that it was a good test image because of its detail, flat regions, shading, and texture. He also noted that "the Lena image is a picture of an attractive woman. It is not surprising that the (mostly male) image processing research community gravitated toward an image that they found attractive."

也因為後者的原因，後來也有愈來愈多其他的圖片可以達到類似的效果 (甚至更好)，就有替代的聲音出現了。

另外一方面，Lena 本人在 2019 年也提到希望淡出的想法：「How a Nude “Playboy” Photo Became a Fixture in the Tech World」。

But I retired from modeling a long time ago. It’s time I retired from tech, too.

而最新的消息就是 2024/04/01 開始，IEEE 不再接受使用 Lenna 圖的投稿：「Institute bans use of Playboy test image in engineering journals」。

之後大概只會在歷史回顧的時候會引用提到了...

找數列的平均值

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

IEEE P1735 漏洞，又是 Padding Oracle Attack...

在「IEEE P1735 Encryption Is Broken—Flaws Allow Intellectual Property Theft」這邊看到 US-CERT 發表的「IEEE P1735 implementations may have weak cryptographic protections」，裡面提到的主要漏洞：

The methods are flawed and, in the most egregious cases, enable attack vectors that allow recovery of the entire underlying plaintext IP.

主要應該是第一包：

CVE-2017-13091: improperly specified padding in CBC mode allows use of an EDA tool as a decryption oracle.

又是 CBC 的 padding oracle attack 啊... 看起來是標準沒有強制定義好造成的？

The main vulnerability (CVE-2017-13091) resides in the IEEE P1735 standard's use of AES-CBC mode.

Since the standard makes no recommendation for any specific padding scheme, the developers often choose the wrong scheme, making it possible for attackers to use a well-known classic padding-oracle attack (POA) technique to decrypt the system-on-chip blueprints without knowledge of the key.

去年 Cloudflare 寫的「Padding oracles and the decline of CBC-mode cipher suites」這邊有提到 padding oracle attack 的方式，比較一般性的解法是避開要自己決定 Encrypt-then-MAC (IPsec；也是數學上證明安全性) 或 Encrypt-and-MAC (SSH) 或是 MAC-then-Encrypt (SSL)，而是用 AEAD 類的加密元件直接躲開 padding oracle attack 的某些必要條件 (像是 AES-GCM 或是 ChaCha20-Poly1305)。

不過這也是這幾年大家才了解這樣做的重要性，當年在訂規格的時候都比較沒在在意這些...

0.1 + 0.2 = 0.30000000000000004

看到「http://0.30000000000000004.com/」這個網站對經典的 0.1 + 0.2 問題整理了各語言的結果。這個網址名稱也很機車啊 XD

開頭的說明講述 IEEE 754 二進制表示法的問題：

Your language isn't broken, it's doing floating point math. Computers can only natively store integers, so they need some way of representing decimal numbers. This representation comes with some degree of inaccuracy. That's why, more often than not, .1 + .2 != .3.

It's actually pretty simple. When you have a base 10 system (like ours), it can only express fractions that use a prime factor of the base. The prime factors of 10 are 2 and 5. So 1/2, 1/4, 1/5, 1/8, and 1/10 can all be expressed cleanly because the denominators all use prime factors of 10. In contrast, 1/3, 1/6, and 1/7 are all repeating decimals because their denominators use a prime factor of 3 or 7. In binary (or base 2), the only prime factor is 2. So you can only express fractions cleanly which only contain 2 as a prime factor. In binary, 1/2, 1/4, 1/8 would all be expressed cleanly as decimals. While, 1/5 or 1/10 would be repeating decimals. So 0.1 and 0.2 (1/10 and 1/5) while clean decimals in a base 10 system, are repeating decimals in the base 2 system the computer is operating in. When you do math on these repeating decimals, you end up with leftovers which carry over when you convert the computer's base 2 (binary) number into a more human readable base 10 number.

這邊主要是討論 IEEE 754-1985 這個標準，後來在 IEEE 754-2008 提出了新的表示方法，支援十進位的表示法來解這個問題 (雖然還沒普及)。

Fast Inverse Square Root 演算法...

中文稱為「平方根倒數速演算法」，英文則是「Fast Inverse Square Root」。

好像是在 Twitter 還是 Facebook 上看到的 (還是是在其他管道？)，仔細看中文版維基百科條目，發現中文版的資料相當完整了 (看了一下歷史記錄，是去年 2012 年 6 月的時候從英文版翻出來的)。

當時很有名的 magic hack，比查表法快：

在1990年代初（也即該演算法發明的大概時間），軟體開發時通用的平方根計算方法多是從尋找表中取得近似值，而這段代碼取近似值耗時比之更短，達到精確度要求的速度也比通常使用的浮點除法計演算法快四倍，

然後還比 CPU 指令集快 XD

由於演算法所生成的用於輸入牛頓法的首次近似值已經相當精確，此演算法所得近似值的精度已可接受，而若使用與《雷神之鎚III競技場》同為1999年發行的Pentium III中的SSE指令rsqrtss計算，則計算平方根倒數的收斂速度更慢，精度也更低。

Update：請參考 comment，看起來中文版有誤譯...

我本來以為我之前寫過，找了找沒翻到... 補記錄下來 :p