Weird recursive algorithms

Here are some weirder recursive algorithms.

TAK

The Tak function was invented by Ikuo Takeuchi of the Electrical Communication Laboratory of Nippon Telephone and Telegraph Co., for the purpose of comparing the speeds of LISP systems [1]. This is one of those non-sensical algorithms that can be used to profile efficiency, either of a system or language, similar to Ackermann. The amount of recursion performed by this algorithm is significant. Here is the algorithm:

tak(x,y,z) = y, if x<=y, otherwise
tak(x,y,z) = tak(tarai(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y))

Call this with tak(10,2,9) returns a calue of 9, calling the function 4145 times. Here is the C version of the function:

int tak(int x, int y, int z) {
   if (x > y)
      return tak(tak(x-1,y,z),tak(y-1,z,x),tak(z-1,x,y));
   else
      return y;
}

Zibonacci

This is a weird rendition of Fibonacci which tends to calculate results which appear to zig and zag.

zib(0) = 1
zib(1) = 1
zib(2) = 2
zib(2n+1) = zib(n) + zib(n-1) + 1, if n>0 (odd values 3 and higher)
zib(2n) = zib(n) + zib(n+1) + 1, if n>1 (even values 4 and higher)

The C program to calculate this looks like:

int zib(int n) {
   if (n == 0)
      return 1;
   else if (n == 1)
      return 1;
   else if (n == 2)
      return 2;
   else if (n%2 == 1 && n >= 3) // odd
      return zib((n-1)/2) + zib((n-1)/2-1) + 1;
   else if (n%2 == 0 && n >= 4) // even
      return zib(n/2) + zib(n/2+1) + 1;
}

Here is the output for 1 to 20:

1  2  3  6  4  10  6  11  10  15  11  17  15  18  17  22  18  26  22  27

Tribonacci

This algorithm mimics Fibonacci, but adds the previous three values instead of two. The first three Tribonacci numbers are 0, 0, 1.

trib(0) = 0
trib(1) = 0
trib(2) = 1
trib(n) = trib(n-1) + trib(n-2) + trib(n-3)

Here are the values 0 to 10: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81

Here is the algorithm written in C:

int trib(int n) {
   if (n == 0 || n == 1)
      return 0;
   else if (n == 2)
      return 1;
   else
      return trib(n-1) + trib(n-2) + trib(n-3);
}

[1] McCarthy, J., “An interesting LISP function”, ACM Lisp Bulletin, 3, pp.6-8 (1979)

 

 

Advertisements

Stupid switch (ii) – Bad design

In most cases when we learn about the switch statement in C, we get something of the form:

switch(op) {
   case '+' : result = a + b;
              break;
   case '-' : result = a - b;
              break;
   case '/' : result = a / b;
              break;
   case '*' : result = a * b;
              break;
   default : printf("Error! Operator not found\n");
}

Which is pretty innocuous, and could have been coded with slightly less code using an if-else sequence. But switch has a somewhat darer side. While the if statement and the for and while loops allow a single statement without enclosing { }, so does switch, which is not something that is ever really discussed. So technically, this is valid:

switch(0);

as is this:

switch(i)
   i=i+1;

and even this:

switch(x)
   case 0:
      for (i = 0; i < 10; i++)
   case 1:
      for (j = 0; j < 10; j++)
   case 2:
      for (k = 0; k < 10; k++);

They all compile and run. But using them leads to code which is extremely difficult to comprehend, and likely results in the obfuscated code commonly seen in C (more so than any other language). Here is another fun piece of code:

int j, x=0;

switch(x) {
   int i = 4;
   case 0:
      j = i * i;
   default:
      printf("%d %d\n", i, j);
}

When this code runs, the answer produced is something like “32767 1073676289”, which is not the “4 16” expected. But why, it compiles okay? The problem is that the variable i is declared within the switch block, but it is not initialized to the value 4. This means that i contains some type of indeterminate value, in this case 32767, which when squared gives 1073676289.

This code seems odd, but it represents something that a novice programmer might write, and consequently it is compiled, which indicates to the programmer that what they wrote is acceptable.

 

 

Stupid switch (i) – Why B’s switch statement was better

One of the inadequacies of C has always been the lacklustre switch statement, which is less useful than similar statements found in other languages. This is strange considering C’s evolution from B, mainly because B allowed ranges, that’s right ranges. Consider the following piece of B code¹:

switch(c) {
   case 'A' :: 'Z' :
     c = c + 'a' - 'A';
   case 'a' :: 'z' :
   case '0' :: '9' :
   case '_' :
     break;
   case '.' :
     printf("Warning: avoid using dot.*n");
     break;
   default:
     printf("Invalid character:'%c'.*n",c);
     exit();
}

Although it has the awkward fall-though characteristic of C, it specifies ranges using the :: separator. Note that some compiler like GCC allow C language extensions, in this case using “…” in the form:

case 0 ... 9 :

But for some reason C has never adopted this in the standard. B also allowed relational headings, using <, <=, >=, and >. For example¹:

switch(i) {
   case <0 :
     printf("Number is negative");
     break;
   case 0 :
     printf("Number is zero");
     break;
   case >0 :
     printf("Number is positive");
     break;
}

Ignoring the whole fall-through issue, there is no doubt that both these concepts would have made the switch statement a much more effective construct in C.

¹ From “The B Tutorial Guide

 

Where did C arrays come from?

One of C’s predecessors was B, designed and implemented by Ken Thompson and Dennis Ritchie. B is essentially a simplified version of C, descended from BCPL. In the “Users’ Reference to B”, B was touted as a language good for “recursive, non-numeric, machine independent applications, such as system and language work” [1]. It was a typeless language, i.e. it had no type, or rather it had one type – the machine word, which is very similar to C’s int type.

Now arrays were problematic, because it is impossible to pack a whole array into a single word. B overcame this by defining an array to a pointer to a block of storage – the pointer could easily be stored in a word. This also makes it trivial to pass the array to a function, as only the pointer to the storage needs to be passed, not the whole array. Arrays were termed vectors in B.

From [1] – “a vector is a primary expression followed by any expression in [ ] brackets.” and “The primary expression can be thought of as a pointer to the base of the vector, while the bracketed expression can be thought of as the offset in the vector”.  The invertible notation used in C also had its beginnings in B: “Since E1[E2] is identical to *(E1+E2), and addition is commutative, the base of the vector and the offset in the vector can swap positions”.

There were some differences. In B, a vector was declared in the following way:

auto vec[10];

However this actually allocates 11 consecutive words, from vec[0] to vec[10]. A tutorial on B [2] makes the point that B lacks the Fortran-like ambiguity between subscripts and function calls, which both use ( ). B also introduced the unary operators * and & for manipulation of addresses. ‘&’ is the address operator so &x is the address of x, assuming it has one. ‘*’ is the indirection operator; *x means “use the content of x as an address.”

Strings were just a vector of characters, terminated in this case by what Kernighan calls a “mysterious character” known as *e (ascii EOT).

Interestingly enough, one document on B [3] makes it quite clear that “B does NOT check whether an index has gone past the end of a vector.”, going on to say “In B, it is the programmer’s responsibility to make sure that indices don’t run off the end of a vector. ” Seem familiar? (B also allowed negative indices in certain circumstances it seems, a practice I’m glad C dispensed with).

[1] Thompson, K., “Users’ Reference to B”, Bell Telephone Laboratories, (1972)
[2] Kernighan, B.W., “A Tutorial Introduction to the Language B” (1996)
[3] The B Tutorial Guide

 

Using the “Processing” language

Today I stumbled onto a language called Processing. It seems to be an OO language similar to Java in construct (but with a simplified syntax), coupled with an IDE – built for media art and visual design. It appeared in 2001, so it has been around for a while, just flying under the radar I imagine. I downloaded the OSX IDE and it ran without fuss, which was nice. It took a couple of hours to get the hang of how it works, but there seems to be a good amount of functionality. I found Processing because I was looking for a language to implement visual recursion algorithms, such as Hilbert curves. Due to the fact that I do like Julia, I tried to install Luxor, a Julia package that does vector drawing, but the install was *horrible*, and it still didn’t run (this is always my fear when people create packages – they become so overwhelm, I fear installing them). I’ve never like Java, but I don’t mind the language structure of Processing. Below is a program to generate a Hilbert curve.

float turtleangle = 0;
float cx;
float cy;
float length;
 
void setup() {
  size(400, 400);
  cx = width/2;
  cy = height/2;
}
 
void draw() {
  length = 10;
  background(255);
  stroke(0);
  hilbert(4,90);
  noLoop();
}

void hilbert(int level, float angle) {
  if (level == 0)
    return;
  rotation(angle);
  hilbert(level-1,-angle);
  forward(length);
  rotation(-angle);
  hilbert(level-1, angle);
  forward(length);
  hilbert(level-1, angle);
  rotation(-angle);
  forward(length); 
  hilbert(level-1,-angle);
  rotation(angle);
}

void forward(float amount) {
  float newX = cx + cos(radians(turtleangle)) * amount;
  float newY = cy + sin(radians(turtleangle)) * amount;
 
  line(cx, cy, newX, newY);
  fill(0);  
  cx = newX;
  cy = newY;
}

void rotation(float degrees) {
  turtleangle = turtleangle + degrees;
}

The system works by applying the setup() function (sets up the drawing board, in this case a 400×400 board), and draw() functions, which are the standard functions. The function hilbert() generates the curve, using forward() to move a certain distance from a point, and rotation() to rotate a certain amount. The only real problem I had was realizing that draw() needs a call to noLoop(), otherwise it continues running in a loop. Here is the output:

Overall, the experience of programming in Processing was quite good. The only problem is that using Turtle Graphics is super easy, and Processing requires you to write functions to perform some of the moving operations. Next I’m going to try and build something a little more complicated: a sunflower spiral.

P.S. I don’t really like the name. I *get* where they were going, but the term processing is far too generic to use as a programming name (it’s also hard to Google stuff).

 

 

Timing and efficiency in C programs (ii)

TIMING WITH NANO SECONDS

Now a nanosecond is one-billionth of a second. That’s pretty small, and essentially regardless of the system, a version of clock_gettime() can be cobbled together. The library time.h contains a structure timespec, which has the following members:

time_t tv_sec    /* seconds */
long   tv_nsec   /* nanoseconds */

If the system is OSX, then the following code will include the appropriate libraries:

#ifdef __APPLE__
#include <mach/clock.h>
#include <mach/mach.h>
#endif

Then a function can be built to return the time, stored in a timespec structure, using the Mach clock.

void get_Mach_time(struct timespec *ts) {
 
#ifdef __APPLE__ // OS X does not have clock_gettime, use clock_get_time
   clock_serv_t cclock;
   mach_timespec_t mts;
   host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &cclock);
   clock_get_time(cclock, &mts);
   mach_port_deallocate(mach_task_self(), cclock);
   ts->tv_sec = mts.tv_sec;
   ts->tv_nsec = mts.tv_nsec;
#else
   clock_gettime(CLOCK_REALTIME, ts);
#endif

}

On line 6, the code gets a Mach clock port using the function host_get_clock_service(). The parameter CALENDAR_CLOCK is time since the epoch (1970-01-01). The port is returned in cclock. The function clock_get_time() is then used to get the time, which is returned in the variable mts, a structure which is the same as the timespec struct from time.h. The code on line 8 deallocates the port. The code on lines 9 and 10 assign the seconds and nanoseconds data to the timespec struct ts, which is returned from the function. This is used in the following manner:

get_Mach_time(&ts1);

// code to do something

get_Mach_time(&ts2);

ts1nano = ts1.tv_sec * 1000000000 + ts1.tv_nsec;
ts2nano = ts2.tv_sec * 1000000000 + ts2.tv_nsec;
diffN = ts2nano - ts1nano;

printf("%lu nanoseconds\n", diffN);
printf("%.6lf milliseconds\n", diffN/1000000.0);

The calculates are performed in nanoseconds,  and then output in both nanoseconds and milliseconds.

EXPERIMENTS

Consider some experiments using Ackermann’s function. Calculating ackerman(4,1) using all three methods results in the following:

clock           8565 milliseconds

gettimeofday    8700 milliseconds

get_Mach_time   8593.151 milliseconds

Timing is obviously somewhat different because the algorithm had to be timed separately three times.

Timing and efficiency in C programs (i)

What would algorithms be without time. Efficiency. Sure, there will always be faster machines to run algorithms on, so efficiency may not be that big a deal. Or is it? Certainly resources on a mobile device, or a probe going into space are limited. More resources = more energy requirements = bigger batteries = less room for increased functionality (i.e. higher resolution cameras).

So how do we calculate how fast an algorithm runs? Firstly, what are the properties of the speed calculation – real/user/system time? seconds/milliseconds/microseconds?

THE MOST BASIC TIMING REGIME

The most basic timing uses the time.h library, and the clock_t structure. It allows timing using seconds, and the function clock(), which provides a minimum amount of feedback.

The function clock() returns the sum of user and system time represented as CPU time in cycles, but modern standards require CLOCKS_PER_SEC to be 1000000, giving a maximum possible precision of 1 µs. Here is a sample piece of code:

clock_t start, end;
double timeshift;

start = <strong>clock()</strong>;

// Perform some operation

end = <strong>clock()</strong>;

timeshift = (end - start) / CLOCKS_PER_SEC;

The variable timeshift will contain the timing for the algorithm in seconds. This works okay, but if the time resolution between algorithms is finer, then chances are this will produce the same time. To calculate the value in milliseconds:

timeshift = ((end - start)*1000) / CLOCKS_PER_SEC;

TIMING WITH FINER RESOLUTION

A better measure of timing can be had using the sys/time.h library and the timeval structure. The structure looks like this:

struct {
   int32_t tv_sec;         /* Seconds */
   int32_t tv_usec;        /* Microseconds */
} ut_tv;                   /* Time entry was made */

struct timeval ut_tv;      /* Time entry was made */

The function gettimeofday() returns the current wall clock time.

struct timeval t1, t2;
long sec, msec, tmilli;

gettimeofday(&t1,NULL);

// Perform some operation

gettimeofday(&t2,NULL);

sec = (t2.tv_sec - t1.tv_sec); 
msec = (t2.tv_usec - t1.tv_usec); 

tmilli = (1000 * sec) + (msec * 0.001);

printf("%ld milliseconds\n", tmilli);

This timer has 1 microsecond resolution, where 1,000,000 microseconds = 1 second.

Are there problems with this approach? Yes, some to do with NTP (network time protocol) and the fact that processes on the system can potentially change the timer, making it jump backward and forward in time.

Sometimes it returns a negative value. That’s right, your program was *so* efficient it executed before you even ran it. The problem is that gettimeofday() still can’t really tell the difference between a 2 microseconds and 3 microseconds difference. The problem lies in deriving the code. If the difference in time is derived as above, the code will work as long as the relationship t2.tv_usec > t1.tv_usec holds. However although the relationship t2.tv_sec > t1.tv_sec holds, the same is not true for microseconds. For example consider the following two timestamps:

t1 = 1370282687 434738
t2 = 1370282711 289326

Calculating the differences results in 24 for seconds, and -145412 for microseconds. A better way is to convert both elements of the structure to microseconds, before calculating the difference.

long t1_msec, t2_msec, diff;

t1_msec = (1000000 * t1.tv_sec) + t1.tv_usec; 
t2_msec = (1000000 * t2.tv_sec) + t2.tv_usec; 

diff = t2_msec - t1_msec;

Or, even better, use the function timersub(), also found in sys/time.h. It basically works like this:

timersub(&t2, &t1, &tv);
tMilli = (1000000 * tv.tv_sec + tv.tv_usec) / 1000;
printf("%ld milliseconds\n", tMilli);

The difference is calculated and stored in the structure tv, which can then be output in microseconds. Note that microseconds may be too fine a resolution, however dividing by 1000 gives a measure in milliseconds.

Note that on some systems (Linux, BSD) gettimeofday() has been replaced with clock_gettime() (not OSX).

 

While C is a surfer dude, Ada is Thor

I like to think of C and Ada as two different personalities. C is the surfer dude of programming languages, sitting on the beach, being cool with everything, “Hey, I’ll compile the array that’s out of bounds… no problem”. It has a very easy-going way about things. C thinks using pointers is gnarly, and that you’re not really cool until your program is obfuscated (which really just means that the code is now speaking a different language, like surfer slang). With Surfer C there is never a problem, well, until there is. Programming in C is sometimes like being lured to sea by Sirens, we are bewitched by their song, and then getting caught in a rip, dragged out to sea. Ada on the other hand is the Thor of programming languages. Array out of bounds? Ada will smash down its hammer. It is a different experience. Ada enforces type compatibility which makes sure we don’t use incompatible types.

Now all this has to do with how they were brought up. C is “weakly typed”, and Ada is “strongly typed”, like its predecessors Pascal, Euclid and Modula. If you have never heard these concepts before, let’s take a moment to understand them. Typing, i.e. whether a language is weak or strong, which are somewhat vague terms. The quasi difference between a strongly typed language and a weakly typed one is that a weakly typed one makes conversions between unrelated types implicitly. A strongly typed language, on the other hand, typically disallows implicit conversions between unrelated types. Strong typing means that it is impossible to concatenate a string with a floating-point number. In C, not every type is checked, and so it is considered fairly weakly typed. Consider the following piece of code in Ada:

i : integer;
u, v : float;

v := 5.6;
i := 2;
u := v + i;

This code will fail to compile, resulting in an error message of the form:

typeeg.adb:15:11: invalid operand types for operator "+"
typeeg.adb:15:11: left operand has type "Standard.Float"
typeeg.adb:15:11: right operand has type "Standard.Integer"

To fix this problem, you actually have to explicitly convert i, i.e. float(i). Ada will not do an implicit type conversion from integer to float, C on the other hand will do an implicit conversion. Fussy? Maybe, but it does lead to fewer inadvertent mathematical errors. Conversely, consider this convoluted piece of code in C:

int x = 0;
void *v = &x;
char *c = v;

printf("=%c=\n", *c);

Code it, run it. The result is interesting. Not the sort of code you really want people to create. (You cannot create a void variable, but you *can* create a pointer to void).

It’s also about the job they do. C is a systems programming language, which is often used to build things like embedded systems, or even compilers for other programming languages. C is considered by some to be a WYSISWYG language – looking at a C program gives a good indication of what the lower level combined code will look like. That’s why C is such a good language for lower-level software that interacts with hardware. On the other hand, it is not really known how well such languages scale to large systems (we develop large systems, but who has ever evaluated the software development process for  programs 50 million lines long?). In addition, C’s focus is on efficiency, and as such it sacrifices checks that other languages make – reliability, safety and security can sometimes be compromised. Ada on the other hand was designed for embedded systems, multi-tasking, and dealing with real-time programming. For instance in the aerospace, or transport industries – driverless trains anyone?

People will argue that C is better because it is, well, C! Ada is too unwieldy. But I know I would prefer to drive in a car/plane/train built in Ada over one built in C (well, I would be okay if the programmers were truly experts), but better C than C++, or heaven forbid Java.

 

Coding Cobol: dynamic filenames

So how do we prompt for a filename in Cobol?

identification division.
program-id. fileio.

environment division.
input-output section.
file-control.
select ifile assign to dynamic ws-fname.

data division.
file section.
fd ifile
   record contains 88 characters.
01 student-info.
   05 student-name occurs 4 times.
      10 stdnt-name pic x(15).
      10 stdnt-idno pic x(7).

working-storage section.
01 i pic 9.
77 ws-fname pic x(30).

procedure division.

   display "Filename containing book information? ".
   accept ws-fname.

   open input ifile.
      read ifile
   end-read.
   close ifile.

   move 1 to i.
   perform print-out until i is greater than 4.
   stop run.

print-out.
   display "Student name is " stdnt-name(i).
   add 1 to i.

Here’s what a potential data file has in it (Each record has 22 elements, 15 for the student name, and 7 for the student number):

Skywalker      6543287Ackbar         1189283Chewbacca      9882870Palpatine      0000001

One line of code in the environment division specifies the dynamic filename:

select ifile assign to dynamic ws-fname.

The output from this program is:

Student name is Skywalker
Student name is Ackbar
Student name is Chewbacca
Student name is Palpatine

 

C language: The good, the badly, and the ugly

C is a language used by many a programmer, and it is an interesting language. But here’s the thing, it was never designed to teach people how to program. It’s a great language for people who have a basic understanding of programming principles, but for a novice programmer, it just doesn’t make the grade. Let’s explore why.

The Good

Let’s start off with the good. C only uses 32 reserved keywords, which is extremely good from the perspective of learning the entirety of the language. On the other end of the scale, Java has 50, and C++ has the 32 keywords of C, with an additional 30 keywords, for a total of 62. So, C has brevity on its side, which is good. C also allows for access to low-level programming, some have likened it to “assembler with steroids”. This is a double edged sword, because it makes the language powerful, but it also makes it unwieldy for a novice programmer. It is also a very powerful language, and that is best illustrated by the fact that a number of compilers for other languages are written in C. However  Python has 33 keywords and is inherently easier to deal with.

C is also a pure language, unlike many other languages are multi-paradigm, or use concepts such as OO. Not that OO is bad, it’s just a real distraction to have to deal with concepts such as inheritance and polymorphism. However if you learn C, it is easier to transition to languages with a similar structure, such as C++, and even Java. Other good things? I have to strain to think of some… for the novice anyway.

The Bad

For the novice programmer, who knows very little about the intricacies of memory, C can be a horrible language to learn to program in. This manifests itself in the first time a programmer writes a scanf() statement. Consider this piece of code:

int nmbr;
scanf("%d", &nmbr);

To a veteran programmer, this is not an issue. To a novice, they are forced to understand that the ampersand character in the clause &nmbr is used to store the value input by the user from the keyword in the memory position associated with the integer variable nmbr. Quite a daunting task. Failure to add the & will result in a problem int he form of a Segmentation fault: 11. But the compiler *will* compile the code, giving the programmer the false sense of security by thinking that their code is okay. This could not be further from the truth. Now the novice programmer has to try and figure out what a Segmentation fault: 11 means.

This reliance on memory does not go away. It forces itself upon the programmer again in the guise of pointers in the context of function parameters, and dynamic memory if a large amount of space is need to store some piece of data. It can also inadvertently appear in the form of insufficient memory associated with the stack. You have to understand memory to program in C, it’s unavoidable. In addition, C allows programs with errors to run. Consider the following code:

int a = 0;
if (a = 1)
   printf("valid");

C allows assignment statements within an if conditional, so the fact that a is set to equal 1, means that the condition will always be true, regardless of what a‘s value is coming into the if statement. There are also deep issues with a failure to check array bounds, and overwriting memory.

The UGLy

Ugliness in C manifests itself in the compactness of the language. Firstly through the use of compact operators such as ++, ––, &&, ||, += etc. These operators likely made a lot of sense when C was first introduced, because they likely helped reduce machine instructions (many were first used in preceding language such as CPL, BCPL, B, etc). However to the novice programmer, the i=i+1 is inherently easier to write than i++, because it is understandable (once they get past i=i+1 as a programming statement, not a mathematical one).  The use of operators such as ++ serve to confuse the novice programmer, because in certain contexts such as:

int p = 4;
p++;
printf("%d", p);

The value of p is 5, whether or not p++ or ++p is used. However used in this context:

int p, x;
p = 4;
x = p++;

The value assigned to x is 4. Change p++ to ++p, and the value of x becomes 5. This is because p++ means “use the value of p, then increment p by 1, and ++p means “increment p by 1, and then use its value”. Subtle, yet bound to make an algorithm fail. The novice programmer doesn’t need this (and I would argue the rest of us don’t either). There are similar issues using && for and, etc.

There is also things like the way arrays are indexed. The most common way is something like a[x], where x is the index. However in C it is also possible to write x[a], which is super confusing for the novice. This is because a[x] means *(a+x) and x[a] means *(x+a).

Ugly? Yes.

Oh, and some control structures that have somewhat obtuse structures (e.g. switch), or lack consistency, such as the while and do-while loops. The while loop does not require enclosing parentheses, unless there is more than one statement. The do-while loop does require parentheses. Lack of consistency causes recall issues amongst novice programmers.

The BORING

I add this last category, because frankly, C is a boring language. There are things that can be done with C, but it takes a good amount of experience with the language. Starting with the bare bones language, there is nothing inspiring which can be done. No graphics, no processing images, no fun stuff. So it is inherently hard to motivate novice programmers, when the pinnacle of fun is outputting Factorials, or a “cool” sorting algorithm.