Back of the envelope.

Was reading Jon Bentley Programming Perls (second edition) [1] and  I don’t feel particularly good confessing that I had not read this book before.  It has lots of really nice programming tidbits that can be very helpful in the day-2-day.  The book is a compilation of columns that appeared in one of the ACMs publications.  Therefore it is organized in chapters that directly reflect the columns that appeared in the ACM.

I received an activity for the class that I will TA this semester.  The activity is centered in one of the chapters of Programming Perls: Back of the envelope calculations (BOEC).  In general these are quick processes that do not have to be exact and are made to make decision about a certain process.  Jon Bentley has really nice examples of situations were he has used back of the envelope calculations.  These examples are taken from real life situations that prove their importance.

The activity [2] that was given to me contains two main points: I assume that the first is intended as a warm-up activity that will lead into the second part; the second is made up of 3 curious exercises that taught me the importance of BOEC.  I basically ignored the first part and concentrated my efforts in the second section.  The first two I did in about 15 mins.  I did the calculations in my notebook and modified the values a little to make the calculations easier.  So if I had to divide by 3600, I chose to divide by 3000 (I’m lazy).  After digesting the results a little and double checking them, I continued and calculated everything with the exact values.  I used the calc command [3].  I then compared the results from my approximate calculations with the “correct” ones.  The “correct” calculations were not 100% correct as one has to assume things like average bike velocity.

What I saw when comparing the approximate value and the “correct” value was that, though they were different, their values fell into the same ball park.  That means that I would have taken the same decision based on the approximate values than on the “correct” values.  the approximate values being much faster to calculate.  In general this is a very good way to give a first tier validation to whatever you are doing.  Not happy with what I learned I coded a little script that shows exactly what I did for the first two exercises [4].

For the third exercise I just created a python script and some C code to get some numbers out.  After running them on my  box I got the following results.

```For PYTHON:
1 addition in 0.00966 secs
1 subtraction in 0.00857 secs
1 division in 0.023 secs
1 multiplication in 0.0089 secs

For C: ran with argument 1000000000
1 addition in 2.62e-9
1 subtraction in 2.64r-9
1 division in 2.64e-9
1 multiplication in 2.62e-9
```

This is a primitive comparison of language performance.  Though this is not intended to be an accurate benchmark for integer operations, It gives us some information:  Like the fact that python will probably run 10e6 times slower than C when operating.  Or that C gets really close to an operation per cycle.  It takes a bit less than the advertised velocity for one core in my box.  And finally, python was much easier to code than C :)

[1] http://www.amazon.co.uk/Programming-Pearls-ACM-Press-Bentley/dp/0201657880/ref=sr_1_1?ie=UTF8&s=books&qid=1283767271&sr=8-1
[2] http://www.itu.dk/people/jogr/classes/SDBS/FALL2010/20100906BackOfTheEnvelopPuzzles.pdf
[3] http://isthe.com/chongo/tech/comp/calc/
[4] http://www.itu.dk/people/jogr/classes/SDBS/FALL2010/20100906botep.sh
[5] http://www.itu.dk/people/jogr/classes/SDBS/FALL2010/20100906operations.c
[6] http://www.itu.dk/people/jogr/classes/SDBS/FALL2010/20100906operations.py
Advertisement

About joelgranados

I'm fascinated with how technology and science impact our reality and am drawn to leverage them in order to increase the potential of human activity.
This entry was posted in PhD. Bookmark the permalink.