Project Euler 198 題

Project Euler 的 198 題。簡單的說，要算出分母在 10^8 以內，大小在 0~0.01 之間的「混淆數」總共有幾個 。而所謂的混淆數 x，是指如果對於某個 m，分母不超過 m 的「最近似 x 的分數」不只一個時，就稱 x 為混淆數。比方對於 x=9/40 來說，m=6 時， 1/5 和 1/4 都是分母不超過 6 最近似 x 的分數。
這個題目其實如果沒有任何基礎知識的話，還不太容易，所以解出的人不多。但站在一些基礎知識之上， 10^8 這種數量級是很容易用程式來秒殺的。據說 Knuth 的 The Art of Computer Programming 裡面就有提供相關的演算法。
不過使用 Haskell，可以很直接的用遞迴解出：

f a b l m | a*b>l || (a==1 && b > m)  = 0
         | otherwise = (f a c l m)+1+(f c b l m) where c=a+b
main = putStrLn $ show result
      where result= (f 1 100 l2 m) + 49+l2-m
      l = 10^8
      l2 = l `div` 2
      m = floor (sqrt (fromIntegral l2)

七行就簡單解決了。如果你知道背後的數學，上面的程式碼其實是很直接的。但用 Python 解就麻煩了，因為上面這個遞迴解超出 Python 的遞迴深度。可以用迴圈來取代遞迴，如下面的演算法：

def p198(M=10**8, z=100, cnt=0):
 M2=M/2
 a=m=int(M2**0.5)
 stack=range(z,m)
 while stack:
     b=stack[-1]
     if a*b>M2:
         a=stack.pop()
     else:
         cnt+=1
         stack.append(a+b)
 return cnt+M2-z/2

(程式碼我從 Project Euler 直接貼過來，排版有點亂掉）
這個演算法是我參考別人的解答後寫出的，配上 psyco 後，其實還挺巧妙也挺快的，但不太容易讀懂，要跟蹤一下堆疊是怎麼跑的。
但有些簡單的工作， Haskell 寫起來又很累贅。比方有一個整數 n，想找出它的根號的整數部份，如後印出來，在 python 來說再簡單不過的

print int(x**0.5).

Haskell 的作法要先將整數轉成浮點數，開根號，然後再用 floor 轉成整數，最後再用 show 轉成字串才能印出。所以是

putStrLn.show $ (floor . sqrt) (fromIntegral n)

如果有許多浮點數與整數，那更複雜一點的運算就要轉來轉去。雖說這樣可以強迫正確的設計風格，但有時只是簡單的小計算，這樣也未免太累了。
果然 Haskell 能將複雜工作簡單化，簡單工作複雜化。

Read More

程式設計語錄

圖片來源: wikipedia

(選自 DevTopics 整理的語錄)
(用來讓自己看起有學問的)

• "Simplicity, carried to the extreme, becomes elegance."  簡單到極致即為優雅。
  – Jon Franklin
• "The best way to predict the future is to implement it."  預測未來的最佳方式就是實做它。
  – David Heinemeier Hansson
• "Make everything as simple as possible, but not simpler."   儘量讓事情簡化，但別太簡化。
  – Albert Einstein
• "The difference between theory and practice is that in theory, there is no difference between theory and practice."  理論和實務的差別在於，理論上，理論和實務沒有分別。
  – Richard Moore
• "The greatest enemy of knowledge is not ignorance, it is the illusion of knowledge."  知識的的敵人不是無知，而是知識的假象。
  – Stephen Hawking
• "密碼就像內褲一樣： 不要讓別人看到，要常常更換，而且，別和陌生人共用."
  – Chris Pirillo
• "Computers are like bikinis. They save people a lot of guesswork." 電腦就像比基尼，幫我們省下許多猜測的麻煩。
  (Sam Ewing)
• "Come to think of it, there are already a million monkeys on a million typewriters, and Usenet is nothing like Shakespeare."  其實想想，現在已經有上百萬隻猴子坐在上百萬台打字機前了，但網路論壇一點也不像莎士比亞。(現在可用來描寫部落格)
  (Blair Houghton)
• "Hardware: The parts of a computer system that can be kicked." 
  (Jeff Pesis)
• "Web Services are like teenage sex. Everyone is talking about doing it, and those who are actually doing it are doing it badly." (網路服務) 
  – Michelle Bustamante
• "The best way to get accurate information on Usenet is to post something wrong and wait for corrections."
  – Matthew Austern

程式師的幽默

• 問：為什麼程式設計師是分不清萬聖節和聖誕節？
  答：因為 Oct 31 = Dec 25.
• 一個男人在吸煙，他的女朋友很生氣的說："Can't you see the warning on the cigarette pack? Smoking is hazardous to your health!" 男人回答說： "I am a programmer. We don't worry about warnings; we only worry about errors."
  
• "I think Microsoft named .Net so it wouldn't show up in a Unix directory listing."
  (Oktal)
• "C++ : Where friends have access to your private members."
  (Gavin Russell Baker)
• "Computers are getting smarter all the time. Scientists tell us that soon they will be able to talk to us. (And by 'they', I mean 'computers'. I doubt scientists will ever be able to talk to us.)"
  (Dave Barry)
• "I've noticed lately that the paranoid fear of computers becoming intelligent and taking over the world has almost entirely disappeared from the common culture. Near as I can tell, this coincides with the release of MS-DOS."
  (Larry DeLuca)
• "It was a joke, okay? If we thought it would actually be used, we wouldn't have written it!"
  – Mark Andreesen, 談 HTML 的 BLINK 標籤

程式師與使用者

• The three most dangerous things in the world are a programmer with a soldering iron, a hardware engineer with a software patch, and a user with an idea. - The Wizardry Compiled by Rick Cook
• "If you think your users are idiots, only idiots will use it."
  – Linus Torvalds
• "From a programmer's point of view, the user is a peripheral that types when you issue a read request."
  – P. Williams
• "Computers are good at following instructions, but not at reading your mind."
  – Donald Knuth
• "There is only one problem with common sense; it's not very common."
  – Milt Bryce
• "Your most unhappy customers are your greatest source of learning."
  – Bill Gates
• "There are only two industries that refer to their customers as 'users'."(販毒業與軟體業)
  (Edward Tufte)
• 
  "Any fool can use a computer. Many do."
  (Ted Nelson)
• "That's the thing about people who think they hate computers. What they really hate is lousy programmers."
  (Larry Niven)
• "Just remember: you're not a 'dummy,' no matter what those computer books claim. The real dummies are the people who–though technically expert–couldn't design hardware and software that's usable by normal consumers if their lives depended upon it."
  (Walter Mossberg)
• "Software suppliers are trying to make their software packages more 'user-friendly'… Their best approach so far has been to take all the old brochures and stamp the words 'user-friendly' on the cover."
  (Bill Gates)
• "There's an old story about the person who wished his computer were as easy to use as his telephone. That wish has come true, since I no longer know how to use my telephone."
  (Bjarne Stroustrup)

程式設計

• (程式註解)"Commenting your code is like cleaning your bathroom — you never want to do it, but it really does create a more pleasant experience for you and your guests."
  – Ryan Campbell
• "Low-level programming is good for the programmer's soul."
  – John Carmack
• "A program is never less than 90% complete, and never more than 95% complete."
  – Terry Baker
• "Manually managing blocks of memory in C is like juggling bars of soap in a prison shower: It's all fun and games until you forget about one of them."
  – anonymous Usenet use"
• "Standards are always out of date. That's what makes them standards."
  – Alan Bennett
• "There's no obfuscated Perl contest because it's pointless."
  – Jeff Polk
• "Some people, when confronted with a problem, think 'I know, I'll use regular expressions.' Now they have two problems."
  – Jamie Zawinski
• "You can't have great software without a great team, and most software teams behave like dysfunctional families."
  (Jim McCarthy)
• "There are only two kinds of programming languages: those people always bitch about and those nobody uses."
  (Bjarne Stroustrup)

Read More

zhpy 的另類用法

配合上 zhpy ，我們可以寫出下面這樣的 python 程式:

# encoding: zhpy_utf8
from math import *
from operator import *
print Σ(range(100))
print sin(π/4) ≠ √(2)/2
print ㏒(100), ㏑(e)
print 5 × 30 ÷ 2 ≦ tan(√(5)*π/4)
Π=λ f:reduce(mul, f, 1)
print Π(range(1,6))
print set([1, 2, 3, 4, 5]) ∩ set([1, 3, 5, 7, 9])

(第一行是 MagicCodec 語法，普通的 zhpy 請去掉第一行)
不管實不實用，至少增加了一點可讀性。既然是λ，為什麼要寫成 lambda?
以上的程式碼只需要下面的 zhpy .ini 檔案（可以叫做 math.ini，放在執行的目錄下)

[math]
λ=lambda
π=pi
Σ=sum
≠=!=
÷=/
×=*
㏒=log10
㏑=log
√=sqrt
≧=>=
≦=<= ∩=& ∪=l

for 和 in 可以換成相對應的符號, set 的 <, <= 也可以換成 set 符號。
Haskell 的 ide Lesksah 就能做到這件事情。 如果能夠把 lyx 修改成 python, haskell 或者其他程式語言的編輯器，應該也挺有趣的。
相關的東西是 TeXmacs 的 python plugin tmPython，

Read More

根號 2 到兩百萬位的挑戰

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 功能。

Read More

Euler 計畫和其他

前一陣註冊了 Project Euler，然後玩了一下裡面的題目。
Project Euler 蒐集了一系列的挑戰問題，這些問題的答案都是一個數字或者一組數字。每當你破解一個問題後，你就能與其他同樣破解這個問題的人，討論答案與心得。通常解決這問題需要一點程式設計技巧和數學知識。

網站裡面也會對於不同國家或者程式語言的解題者做統計和排名。比方說這是台灣的統計，而這是 Python 語言的統計。和「點點點」相比，台灣的表現很爛。
一般所謂的 online judge 系統其實很多，ACM 風格的 online judge 是主流。 UVa online judge 是其中的代表。其他還有如ZeroJudge。
和 Project Euler 不同， Project Euler 上傳的是答案，而這類 online judge 要你上傳的是「程式」。所以有限定使用的程式語言。標準的語言是 C,C++,Java。雖然我也寫 C++和C，但我還是比較喜歡能自由選擇工具。這點到不是根本性的問題，像是 Sphere Online Judge 就能讓你使用許多不同的程式語言，包含 perl, ruby, python。
另外一個不同點是時間限制，雖然 Project Euler 也有所謂的「一分鐘法則」，就是程式應該要能在一分鐘跑完，但這不是硬性規定，真正的裁判是你自己。事實上，如果你喜歡（而且可以的話），你甚至可以 用google 找答案。真正的裁判是你自己。我喜歡這種風格。
一般的 online judge，有些題目有時間限制。就比賽而言，這提供競賽公平性的基準。但這個時間限制沒有「理論上的定義」，端看裁判主機端執行的時間而定。這缺乏了一點美感。
另外就是題目取向，Project Euler 的題目有時會需要一點數學知識，而一般程式競賽有時則是要一點演算法上的知識。而 Project Euler 容許的執行時間往往比較長一點。
總之，雖然都是程式挑戰題，但是風格和取向各有不同。
另外一種類型是 Code Golf，著重在用最短短的程式碼達成指定的功能，就像是打高爾夫一樣，你想要用最少的桿數完成比賽。雖然也是程式解題競賽，但又另有一番風格。
當然，寫程式的目的在於寫出「真正有用」的東西，而不是解答這些問題來炫耀自己有多強。但是，不管是哪一種風格的程式解題競賽，在你解題的過程，都能增進自己的程式設計能力。比方 Code Golf 裡面，有些解答是不可思議的短，在你追求這個目標的同時，才發現原來有些語言特性是自己之前忽略的，某種問題原來還有這種寫法。
(對 Project Euler 有興趣的朋友，可能也會對 IBM 的 Ponder This 有興趣。)

Read More