Thursday, December 28, 2006

Quote of the Day

The creation of standardized, vendor-independent operating systems, such as UNIX and its clone, Linux, lowered the cost and risk of bringing out a new architecture

David Patterson and John Hennessey

Monday, December 25, 2006

A shortcut through time

Written by science writer George Johnson, this book talks about mans quest for the ultimate computing machine, the Quantum Computer.


The books begins with the basic of computing, the language used is quite amusing

"In a typical circuit, there were resistors that, true to their calling, resisted electricity, pinching the flow of electricity"

The book starts off with the authors experience with GENIAC, a mock clone of ENIAC. The author then explains, tinkertoy logic, the book helps the reader discover that computers are more about logic, more than semiconductors that are used to build them. Logic is more important than how it's actually implemented.

The book then dwells into physics, explaining how atoms spin, and how depending on the direction of spin, we can treat the spinning as a boolean quantity as 1, 0 or Φ. Φ represents the state of the atom, when it is spinning in both directions simultaneously.


The introduction to Quantum physics makes a good read and makes me wonder why I slept through Physics in school. Reading further through the book the author aptly states "Human brains are just not equipped to intuitively understand the subatomic rules". The author then takes you to the Aha! Moment, when you realize that the Quantum Computer is so powerful that it can carry out 2n computations simultaneously, where n is the number of computing bits.

The book then introduces the layman to the Turing Machine and computational complexity, followed by Cellular Automata, Shor's Factoring Algorithm and its application to the world of Quantum Computing. No mathematical proofs are included in the book, but the concepts are well illustrated with examples and supporting diagrams.

Cryptography is then introduced along with the challenge of decrypting code, the computational complexity of cryptanalysis and implications of a quantum computer on current security technology is discussed.

What follows is an elegant description of logic gates and reversible logic. The current and state of the art attempts made at building a quantum computer are described in detail. Quantum error correction, its need and challenges is also discussed.

The book closes with chapters on Quantum secrecy and describes how polarized photons are used to implement quantum cryptography. Real life examples of hard problems, like protein folding is discussed. The reader is introduced to the fact that protein folding is a hard problem to solve (see books on NP-Hard) and the mystery surrounding how nature is able to solve the problem so quickly is discussed.

In summary, this is a great book to read. If you know and understand computer science, it will expose you to how, some of the most complicated concepts can explained without the need for complex mathematics. If you do not understand Quantum computing, the concepts exposed will get you interested in the world of Quantum, where the laws of nature are different. Simple Newtonian physics cannot explain what goes on inside an atom. It is this randomness and uncertainty that can change the way we compute today.

Friday, December 01, 2006

Just my lucky day! (errata in The METAFONTbook)

I got this email as a reply for an errata report I sent out

thanks for your report.

I hope I am emailing the correct people for an errata I found in The MetaFont book Volume C, Page 159

yes. you've come to the right place.

Original Text

For example, Appendix B says

def --- = .. tension infinity.. enddef .

Corrected Text (It should be)

For example, Appendix B says

def --- = .. tension infinity .. enddef;

(Note the change from . to ;)

i've verified this; the reference in appendix b
is on p.262. i don't see any earlier reports on
this, so it looks like you're the first.

should this actually be the case, you will be due
a small reward. to deliver it, we'll need a
postal address. i've received word from knuth
that he expects to be looking at reports about
this time next year, so an address that will be
current at that time is what we'll need.
-- bb

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...