I've Just Learned About Bloom Filter

Although the algorithm was invented at about the same time that I was born, I've just understood how Bloom filter works today :-)

From Wikipedia page, the Bloom filter "is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positives are possible, but false negatives are not. Elements can be added to the set, but not removed (though this can be addressed with a counting filter). The more elements that are added to the set, the larger the probability of false positives."

Here's a discussion about a 22-line Python implementation of the filter.

TestDisk & PhotoRec: Rescuing Deleted Files On Windows, Linux, Mac OS X, And Other OS's

TestDisk is a free (open source) software that let you recovered deleted partitions and files on most major operating systems easily. I've used it successfully on Windows, Linux, and Mac OS X on various occasions. So, if you unintentionally delete your files you might want to try it.

For deleted files on digital camera memory, TestDisk has a companion program called PhotoRec that recovers pictures and videos from the various media such hard disks, DVD, CD, memory cards, and thumb drives. Here's a step-by-step guide on how to use it.

Finding Links You Shared On Facebook

I've shared a lot of links on Facebook and occasionally people would ask me about an old link that I've already forgotten. I don't know of a way to easily find those links but last week someone introduced me to trunk.ly, a search engine for the links I shared on Facebook and Twitter. It has done a good job of listing and searching the links that I've recently shared. So, if you want to keep track of the links you share, you might find trunk.ly useful.

By the way, my list of links at trunk.ly is at http://trunk.ly/psaipetc/ and all the links I've shared on Facebook is at http://www.facebook.com/posted.php?id=552001173

md5 On Mac OS X ~ md5sum On Linux

{Summary: Mac OS X's md5 command is analogous to Linux's md5sum. openssl can calculate many types of digests for you.}

This entry is a note to myself so that I won't repeat the same mistake again since I have done so at least twice already.

I had to transfer quite a big file from Mac OS X to a Linux server using sFTP. The session was interrupted a few times and I wanted to make sure that the file on the server was not corrupted. So I went ahead to calculate the message digest (MD5) of the file on the server and the original file on the Mac.

I typed md5sum filename on Linux and got the message digest with no problem. When I typed md5sum filename on Mac, the computer said the command was not found. So I googled for "md5sum mac os x" and the links on the first page seemed to say that md5sum should already be on my Mac.

So I typed "man md5sum" and the computer said there was no manual for the command md5sum. I then tried "man md5" and got the manual for the command md5 that would calculate the MD5 message digest just as I needed and I went ahead and used the md5 command.

After I verified that the uploaded file was not corrupted, I realized that I had done these steps before but have forgotten about it all. I looked at the files on the Linux servers and I saw a few big files that I calculated the MD5 message digests when I uploaded them. So, I must have forgotten all about the steps that led me to use md5 before and hence this note.

BTW, MD5 message digest is no longer considered secure enough for serious work and SHA1 or better digests should be used instead. To find SHA1 on Linux, use sha1sum filename. To find SHA1 on a Mac, use "openssl sha1 filename" or "openssl dgst -sha1 filename". To find SHA256 on a Mac, use "openssl dgst -sha256 filename".

If you want to calculate message digests on multiple files inside directories, you can use md5deep which calculate MD5, SHA1, SHA256, and other digests for you.

How Adsense Was Born

I stumbled on this interesting account of how Google's ubiquitous Adsense (the ads from Google that you see everywhere) was born. Humans are not smart enough to predict most things, so one way to see if anything works is to actually make a prototype and see.

I Learned Something New Today: Automatic Differentiation

After 28 years of (amateurishly and rather clumsily) programming computers and 25 years of using calculus, I just found out about a method to calculate numerical derivatives exactly (up to numerical accuracy.)

I knew how to do numerical differentiation based on approximating derivatives with finite differences which incurs inexactness due to truncating infinite series, but I never thought about how to get exact numerical results. Luckily someone else did, and we got the automatic differentiation technique.

A Mathematical Attack On Copyright

The OFF system is a way to circumvent copyright entirely. It does this by representing any copyright data as a series of meaningless numbers distributed over many computers. Each number does not appear in the original data, but when combined with other meaningless numbers will produce the original data. Weird, but true, and easily understandable once you read the introduction.

The interesting except:

Are these numbers copyrighted? Could they be stored on two separate computers? Would that break the law? What if they were never added together? Would their existence still break the law? What if I give you two other numbers? Again, and again…

It turns out these are not philosophical nor legal questions, but purely mathematical ones. There are two consistent ways to answer the above questions. One leads to the conclusion that “All numbers are already copyrighted.” The other leads to the conclusion that, “There exists encodings of copyrighted numbers that are NOT copyrighted.”

If the first conclusion is true, digital copyright is pointless. If the second is true digital copyright is meaningless.

Useful Unicode Information For Thai Language

I needed to convert a bunch of files saved in a few Unicode encodings and I found the Unicode table for you, Unicode HOWTO (for Python), and Ascii Table MS-DOS Codepage 874 (Thai) pages very useful. I'm writing this down in case someone needs to do similar things for Thai files.

How They Built Apollo 11's Software

Wow. Full story here. You can also run a simulation of the Apollo computers here.

An excerpt from the story:

During the Apollo 11 Lunar Module’s descent to the Moon 40 years ago today, Garman played a direct role in preventing a mission abort. Several warning lights and computer overload alarms came on as the craft descended just above the Moon’s surface, causing worry in Mission Control, but all of Garman’s pre-flight simulation experiences told him that the alarms were not critical and the landing could continue. Without hesitating, and without panicking, the 24-year-old NASA computer engineer confidently gave the “go” to continue the mission.

Granville Paules, was a 32-year-old guidance officer for one of the Apollo 11 mission teams and remembers that moment well.

“The alarms went off on during descent,” Paules said. “It was a conflict between the on-board systems and the computer was starting to get overloaded. Garman had a simulation where a similar thing had occurred about three weeks before that, so he knew what to do. It probably would have been a lot scarier, possibly even an abort for the landing, if we had not had that simulation. I can say that the odds of aborting that lunar landing were a lot higher than people want to believe. That simulation gave everybody the confidence to turn off the alarm and ignore it.”

Useful Python Notes

I learn a few useful things from C. Titus Brown's class handouts for "Intermediate and Advanced Software Carpentry in Python." I especially like idiomatic Python sections.

Dr. C. Titus Brown is currently at Michigan State University's Laboratory of Genomics, Evolution, and Development.

If Skynet Wants to Compile a Program, It'll Probably Use a Descendent of This Compiler

"Our technology automatically learns how to get the best performance from the hardware -- whether mobile phones, desktops, or entire systems -- the software will run faster and use less energy," noted Dr. Bilha Mendelson, Manager of Code Optimization Technologies at IBM Research - Haifa. "We opened the compiler environment so it can access artificial intelligence and machine learning guidance to automatically determine exactly what specific optimizations should be used and when to apply them to ramp-up performance."

The compiler can be found here. It's open source.

A Good Essay From The Past

I first read the essay by Danny Hillis about Richard Feynman and the Connection Machine about two decades ago and by chance read it again today. I still like it very much.

An Excerpt:

...For Richard, figuring out these problems was a kind of a game. He always started by asking very basic questions like, "What is the simplest example?" or "How can you tell if the answer is right?" He asked questions until he reduced the problem to some essential puzzle that he thought he would be able to solve. Then he would set to work, scribbling on a pad of paper and staring at the results. While he was in the middle of this kind of puzzle solving he was impossible to interrupt. "Don't bug me. I'm busy," he would say without even looking up. Eventually he would either decide the problem was too hard (in which case he lost interest), or he would find a solution (in which case he spent the next day or two explaining it to anyone who listened). In this way he worked on problems in database searches, geophysical modeling, protein folding, analyzing images, and reading insurance forms...

If you like science, or want to have a glimpse of how one of the finest minds of our species operated, you might want to check it out.

Skynet* Is Coming!

Really, look at this A.I. and tell me you are not impressed.

I asked START, "Who is Norah Jones?", and it got info from Wikipedia and Biography.com in a good short summary. By the way, do you know that Norah Jones' full name is Geethali Norah Jones Shankar?

It knows answers to a lot of questions, such as "Why is the sky blue?", "Where is the deepest spot on Earth?", "What is a Terminator?", and "What is staccato?" However, when I asked "Who created Skynet?", it said "Sorry, I don't have this information."

*Skynet is the A.I. that decimated the human population in Terminator movies and series.

If Programming Languages Were Religions...

I stumbled upon an amusing essay called "If programming languages were religions..."

It's doubly amusing that my programming language of choice (Python) and my life philosophy (Humanism) match in the comparison.

Historically I went through Satanism (Basic) to Judaism (C) to Islam (C++) to Voodoo (Perl) to Humanism (Python.)  I'm also curious about Zen Buddhism (Lisp), Taoism (Haskell), and Hinduism (Erlang) but haven't learned much about them.

Frequently Forgotten Fundamental Facts about Software Engineering

Robert L. Glass, a noted software engineer, provides us with a great list of Frequently Forgotten Fundamental Facts about Software Engineering. If your work is related to software production in anyway, you should really take a look. Sometimes people lose sight of the true nature of software development and make tremendously stupid decisions--by being aware of the list, our chance of being a butthead should decrease.

The list was fleshed out into a book called Facts and Fallacies of Software Engineering. I enjoyed the book immensely and you might like it too.

Top 10 Bugs

Whenever I have a stupid bug in my programming, I would console myself by saying "Well, at least I didn't kill anybody."  Not all programmers can say the same though.  Welcome to History's Worst Software Bugs page at Wired.com.

(Technically, the 1982 Soviet gas pipeline "bug" worked exactly as the designers intended, so I don't think it's a bug at all.)

What Is "Load Average" In Top's Output Anyway?

When I started using Unix in 1989, I learned about the "top" command to see how hard the computer was working. There are many numbers in top's output. Some (such as time, uptime, number of users, CPU states, etc.) are easy to understand. However, I never really understood what "load average" means.

Of course, if the computer is doing nothing, the load average would be low, and if the computer is busy, the load average will be large. However, the number can go much higher than 1, so it's not the fraction of the computer's capacity that is being used. I was never curious enough to find out exactly what that number means, and just settled for general feeling of typical numbers that would be "safe" for each computer.

Now, thanks to the magic of the Internet, the exact meaning can easily be found here and here. (Yes, it's easily found, but to really understand it, you need to read till the end.)

To summarize:

So, what have we learned? Those three innocuous looking numbers in the LA triplet have a surprising amount of depth behind them.

The triplet is intended to provide you with some kind of information about how much work has been done on the system in the recent past (1 minute), the past (5 minutes) and the distant past (15 minutes).

and

Those three little numbers tucked away innocently in certain UNIX commands are not so trivial after all. The first point is that load in this context refers to run-queue length (i.e., the sum of the number of processes waiting in the run-queue plus the number currently executing). Therefore, the number is absolute (not relative) and thus it can be unbounded; unlike utilization (AKA ``load'' in queueing theory parlence).

How Software Companies Die

Orson Scott Card, one of the great sci-fi writers, the author of Ender's Game and Speaker for the Dead, wrote a pithy essay about How Software Companies Die. It's funny (and sad), and true.

Progress Bars To Make People Happier

Chris Harrison et al. has a paper showing that people perceive time as running faster if they are looking at an appropriately accelerating progress bar. It seems that a progress bar that slows in the beginning and accelerates near the end (called "Fast Power" in the paper) makes people happiest. The study focused on the duration of 5.5 seconds and suggested that other longer durations should be further investigated.

I never asked myself how a progress bar should move to please people. I'm glad there are people like Chris who thinks of these things. He also has a lot of interesting projects here.

On a slightly related news, here's an article about how to slow your perception of time.

Applied Probability: How To Write A Spelling Corrector In 21 Lines Of Python

Once again Bayes' Theorem comes in handy. This time, Peter Norvig shows us how to make a not-so-bad spelling corrector. It was done in 21 lines of easy-to-understand Python! I actually could understand it in one pass of reading. (It usually takes me many reading passes to understand any algorithm--I'm dense that way.)

If you have children, they should have some basic math and probability skills. Rational thoughts need those skills. Otherwise, they won't be able to make quantitative comparisons.