根號 2 到兩百萬位的挑戰

Posted by TJ Wei on 星期二, 6月 10, 2008 with No comments

Sphere Online Judge 有一個題目是在 20 秒內計算根號 2,越多位越好(上限是兩百萬位)。有不少人能達到這個目標,但都是使用 C 或者 C++。我想試試看 python 這種以速度慢聞名的語言,能達到什麼程度。試驗的結果是十五萬位。雖然不太多,但是也擠進了排行榜裡面前二十名。而目前 python 語言的第二名還不到五萬位。

我的程式沒有用什麼特殊的技巧。事實上, python 的乘法不算太慢,現在 python 已經使用了 Karatsuba 演算法來做乘法,在一萬位以內的效能都還不錯,算到十幾萬位也都還能接受。但再上去就有點吃力了。而最主要的瓶頸在於 long 到 str 的轉換速度。光是將一個兩百萬位的數字轉成字串,就會花上非常久的時間。

改用 gmpy 會快很多,應該能夠算到百萬位以上,雖然我沒試過,但 spoj 應該不能使用 gmpy。

所以,也許應該直接寫個簡單的 FFT 乘法模組。事實上,我找到了一個叫做 DecInt 的 Pure python 套件,裡面實現了幾種快速的乘法及除法演算法,而且因為基本上資料是用十進位表示,數字轉字串非常快。他的乘法也許不是最快的,但是如果要我自己寫,大概也會是類似的東西,所以相當適合先拿來測試一下效能。

果然,大致上可以讓算十五萬位的速度快兩三倍。如果自己再強化改進,也許能再快個兩倍,但估計最多只能勉強上到百萬位,而且需要相當長時間的測試和實驗,所以我放棄。

於是我改用 Haskell 來寫。我沒有寫過 Haskell 程式(現在也還不會),而且連 Tutorial 都沒有讀完,就抓了 ghc 用最笨的方式把程式寫出來了。我只需要知道怎麼用 = 來定義函數能寫了。結果算到了一百六十萬位,足足比 python 多了十倍(Haskell 現在第二名約一百二十萬位)。如果再多加微調,或者我如果對 Haskell 再多熟悉一點,也許還能多個不少位,甚至到兩百萬位也不無可能。

其實我只要算到五十萬位,然後再用個 4-way Toom Cook 就行了,而算到四十萬位不用三秒。不過問題是,就像前面說得,其實我還不會寫 Haskell。

演算法基本上和 python 版本的相同,不過改以 recursive 的寫法。 Python 雖然完全支援 recursive 函數,但是 Python 的函數呼叫很慢,又限制層數(內定1000,最多 5000),所以,其實有點降低我把東西寫成遞迴的誘因。反之,Haskell 是 functional language,所以其實是獎勵這種寫法。

而 Haskell 之所以算得這麼快,其實有點勝之不武,因為 ghc 內建用 gmp 來做計算。

讓人疑惑的反而是,為什麼 python 不用 gmp 來做計算?

當演算法夠好,時間夠長, python 的速度劣勢就能被彌補,但 online judge 的時間限制都不太長,二十秒已經算是超級長的了,但這二十秒差不多只等於我電腦上的五、六秒,典型的時間限制是兩秒。用 pure python 實現很好的乘法演算法,也要到上萬位才能擊敗 python 內建的長整數乘法。所以,現在想用純 python(而且程式碼在4kb以內)上兩百萬位,還挺困難的,不過,也許還是有人能辦到也說不定。

(Update 2008-06-11) Haskell 達成兩百萬位。當然我 Haskell 的能力比兩天前進步一點,但主要還是用笨方法寫 recursive function。程式碼總共 11 行,而且其中有 3 行是用來定義一個函數,來達到 python 的 zfill 功能。

Categories: , ,