有使用過網頁郵件或是一些網路討論區的人都會知道，有一種叫 CAPTCHA 的東西。CAPTCHA 是利用把隨機產生的文字經過一些扭曲、加上雜訊等動作之後的圖片，讓使用者去進行判讀，主要目的是要避免那種自動化的程式大量申請網頁郵件帳號或網路討論區帳號，再利用這些帳號來散播廣告信件。
很明顯的 CAPTCHA 的有效性，是基於「人類可以判讀」而「電腦不容易判讀」的假設之上。但是，現在電腦判讀 CAPTCHA 的能力愈來愈強，而且有些 CAPTCHA 已經混亂到人都不太容易看得清楚了。因此，這已經是一個相當嚴重的問題。最近的一些報導中顯示，包括 Gmail 和 Hotmail 的 CAPTCHA 系統都已經被有效率的破解，甚至達到平均一分鐘即可自動建立一個帳號的效率。
為了解決這個問題，也有很多人想過不同的方法。一個很明顯的「人類很擅長」而「電腦很不容易做」的工作，是圖片的辨識。其中一個例子是 KittyAuth 系統。KittyAuth 會隨機選出不同的動物的圖片，並要求使用者選出貓咪的圖片。理論上電腦很難判斷一張動物的照片是不是貓咪，所以可以達到分辨人類和電腦的效果。
不過 KittyAuth 和其它類似的系統都有同樣的缺點：他們的圖片資料庫的大小不夠。這使得破解變得容易：電腦不需要真的去判斷哪些照片是貓咪，它只需要「記住」哪些照片是貓咪就好了。如果照片都沒有經過任何更改，可以很容易利用 MD5 等 signature 比對的方式，就可以快速判斷一張照片是否在資料庫中。當然，一個解決方法是把照片進行細微的改動，例如加上一些雜訊。不過即使如此，如果資料庫不大（例如數百張照片），要比對兩張照片是否相似，也不是困難的事情。
為了解決這個問題，Microsoft Research 提出了一個叫 ASIRRA 的系統。基本上 ASIRRA 和 KittyAuth 一樣，也是使用動物的照片，要求使用者選出哪些是貓咪。不過，和 KittyAuth 不同的是，ASIRRA 和 Petfinder.com 合作。Petfinder.com 是一個幫無家可歸的寵物找到新家的服務，他們有數百萬張不同動物的照片。因此，ASIRRA 系統可以解決 KittyAuth 等系統的最大問題，即資料庫大小有限的問題。另外，為了避免電腦程式利用亂猜的方式，ASIRRA 要求使用者選出所有貓咪的圖片，而不是只選出其中一張。例如，12 張照片中，如果有未知數目的貓咪照片，則一個亂猜的程式，正確選出所有貓咪照片的機率，只有 1/4096。
那麼 Petfinder.com 能得到什麼好處呢？ASIRRA 在每張動物的照片下，增加一個 "Adopt Me" 的連結，讓有興趣的使用者，可以選擇領養照片中的動物。這同時也讓 Petfinder.com 可以大量增加其動物照片的曝光率。
目前 Microsoft Research 提供 ASIRRA 供大眾進行 beta 測試。不過這樣的系統倒底是不是真的有效呢？恐怕也很難說，畢竟理論上數百萬張照片，仍有機會透過人工方式進行分辨（畢竟這些照片一開始也是以人工方式進行分辨的）。想要破解 ASIRRA 的人，可以儘可能收集到足夠多的照片資料，以人工進行分辨後，即使沒辦法達到 100% 成功率，但若有 80% 成功率，也可以大幅提高猜對的機率（12 張照片若有 80% 猜對機率，則完全正確選中的機率會提高到 1/15）。
另一種可能的方式，是透過圖片合成。最簡單的方法，是把大量動物的照片，經過去背處理，再隨機以不同的大小，甚至不同的角度，貼在隨機的背景上（例如類似草皮的圖案）。然後，再要求使用者點選在貓咪上。為了降低亂猜的成功率，可以要求使用者需連續答對一定的次數。這樣一來，即使想要破解的人，已經取得完整經過去背處理的照片資料庫，要比對出貓咪的位置，仍會需要費一番功夫。另一種方法則是利用 3D 繪圖技術，從隨機的角度繪製不同的 3D 物品，同樣是貼在隨機的背景上，再要求使用者選出指定的物品。不過，這樣做的話，伺服器的負擔可能會變得很重。
2008年4月17日 星期四
NVIDIA 發表 CUDA 2.0 beta 版
NVIDIA 發表了 CUDA 2.0 beta 版的 Toolkit 和 SDK。這一版主要新增的功能，是對 Windows Vista 的支援（包括 32 bits 和 64 bits 版本）。NVIDIA 目前沒有提到其它 2.0 版新增的功能包括哪些，但大致上看起來，2.0 版包括了新的文件檔（其中包括一個使用 chm 格式、較容易查詢的 CUDA Reference Manual），以及新的 sample。比較細節上的新功能，目前看起來包括 3D 貼圖的支援，以及 cudaGetDeviceProperties 增加了 multiprocessor 數目以及 device 是否支援重疊操作的欄位。
CUDA 2.0 beta 可以在這裡下載
CUDA 2.0 beta 可以在這裡下載
2007年11月25日 星期日
Mahalanobis 的問題
在 Wikipedia 上介紹數學天才 Ramanujan 的文章中，提到一個有趣的問題：
假設你在一條街道上，有 n 間房子，路牌號碼是 1 ~ n。其中有一間房子（號碼 x），它的左邊所有房子的路牌號碼總和，和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間，那麼 n 和 x 各是多少？
文章中提到 Ramanujan 很快就利用連分數解出了這個問題，讓他的室友 Mahalanobis 非常驚訝。
當然，Ramanujan 是數學天才。不過這個問題讓我覺得很有意思：它看起來算是相當簡單，我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢？
考慮 x 左邊的房子，即號碼 1 ~ x-1 的房子，其路牌號碼總和就是 x(x-1)/2。它右邊的房子，路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣，所以：
x(x-1)/2 = n(n+1)/2 - x(x+1)/2
-> x^2 = n(n+1)/2
所以，問題變成，要找出一個平方數（即 x^2），它同時也是一個三角數（即 n(n+1)/2）。
這個問題其實就蠻古老的，例如有名的阿基米德分牛問題，也有類似的要求。解法的關鍵是，一個正整數 m 若是三角數，則 8m+1 會是一個平方數，反之亦然。所以，因為 x^2 是一個三角數，所以 8x^2 + 1 會是一個平方數，設它為 y^2，這樣會得到一個 Pell's equation：
y^2 - 8x^2 = 1
解 Pell's equation 的確是會用到連分數，這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解，就是 y = 3, x = 1。
要求出更多的解，除了用連分數之外，也可以用下面的方法：
y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1
因此
(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1
n 是任意正整數。也就是說，假設已經有一組解（例如 y = 3, x = 1），就可以很容易計算出更多的解。比如說：
(3 + sqrt(8))^2 = 17 + 6 sqrt(8)
所以 y = 17, x = 6 也是一組解。
現在有了 x，就需要算出 n，因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了：因為
n(n+1)/2 = x^2
-> n^2 + n = 2x^2
所以要算出 n，只需要把 x 乘上 sqrt(2)，再取整數部份即可（因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2）。所以，x = 6 的時候 n = 8。很容易驗證這個答案是正確的（1 + 2 + ... + 5 = 15，7 + 8 = 15）。另外也可以注意到因為 y^2 = 8x^2 + 1，所以
y^2 - 1 = 8x^2
-> (y + 1) (y - 1) / 4 = 2x^2
-> (y + 1) / 2 * (y - 1) / 2 = 2x^2
所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2，也就是要求得的 n。
要計算出 50 ~ 500 之間的 n，需要再找更大的 x：
(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49
(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288
這就是原問題的解了。
假設你在一條街道上，有 n 間房子，路牌號碼是 1 ~ n。其中有一間房子（號碼 x），它的左邊所有房子的路牌號碼總和，和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間，那麼 n 和 x 各是多少？
文章中提到 Ramanujan 很快就利用連分數解出了這個問題，讓他的室友 Mahalanobis 非常驚訝。
當然，Ramanujan 是數學天才。不過這個問題讓我覺得很有意思：它看起來算是相當簡單，我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢？
考慮 x 左邊的房子，即號碼 1 ~ x-1 的房子，其路牌號碼總和就是 x(x-1)/2。它右邊的房子，路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣，所以：
x(x-1)/2 = n(n+1)/2 - x(x+1)/2
-> x^2 = n(n+1)/2
所以，問題變成，要找出一個平方數（即 x^2），它同時也是一個三角數（即 n(n+1)/2）。
這個問題其實就蠻古老的，例如有名的阿基米德分牛問題，也有類似的要求。解法的關鍵是，一個正整數 m 若是三角數，則 8m+1 會是一個平方數，反之亦然。所以，因為 x^2 是一個三角數，所以 8x^2 + 1 會是一個平方數，設它為 y^2，這樣會得到一個 Pell's equation：
y^2 - 8x^2 = 1
解 Pell's equation 的確是會用到連分數，這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解，就是 y = 3, x = 1。
要求出更多的解，除了用連分數之外，也可以用下面的方法：
y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1
因此
(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1
n 是任意正整數。也就是說，假設已經有一組解（例如 y = 3, x = 1），就可以很容易計算出更多的解。比如說：
(3 + sqrt(8))^2 = 17 + 6 sqrt(8)
所以 y = 17, x = 6 也是一組解。
現在有了 x，就需要算出 n，因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了：因為
n(n+1)/2 = x^2
-> n^2 + n = 2x^2
所以要算出 n，只需要把 x 乘上 sqrt(2)，再取整數部份即可（因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2）。所以，x = 6 的時候 n = 8。很容易驗證這個答案是正確的（1 + 2 + ... + 5 = 15，7 + 8 = 15）。另外也可以注意到因為 y^2 = 8x^2 + 1，所以
y^2 - 1 = 8x^2
-> (y + 1) (y - 1) / 4 = 2x^2
-> (y + 1) / 2 * (y - 1) / 2 = 2x^2
所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2，也就是要求得的 n。
要計算出 50 ~ 500 之間的 n，需要再找更大的 x：
(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49
(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288
這就是原問題的解了。
2007年6月27日 星期三
最新的 TOP500
最新的 TOP500 列表又發表了。BlueGene/L 仍然穩居第一名，而且還有兩部新的 BlueGene 電腦進入了前十名。現在前八名的電腦都是位於美國的電腦。另外，前三名的電腦都超過了 100 TFLOPS。
前十名中另一部新電腦是 Dell 的 cluster，位於第八名。第十名的電腦也是一部新電腦，是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster，使用 Opteron 處理器和 Clearspeed 加速器，位於第十四名。
前十名中另一部新電腦是 Dell 的 cluster，位於第八名。第十名的電腦也是一部新電腦，是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster，使用 Opteron 處理器和 Clearspeed 加速器，位於第十四名。
2007年5月9日 星期三
哪種方法好？
有一隻大怪物出現在你面前，十秒內就可以把你幹掉。所以，你得在十秒內把它解決。你可以用小刀刺它：速度比較快，但是效果也比較差，要刺中六下才能解決它。或是，你可以用球棒，速度比較慢，但是效果比較好，只要打中三下就夠了。哪種方法比較好？
假設球棒的速度正好是小刀的一半，那麼，看起來似乎沒什麼差別，因為小刀刺中六下所需要的時間，和球棒打三下是一樣的。不過，這是假設每一下都能打中。如果有一個固定機率會沒打中的話，情形似乎就不同了。
如果十秒的時間，剛好可以用小刀刺十下，或是用球棒打五下。那麼，直覺來看，似乎用小刀「比較安全」，因為就算偶而沒刺到，也有比較多次機會可以補救。但真的是這樣嗎？
為了簡單起見，先假設，打中的機率和打不中的機率是一樣的（各為 50%）。這麼一來，這個問題就變成：丟五次硬幣，至少出現三次正面，和丟十次硬幣，至少出現六次正面，比較哪種方法的機率高。
丟五次硬幣中出現至少三次正面的機率是 (1 + 5 + C(5, 2))/2^5 = 16/32 = 50%。丟十次硬幣中出現至少六次正面的機率是 (1 + 10 + C(10, 2) + C(10, 3) + C(10, 4))/2^10 = 386/1024 ~= 38%。所以，如果打中的機率只有 50% 時，用小刀反而不好，看起來「直覺」好像是錯的。
不過，如果打中的提率提高了，會有什麼影響？設打中的機率是 p，則五次打中至少三次的機率是：
p^5 + 5p^4(1-p) + C(5,2)p^3(1-p)^2
如果 p = 0.9 則機率是 99.144%。
十次中打中至少六次的機率是：
p^10 + 10p^9(1-p) + C(10,2)p^8(1-p)^2 + C(10,3)p^7(1-p)^3 + C(10,4)p^6(1-p)^4
如果 p = 0.9 則機率是 99.836%。
也就是說，如果打中的機率提高到 90%，則使用小刀反而是比較好的方法。直覺畢竟是對的 (?)。
當然，認真來說，哪種方法比較好，和 p 有很密切的關係。也就是說，如果你打中怪物的準度不夠，就應該打少次一點，期待運氣好每次都命中。但是如果準度夠，就可以選擇打多次一點，比較「保險」。
假設球棒的速度正好是小刀的一半，那麼，看起來似乎沒什麼差別，因為小刀刺中六下所需要的時間，和球棒打三下是一樣的。不過，這是假設每一下都能打中。如果有一個固定機率會沒打中的話，情形似乎就不同了。
如果十秒的時間，剛好可以用小刀刺十下，或是用球棒打五下。那麼，直覺來看，似乎用小刀「比較安全」，因為就算偶而沒刺到，也有比較多次機會可以補救。但真的是這樣嗎？
為了簡單起見，先假設，打中的機率和打不中的機率是一樣的（各為 50%）。這麼一來，這個問題就變成：丟五次硬幣，至少出現三次正面，和丟十次硬幣，至少出現六次正面，比較哪種方法的機率高。
丟五次硬幣中出現至少三次正面的機率是 (1 + 5 + C(5, 2))/2^5 = 16/32 = 50%。丟十次硬幣中出現至少六次正面的機率是 (1 + 10 + C(10, 2) + C(10, 3) + C(10, 4))/2^10 = 386/1024 ~= 38%。所以，如果打中的機率只有 50% 時，用小刀反而不好，看起來「直覺」好像是錯的。
不過，如果打中的提率提高了，會有什麼影響？設打中的機率是 p，則五次打中至少三次的機率是：
p^5 + 5p^4(1-p) + C(5,2)p^3(1-p)^2
如果 p = 0.9 則機率是 99.144%。
十次中打中至少六次的機率是：
p^10 + 10p^9(1-p) + C(10,2)p^8(1-p)^2 + C(10,3)p^7(1-p)^3 + C(10,4)p^6(1-p)^4
如果 p = 0.9 則機率是 99.836%。
也就是說，如果打中的機率提高到 90%，則使用小刀反而是比較好的方法。直覺畢竟是對的 (?)。
當然，認真來說，哪種方法比較好，和 p 有很密切的關係。也就是說，如果你打中怪物的準度不夠，就應該打少次一點，期待運氣好每次都命中。但是如果準度夠，就可以選擇打多次一點，比較「保險」。
2007年2月6日 星期二
Supreme Commander demo 版即將推出
GameSpot 的這個報導說，Supreme Commander 的 demo 版將在星期二早上 9:30 am (PST) 推出（台灣時間星期三 1:30 am）。Demo 版會包括 Cybran Nation 的早期單人任務，以及一個對戰地圖 Finn's Revenge，可以選擇和三種不同難度的電腦對手對戰。
另外，BETA 測試的結束時間訂為二月十二日。
另外，BETA 測試的結束時間訂為二月十二日。
2007年1月29日 星期一
Supreme Commander beta 測試結束日期
Gas Powered Games 表示，目前暫時決定 Supreme Commander 的 beta 測試將在二月五日結束。目前的 beta 測試將以 GPGNet 的測試為主，同時也引進新的統計系統，將會記錄所有 ranked game 中的詳細資訊，包括各種單位被生產的次數等。
訂閱：
文章 (Atom)