fifth in the increasingly insane Computer Science for Smart People course

Today's block of healthy, tasty ASCII text (the stuff you are reading now) concentrates on three objectives:

  1. Maximizing your sense of well being, personal worth and inner glowing happiness.
  2. Making you a better citizen in a complex, occasionally conflictive, but always forward-marching society.
  3. Teaching you how to analize a problem and write the program that solves it.

The problem we set out to solve is the assignment from the last class:

Visualize the relationship between decimal numbers and base two numbers

Notice that the problem (by design) is underspecified. This is not what we can feed to a computer scientist yet. We need to play designer a little bit, and come up with a more precise definition.
In a sense, this whole writeup will be about doing this; refining further and going from vagueness to precision, until it is precise enough for a computer to do it.
The program will be written in Design by Numbers, but I will try to use techniques that can be applied to other languages as well.

Specifying

For no particular reason at all, I don't really feel like drawing figures on screen. This leaves me with the problem of representing graphically the numbers (decimal and binary). Not being a graphic designer, one solution I can come up with is that the decimal numbers will be implicitly represented by some top to down or right to the left order. The binary digits (might as well call them bits and keep things shorter I will quite naturally represent as black or white blocks (or possibly pixels) on the screen.
To make things easier to read, I may try to add some reference marks to the display, in order to make it easier to understand which decimal number are we looking at. Perhaps some sort of mark each ten decimal numbers, and a smaller one each five. Maybe a big one at one hundred.

Refining

At this point, I have a clearer idea of what I set out to do (as expressed in the previous section). I may even write a little piece of pseudocode to clarify it to myself:

add decimal reference marks to the screen
walk down the integer numbers and display the corresponding binary number for each

Now, I refine further the first part.


for each number in the range that I am concerned with
   if it is divisible by 10  then draw a big 2 x 1 reference mark on the side, and paint the background grey
   if it is divisible by 5 then draw a smaller square reference mark and paint the background a lighter grey
   if it is divisible by neither, do nothing at all
   draw a reference line that separates one number from the other

To be a little bit more realistic, I will say that I will work on the range of number from 0 to 69. Why that range? Because I figure that I can dedicate 4 pixels to each number and end up with 200 pixels of vertical bulk, which is not beyond reasonable.
At this point the pseudocode is specific enough to be turned into code. Notice that up to this point, this had absolutely nothing to do with Design by Numbers. I would be going through this same process even if I were planning to do this in C or in Tcl/Tk or in Lingo.


//A program to visualize binary numbers. Written in mostly standard DBN.
//according to a brief given in Listen to Me!.
//Author: baffo
//Started on: 19 11 2001

size 50 210 2                    //undocumented: 2 means fatbits  
set hsize 50                     //I know that I should not need to repeat the numbers, but DBN
set vsize 210                    //does not allow me to use variables in a 'size' statement
set numbersize 3                 
set total (vsize/numbersize)
set tencolor 40                  //these color are reasonable on my LCD screen.
set fivecolor 30
set reflinecolor 80

// Draw reference lines stepped by numbersize
// Not the most efficient method, but it is flexible and compact

repeat n 0 total
{
   set y (n*numbersize)
   set innery (Y + numbersize -1)
   set leftx 0
   pen reflinecolor
   line 0 y hsize y
   same? (n%5)  0
   {                                     //some inefficiency here, but it is not a problem for this size
      set fieldcolor fivecolor
      set leftx numbersize
      same? (n%10) 0
      {
         set fieldcolor tencolor
         set leftx (numbersize *2)             //change this to make ten-marks bigger
      }
      field 0 (y +1) leftx innery reflinecolor
      field leftx (y +1) hsize innery fieldcolor
   }
}

Now, notice that this piece of code is complete in itself. In fact, I could have written this after agreeing with someone else on the piece of pseudocode that I have written above. In this moment, he could be writing on the second part of the problem.
Also, notice that all the numbers that appear in the code as numbers are rather obvious. All the insidious magic numbers are either computed or defined initially in that sequence of set statements. This is to make the code easier to read and to modifiy.
Lastly, notice the copious amount of comments. I know that in two days I will have forgotten why the heck I picked those colors. In one year I will have forgotten that I have written this at all. That's why all code should be dated and signed, and it should come with a revision history.

Now, for the second part of the problem: actually drawing the binary numbers. The pseudocode I had written said:

walk down the integer numbers and display the corresponding binary number for each

To refine it further:


repeat this for every number n in the range
 repeat this for every bit in the binary representation of n
  if the bit is ON draw a black rectangle
  else draw a white square

At this point, the issue of converting a decimal number to binary could face me. Notice that this is not strictly necessary: I can also generate the numbers directly in binary in the right order.
At this point, the right thing to do is NOT TO START CODING like an insane hamster on speed, but rather to wonder:

baffo: (introspectively) my friend, I am sure that this idea of converting decimal to binary has already occurred to somebody else, nay, perhaps to millions of people. Couldn't you save your precious and already scarce neurons and look it up, instead of designing a stupid algorithm to do that? Eh?
baffo: (brightly) wow, that is a rather innovative idea! Actually looking something up! like real scientists do!
baffo: (professorially) not for nothing we are called computer scientists.

By means of a simple search on Everything2 I find a lovely algorithm under decimal to binary. The beauty of it is that a naive algorithm would have required me to generate powers of 2, something that Design by Numbers can do but not very conveniently. I also notice that the algorithm proposed generates the bits from the least significant bit to the most significant bit.
Since my only purpose is generating a display here, I will not store the generated bits anywhere; in some other context, I would probably put the decimal to binary conversion in a function, in order to be able to reuse it.
Notice also that this would require me to solve the problem of returning an unknown number of bits from a function, something that [Design by Numbers|is not able to do. Ugliness would be required.

The algorithm that ariels nicely gives is says: Take your number and repeatedly do an integer division by 2 until you reach a result of 1. The rests are your binary number, in sequence from least significant bit to more significant bit.
This is not entirely trivial. Anyway, onwards to the next chunk of code. Or rather: before writing the next chunk of code, it turns out that I don't know one important thing.
The algorithm gives me the bits from the right to left (that's to say, in the order whose values are 1, 2, 4, 8, 16 ...) and I don't know how many bits I will need until I have generated all the ones I need. On the other hand, I need to plot the bits in a graph where I have a scale on the right, and I like to have them all aligned.
There are two possibilites here:
  1. generate the bits, store them in the friendly <array> facility, and plot them in reverse order. Notice also that I would need to start the conversion from the biggest number in the set.
  2. come up with an estimate of how many bits I need. And this is what I chose.

In a more fully feature programming environment I would do the local equivalent of a base 2 logarithm and get exactly how many bits I need. Here I have to make do with this:

set n 1
repeat i 1 16
{		// 16 is arbitrary: suppose this will never run with really big numbers
   set n (n*2)
   smaller? total n
   {
      set maxbit (i -1)
      set i 16
   }
}

And this is the rest of the code: trivial, really, once you have all the rest set up

//field 0 0 20 (maxbit*10) 70
//field 40 0 50 (total) 40
//DEBUGGING - am I getting the right number for the maxbits

repeat n 0 total
{
   set dec n
   repeat bitindex 0 maxbit
   {
      set x1 ((numbersize *3) + ((bitwidth+bitgap)* (maxbit - bitindex)))
      set y1 ((n * numbersize) + 1)
      set x2 (x1 + bitwidth)
      set y2 (y1 + numbersize -2)        // much math to build a tidy rectangle in the boundaries
      field x1 y1 x2 y2 ((dec %2) * 100)
      set dec (dec/2)
   }
}

Of course, what is important is not the code you just read; rather the process that led to it.

Lesson Plan

  • the material written up above; I designed this class in response to people's concerns with being unable to turn their idea into code.
  • presentation of logical operators AND, OR, XOR, NOT; definition of unary operator. Truth tables.
  • assignmenent for next week: How many different 2-ary logical operations can you imagine? What do they mean?

Listen to Me! <--- oOo --->computers against spacetime

Log in or register to write something here or to contact authors.