Project Euler Problem 198

Original post in Chinese: 2008/06/project-euler-198.html

Project Euler Problem 198 asek you to find all ambiguous numbers between 0~0.01 with denominator no more than 10^8, where by definition, a real number x ambiguous, if there is at least one denominator bound m for which x possesses two best rational approximations. For example, let x=9/40 and m=6, then 1/5 and 1/4 are both best rational approximation of x with denominator no more than 6. Clearly, an ambiguous number is necessarily rational.
This seems to be difficult if you don't have certain number theory background knowledge. On the other hand, if you do have the certain knowledge, you may think 10^8 is kind of too small for a Euler project problem. IIRC, you can find a nice algorithm in Knuth's The Art of Computer Programming.
However, it is pretty straightforward to solve it by recursion using 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)

As easy as 7 lines of code, yet the code is a pretty straightforward translation of the mathematics behind it. However, using Python to solve it is a totally different story. The above recursion exceeds the limit of numbers of function calls in python. The following is a loop based solution:

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

The code is directly copy from the code I gave on Project Euler website, so it does not look good.
With the help of psyco, it is fairly fast, but is not very readable by human and can not be considered as a straightforward interpretation of the mathematics behind the problem.
On the contrary, doing some easy tasks in Haskell is not so elegant. For example, suppose we want to find the integer part of the square root of an integer n, and then print it on the screen. Doing this task in python is as simple as you can imagine.

print int(x**0.5).

To do this in Haskell, you will have to convert the integer n to a float point number, then take square root, then take floor, then covert it to an integer, and then convert it to a text before it is ready to print on screen.

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

If there are a lot of float point numbers and integers involved, then you probably need to do the coversion every here and there in your code. I know that those conversions exist for a good reason, however, sometimes you just fell like to do a quick and simple computation.
Sure Haskell can make complicate tasks simple and make simple tasks complicate.