Tuesday, May 15, 2012

Nostalgia



Long ago I used to program 'C'. I loved it. In those days, access to the net was restricted to a 30 minute session once a week. There used to be a 'superfast' 14400 baud US Robotics modem connected to a DOS PC in our collage library. We had to pay for the access. I used to spend those 30 minutes downloading stuff at optimal speeds for later consumption. Either I used to download code snippets from ftp servers and boards or some random Anarchist documents or I used to be downloading images of angels compressed in this magical format called JPEG. These were so much better and smaller than the prevalent GIF files at that time. 16 million colours as opposed to 256 and that too at 1/5 the size !!

I taught myself 'C' programing using 'Let us C' by Yeshvant Kanhetkar. I also loved the book 'Programing in ANSI C' by Ram Kumar and Rakesh Agarwal. DOS 6.2 was an awesome OS to play with. You could do anything you wanted. :) I wrote a couple of interesting TSR's and a system information utility which gave complete information about your hardware. I also wrote a graphical copy program. The inspiration was the hours we spent transferring bootleg material around on floppies and waiting for them to get copied not knowing how much % was remaining or which files were written on bad sectors. We could skip files which gave the dreaded Abort, Retry, Fail? error.

One of the most amazing and inspirational 'C' programs I came across was from the The International Obfuscated C Code Contest (IOCCC). The program calculated a factorial of any large number. I have let it run for about 30 minutes on my 386 watching the endless stream of numbers. It is written by one Michael Savastio and the source code is beautiful and can be found here (savastio.c)

'Nuff of the nostalgia :)

Sunday, August 23, 2009

How to solve it.

One of the books, which Alok Tiwari, a friend of mine from the old time, had suggested I read was 'How to Solve it' by G Polya. I remember being enthralled reading it. It, with Euclid's 'Elements', are the two books which have had the most impact on my method of thought.

I made a quick set of slides for sharing the salient points of that book with a few friends. The book itself is written in 1945 but still is a very inspiring read.

Wikipedia article about him says that he was born in Budapest, Hungary and that he was a professor of mathematics from 1914 to 1940 at ETH Zürich in Switzerland and from 1940 to 1953 at Stanford University carrying on as Stanford Professor Emeritus the rest of his life and career. He wrote four books on the subject: How to Solve It, Mathematical Discovery: On Understanding, Learning, and Teaching Problem Solving; Mathematics and Plausible Reasoning Volume I: Induction and Analogy in Mathematics, and Mathematics and Plausible Reasoning Volume II: Patterns of Plausible Reasoning.

Some of his quotes are :
"To be a good mathematician, or a good gambler, or good at anything, you must be a good guesser."

"A Great discovery solves a great problem but there is a grain of discovery in the solution of any problem. Your problem may be modest; but if it challenges your curiosity and brings into play your inventive faculties, and if you solve it by your own means, you may experience the tension and enjoy the triumph of discovery"

"To conjecture and not to test is the mark of a savage."



How To Solve It - Presentation Transcript
  1. How to Solve It
    * Completely based on the seminal work of G Polya.
  2. Trying to find / understand not only the solution of some problem, but also the motives and procedures of the solution.
  3. Four Phases
    * Understanding the Problem
    * To make a plan towards the Solution
    * Carry out the Plan
    * Look back and analyze the Solution
  4. Understanding the Problem
    * what is the unknown
    * what are the data
    * what are the conditions
    * consider all parts from different angles
    * draw figures
    * introduce suitable notation whenever necessary
  5. Example : Find length of the diagonal of the Parallelepiped when the length of the sides are known.
  6. Devising the Plan To have (at least) an outline of the procedure to obtain the solution or the computation / calculation required to do so
  7. “In fact, the main achievement in the solution of a problem is to conceive the idea of a plan.”
  8. “ ... it may be hard to have a good idea if we have little knowledge of the subject, and impossible to have it if we have no knowledge.”
  9. Good ideas are based on past experience and formerly acquired knowledge.
  10. Devising a Plan
    * Do you know a related problem ?
    * Do you know a problem with a similar unknown ?
    * Can you restate the problem ?
    * Can you transform the problem ?
  11. back to example
    * what similar problem do you know of ?
    * right angled triangle ?
    * can you introduce an auxiliary element ?
  12. * y^2 = a^2 + b^2 (Pythagorus theorem)
    * x^2 = c^2 + y^2
    * x^2 = c^2 + a^2 + b^2
    * x = sqrt (c^2 + a^2 + b^2)
  13. Look Back
    * Can you check the result ?
    * Can you check the argument ?
    * Can you arrive at the result differently ?
    * Have you used all required data ?
    * Can you reduce the problem ?
  14. Summarizing the procedure ...
  15. Getting Acquainted: Where should I start ? Problem Statement !!
  16. Getting Acquainted: What can I do ?? Visualize the problem as a whole and as vividly and clearly as you can (ignoring the details).
  17. Getting Acquainted: What can I gain by doing so ?? Familiarity with the problem and its purpose. All relevant points will become more accessible and stimulate your thinking.
  18. Towards Better Understanding: Where should I start ?? Digest the problem statement !
  19. Towards Better Understanding: What can I do ?? Isolate the principle parts of your problem. The ‘hypothesis’ and the ‘conclusion’ are the principle parts of a ‘problem to prove’. The ‘unknown’ and ‘data’ are principle parts of a ‘problem to solve’
  20. Towards Better Understanding: What can I gain by doing so ?? Clarify details which are likely to play a role in the ‘plan’ towards the solution.
  21. Ideation !: Where should I start ?? your now complete understanding of the problem statement.
  22. Ideation !: What can I do ?? Consider the problem from various angles seeking contact with your formerly acquired knowledge. Scrutinize all aspects from this context.
  23. Ideation !: What can I gain by doing so ?? More and more ideas will make your conception of the problem more coherent and better balanced. Path towards the end solution will become clearer with ideas giving the intermediate steps.
  24. Carrying out the Plan: What can I do ?? Deal with all the details. Convince yourself of the correctness of each step.
  25. Carrying out the Plan: What should be the result ?? A presentation / implementation of the solution each step of which is correct beyond doubt.
  26. Looking Back: What can I do ?? Consider the completed solution and try to simplify. Try to fit parts into patterns from your previously acquired knowledge. Scrutinize the result and see if you could arrive at it differently.
  27. Looking Back: What can I gain by doing so ?? Maybe a better solution. New and interesting sub-results or facts. Scrutiny of the method of solution will help develop the ability to solve problems.
  28. A short Dictionary of Heuristics.
  29. Analogy: Can you find a problem analogous to your problem and solve it ? Map
  30. Auxiliary Elements: Can you add some new elements to your problem to get closer to a solution ? Extension
  31. Decomposing and Recombining: Can you decompose the problem and “recombine its elements in a new manner” ? Divide and Conquer
  32. Definition: Is your definition of the concepts involved precise ? Exactness
  33. Figures and Diagrams: Can you draw a picture of the problem ? Diagrammatic reasoning
  34. Working Backwards: Can you start with the goal and work backwards to something you already know ? Backward chaining
  35. Generalization: Can you find a problem more general than your problem ?
  36. Specialization: Can you find a problem more specialized ?
  37. Notation: Can you introduce suitable notation to abstract and simplify the problem space ?
  38. thank you for the patience !

Wednesday, August 19, 2009

Wednesday, April 15, 2009

About paradigms and their importance...

Mahavir, Badami
Mahavir and Nirvana, Badami


A multi-paradigm programming language is a programming language that supports more than one programming paradigm. As Lead designer Tim Budd holds it: The idea of a multiparadigm language is to provide a framework in which programmers can work in a variety of styles, freely intermixing constructs from different paradigms. The design goal of such languages is to allow programmers to use the best tool for a job, admitting that no one paradigm solves all problems in the easiest or most efficient way. ~ from Wikipedia

I was just reading this blog post by my friend Sandeep Procedural Programming is NOT a Bad Thing! and just thought I had to add some of my own blab ...

I think rather than what features a language or paradigm provides, it is more important to ask oneself how many of these problem solving tricks/ techniques / methods one really knows and can call to aid. Understanding a certain paradigms enough to start fashioning solutions around it is non trivial. Knowing several paradigms should help open a world of different techniques of problem conquest. Any reasonably sized software would have you contemplate deep and hard on the problem space and probable techniques. Most likely, new techniques and paradigms will have to be acquired.

The tools we know of mould the way in which we approach problems. As a C programmer, say, what I can think of are data, locations of data, manipulation of this data in some conditional or iterative way. I would see clear steps and their impact on performance. As a schemer perhaps, I could see abstractions which might help me solve larger problems with less effort at the cost of seeing immediate impact on performance. For example quoting from SICP where the author is explaining about 'concepts' and 'abstractions' - "Similarly, as program designers, we would like our language to be powerful enough so that we can write a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums."

The key to program design and problem solutions is our ability to see these 'abstractions' and hence reduce problem space and complexity repeatedly till we have managed to 'solve' it sufficiently.

Certain vagueness or misdirections occurs when people give (or understand) only part of the reasons why they propound a particular paradigm strongly. For example, the Java people build a engineering platform which could scale to handle large complexity and resources and also help management of the whole thing. Large companies with extremely large code bases and with large programmer base have, as an element of the problem space, issues regarding code integrity, collaborative maximal exclusion coding. The issues and hence the design patterns which addresses these issues are specific to such systems. A Linus working on GIT is a different proposition. So Java is not necessarily a very elegant medium of expression of ideas but it is an excellent platform for the management of larger code bases and systems.

One has to choose a platform which will give him access to all the paradigms which his problem space may need to reach a good solution. So the key to a good platform for the creative types and people not encumbered with people problems, turns out to be the flexibility of the platform in providing the programmer a free space where a solution could be designed which merits the problem without being restrained or constrained by any particular paradigm or method of work. Ruby and Python are becoming more popular due to the flexibility and the expressiveness they provide, which I will call the elegance factor, which earlier was underrated.

Me, I program in Common Lisp. It is Nirvana for the programmer. The path to Niravana is always tough. But what you can do with such tools is what makes work pleasure.

Saturday, March 21, 2009

Some common Hash Functions in Common Lisp

Here are some common hash functions in C I found online here and here. I have done the menial task of translating them to CL. I have a lot of excuses for such a lame post : blah blah blah. I made a big booper by forgetting that these functions return unsigned-byte 32 ints. After some simple pointing to this by good denizens of #lisp I changed it - that too after reading some literature. duh. If you have any suggestions how daft I am, lemme know.

;;; Hash Function by Dan Bernstein
(defun hash-DJB (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381)) 
    (loop for x across str
     do (setf hash (ldb (byte 32 0) (+ (ldb (byte 32 0) (+ (ldb (byte 32 0) (ash hash 5)) hash)) (char-int x))))
     finally (return hash))))

;;; Hash Function by Dan Bernstein (newer)
(defun hash-DJB2 (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 5381)) 
    (loop for x across str
       do (setf hash (ldb (byte 32 0) (logxor (char-int x) (* hash 33))))
       finally (return hash))))

;;; Hash Function from GAWK, a variation from the verwion from SDBM 
(defun hash-SDBM (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
  (let ((hash 0))
    (loop for x across str
       do (setf hash (ldb (byte 32 0) (+ (char-int x) (ldb (byte 32 0) (ash hash 6)) (ldb (byte 32 0) (ash hash 16)) (- hash))))
       finally (return hash))))

;;; An algorithm proposed by Donald E. Knuth in The Art Of Computer Programming Volume 3
(defun hash-DEK (str)
  (declare (type simple-string str)
    (type (unsigned-byte 32) hash)
    (optimize speed (debug 0)))
    (let ((hash (length str))) 
      (loop for x across str
  do (setf hash (ldb (byte 32 0) (logxor (char-int x) (logxor (ldb (byte 32 0) (ash hash 5)) (ash hash -27)))))
  finally (return hash))))