Alecs' Blog

More puzzles, more fun.

Besides acm oj and projecteuler, i also like to solve the puzzles on spoj. The ACM/ICPC rules are rather limited -- you have to submit the src code (only one file) in java or c/c++. ProjectEuler is much more free: it just accepts the final answer -- you are free to use any tools/langs as you like. Spoj stands kinda in between: it still accepts a one-file-src but you can use a lot of languages (just to name a few: bash, perl, lua, lisp, python, haskell, c, asm, etc.). In other words, it's hard to not to find your favorite language there. But you cannot use any external src or libs (only standard feature or lib of the langauge is allowed).

Among many interesteting puzzles, spoj has some challenge problems. These problems are not simply checked right-or-wrong. Instead it makes the rank based on its problem-specific scoring: usually precision, sometimes code-length. Take the following three for example:

• Digits of e
• Digits of sqrt(2)
• Digits of pi

The rules are same: given limited time and code-length, calculate the value in as many decimal digits as possible.

All three problems involve arbitrary-precision computations -- you either implement your own FFT or use those languages that have bignum built in (like java, python or haskell).

• Digits of e -- just use the Taylor expansion with Binary-Splitting.
• Digits of sqrt(2) -- Newton iteration (note that each iteration doubles the precision).
• Digits of pi -- use Chudnovsky series with Binary-Splitting.

For the underlying magic algorithms, see the those wonderful papers/docs. Here's a reference implementation for pi digits using gmp -- claims to be the world's fastest -- for as many as billion digits. Also, mpmath has some interesting implementations as well.

I myself dont bother to implement a FFT in c/c++ (and i doubt i could write a fast enough version in 4K code). Python is really slow for this (sorry, sad, but true) . Haskell's Integer is using the fast(est) gmp. Not only it's fast, it's very convenient and leads to (much) shorter and cleaner code. You can see the ranks. Also specific ranks in your favorite languages.

Other interesting ones might be:

• Make the src as short as possible. Perl is the ruler for this. But you can try to be the top 1 on a specific language ranking.
• Compress and uncompress in one file. The hard part is how to dump the compressed data in src file.
• Magic Markov. Write code to generate code, with special craft.

I've listed some math tools and libraries before. A lot of math tools have their own DSL (domain-specific language) for quick & easy access to their various math functions with some primitive control flows. DSL is better in the sense that it's relatively convenient and it gets hooked more tightly to the underlying base (i.e. shorter code, more inner-involving). A general programming language has its own strength: it's powerful, elegant, much more mature and more easy to access the 'outer' world. DSL for the math tools (like the 3 big Ms) sometimes looks kinda awkward from a 'programming' point of view. Besides, people tend to like doing work in their own favorite languages.

Python is rather popular nowadays. It's been used in various fields -- sys admin, net utility, web, prototyping, unit testing, etc. -- and of course, in mathematics, science, and engineering. One of the well-known tool chains is: scipy + numpy + matplotlib + ipython aka the PyLab. scipy/numpy is tremendously good for numeric computation and matplotlib can generate high-quality 2D plots -- in your favorite language.

Another tool chain i'd like to share is for symbolic manipulation: gmpy + mpmath + sympy. gmpy provides the python binding for gmp, mpmath provides some high-level arbitrary-precision computing functions while sympy is really good at symbolic processing with great 2D/3D plotting support and a convenient interactive 'isympy'. Your distro may have these pkgs but please check if they are outdated. I recommend you use the latest version built from their own repos. (sympy has included mpmath, btw). Newer versions are way faster -- Try calculating 1M digits of Pi.

And here's a big all-in-one math tool called sage, which is using python as the primary programming language and can be regarded as a free alternative to the 3 big Ms.

Also, two tools not specifically for math: psyco and parallel python (via bones). psyco is kind of a python JIT. If you do a lot of cpu-bound instructions in python, it is your lovely friend. pp is for parallel computing (multi-core or even network cluster). It can split computation at the function level.

Finally, for speed-lovers, there's a language called wirbel. It has very similar syntax to python (almost equal). The key difference is that it can compile src to native bin, thus it's very fast. But limited: not all python code can be easily changed and compiled by it of course, at least not now. Still an interesting alternative anyway. You might want to have a look.

Installing linux is much more easier these days. LiveCD is now becoming a de facto standard. Some distro even provides a LiveUSB. If not, here's a great tool that can help you make a liveusb from a livecd image, automatically: unetbootin.

Besides the usblive feature, it also supports install-from-net, install-from-windoze, install-from-disk, etc. If you like to try installing different distros and dont have a CD drive (or dont like to burn CDs), unetbootin is your friend.

Big distros nowadays are all trying hard to make the booting fast: kernel-mode-setting, init-ng, readahead, parallel loading, etc. Here's a great tool that can monitor and visualize the booting process: bootchart. I upgraded to Intrepid weeks ago. And here's a bootchart shot.

35 seconds: a cold start, from boot to xorg/gdm running with all common services and wireless network up. I'm very pleased with this, considering its a ubuntu default kernel, default initrd with default settings. If you customize your kernel building all needed drivers in with no module or initrd, and use a slimmed down DE/WM without many startup services, it may reduce about 10 seconds i guess.

And speaking of wireless network, i've been using network-manager for a long time (since edgy?) It works fine (well, though not as half good as AirPort). But not for me in intrepid. Authentication goes well but it fails requesting an ip address. I dunno why. Maybe the kernel, the iwl driver, the wireless router or the nm itself. Dont bother to figure it out or use the cmd line (iwconfig, wpa_supplicant, etc.). Bad me, I am a typical desktop linux user now. Here's a replacement: wicd. It works well. No bloat. Kool.

And finally, here's a tool called smolt which can gather your hardware information and submit it to its central database. You can see some stats and devices information. Maybe not directly good for you but it helps the community in the long run.

Cabal is a system for building and packaging Haskell libraries and programs. Put it another way: its Setup.lhs is like Makefile.pl for perl or setup.py for python. Well, you've got the idea. See the user guide for details.

And cabal-install is like perl's cpan (the command) which can automatically download/install/update haskell package off from Hackages. It's still a work in process. Occasionally it cant resolve the dep right or miss out one or two packages. You might have to manually install them. So be warned.

BTW, I dont think many ppl are still using the 'cpan' cmd to install perl modules these days. At least not for most linux distros. CPAN perl modules are very mature and most distro vendors have made their own pkg/ports already for you. But not for haskell, because far few ppl are using/developing haskell pkg. Either there are no pkg built or if there is, the pkg is usually outdated. So if you need to install cutting-edge haskell pkg, i recommend cabal-install. I used it to install lambdabot. Almost went fine except a dead dep loop. Manually fixed it anyway.

Solving project euler problems continued to be fun. Now i have solved 200 out of 213 problems. There have been some relatively easier ones recently added as well as some hard-and-fun ones. Just to name a few:

• laser beam reflecting on mirrors
• paranoid flea jumping on a chess board
• secret ambiguous numbers

And as always, i like to use haskell to solve them if possible. And the more you use haskell the more you love it. Here are some (new) haskell resources:

• Learn You a Haskell, great tutorial, very enjoyable.
• Real World Haskell, soon to be published by O'Reilly.

Two search engines for haskell (API, library, types, etc.):

• Hoogle, Haskell's Google
• Hayoo!, Haskell's Yahoo! 2.0

I've been using awn for quite a while. It's normally ok but sometimes it just has one glitch or another: not very stable. Also the feel is not quite like Mac's Dock. Now here's a new one: Cairo Dock. It looks great and feels snappy. The icon magnification is just neat.

And for the input method, i got fed up with scim and its crappy dict. Now i start using ibus. It's written by the same author of scim-python. It looks very promising (Dbus based, native theme, etc.) and hopefully has a bright future (i guess). You can give it a try.

Call me old school. I like apache + plain cgi.

Export old entries from mt3, install brand new MT4, and import back. Sweet. Smooth. Slick.

MT4 has markdown builtin by default so all my entries are rendered with no problem at all. The new interface is modern and user-friendly, yet still quick and powerful. Time to dig out more and hopefully to write more.

It just works.

I dont digg, i reddit.

Information-exploding century. Tens of feeds. Hundreds of entries. You might have wasted too much time on reading blog/rss/feeds.

Normally, the more feeds you subscribe to, the less percentage of useful entries. I read proggit and YC everyday. There are hundreds of updates everyday but only very few is interesting to me. The truth is, what remains interesting is really nice. So i dont want to miss those interesting ones while i dont want to waste my time doing the manual filtering either.

So here comes a great tool called aiderss to help you easily locate those 'good' ones without wasting your (precious) time. It adopts a technique called PostRank to score/rank a post. Take proggit for example, you can see all, good, great and best ones all filtered for you. There are respective rss feeds made for you too. And if you use firefox + google reader, there's also an addon.

Oh, lets see Alecs' Blog in the postranked mode.

Less is more
Less is more than more

You may use RSA (or other public key crypt method) every day without even noticing it or actually bothering 'whats under the hood'. But for one day, you might ask, "what's actually under the hood anyway?"

Recently I've been reading a new book about algorithms -- Algorithms. In the Chap 1 Algorithms with numbers, the authors give a very good view of the underlying theory and smoothly outline the elegant algorithm. You never truly understand an algorithm until you get your feet^Whands wet and actually code a working implementation.

So here's a small RSA skeleton implemented in haskell, which contains all bits including: Fermat's testing, getting random large primes, calculating mod inverse (extended-Euclid), the cipher functions and a simple test.

For years, as my fans may^Wshould know, i've been using the fetchmail (POP3) + procmail (filter) + mutt (sucks less) + msmtp (eSMTP) tool chain for emailing. And yes, i use gmail. All is very convenient. For the SMTP part, gmail automatically stores any mail you sent in the 'Sent' folder. As for POP3, it can archive any mail you fetched (you can safely specify 'delete' on the client side). All these are very user-friendly and sweet.

But recently i just found that you cant get (via pop3) mails sent by yourself. This is really annoying for mailing lists (yes, i want to see my mails in the lists). And it turns out that it's a feature, not a bug. Gmail smartly thinks it's a duplicate (ie. same message-id) and ignores it. One workaround is to enable 'recent mode' but that's really awkward. Another option is to use IMAP.