================================================================
C program

Compile with optimization:

    nikhil@whopper>cc -O histogram-int.c

Run it, also timing it:

    nikhil@whopper>time a.out

Cross check:
- answer is correct,
- total time reported by program = total time reported by system (u+s)

Record time for hist() (total time includes tree construction, which
we're not counting in the Id program either).

Note: I also tested it with the Gnu compiler (say gcc instead of cc),
but it runs slower.

----------------------------------------------------------------
This version with integer arithmetic:

File: histogram-int.c

Tree size   Tree size    Run time
(depth      (leaves)      (secs)
---------   --------     --------
  10          1,024         0.00 (below clock resolution)
  15         32,768         0.12
  16         64,536         0.20
  17        131,072         0.40
  18        262,144         0.78
  19        524,293         1.55
  20      1,048,576         3.17

----------------------------------------------------------------
This version with double-precision floating point arithmetic (changed
leaf info to be a double = 1.0, and changed the histogram to be an
array of doubles):

File: histogram-double.c

Tree size   Tree size    Run time
(depth      (leaves)      (secs)
---------   --------     --------
  10          1,024         0.02 (below clock resolution)
  15         32,768         0.18
  16         64,536         0.35
  17        131,072         0.72
  18        262,144         1.43
  19        524,293         2.90
  20      1,048,576         5.95

================================================================