Never waste your memory! (Huffman Encoding)

In Morse code, a simple “dit” (.) represents the letter e, while a more complex sequence “dah-dit-dah-dah” (-.–) represents the letter y. As you probably know, the occurrence of e is significantly higher than the occurrence of y in most languages. So obviously Samuel F. B. Morse tried to make his code as efficient as possible for transmission of large text documents.

Morse followed a principle which is fundamental to data compression. In an uncompressed simple text file all characters may be represented by ASCII characters. The length of each character is exactly 8 bit, regardless of what character it is and how often it occurs in the text.

David A. Huffman (1925-1999) developed a fancy method which allows us to encode symbols, e.g. characters, in a way that symbols of high occurrence will be represented by shorter bit patterns than symbols of lower occurrence. In fact, Huffman encoding is one of the most efficient ways to reduce redundancy (unnecessary data) while maintaining 100% of the information. In computer science this is therefore called lossless data compression.

At this point I’d like to skip the mathematical background, which is not as hard to understand as you might think, though. Instead, I want to show you a concrete example. The German word “ERDBEEREIS” (strawberry ice cream in English) takes 10 * 8 bit = 80 bits when stored in 8-bit ASCII code.

Let’s now try to reduce its memory consumption by applying the Huffman algorithm. What we are going to do is to build a binary tree that helps us to find out the bit pattern for each letter.

Step 1 – For each different letter in the word create a node and write down its occurrence in the word.

Step 2 Take the letters that have the lowest occurrence and combine them into a new node. Add the occurrences of both letters. (In our example we might as well could have chosen ‘D’ and ‘B’ instead of ‘I’ and ‘S’).

Step 3 – Now again choose the two nodes of lowest occurrence, combine them into a new node, and so on.

The Huffman tree is now complete. We can easily find the code for a letter starting from the root and moving down to the letter. Each time we follow the left branch, we add a 0 to the code. As you can guess, each time we follow the right branch, we add a 1 to the code.

So the code for letter ‘B’ is 1011 while ‘E’ is just a single 0.

With this tree, the word “ERDBEEREIS” is coded as
0 100 1010 1011 0 0 100 0 110 111

The compressed word only takes 24 bits of memory instead of 80 bits. Pretty cool, eh? (For those of you who feel comfortable with math: The entropy of “ERDBEEREIS” is about 23.2 bits, which means the redundance is now <1 bit.)

You think we do not need to bother about “wasting” bits in an era where we can get Terabytes of memory for no money and where we have Gigabit-Ethernet? Well, you might be wrong, because the amount of data we need to store and to transport has steadily increased (well, it literally had exploded during the last decade). Just think of television on demand, high definition movies, and so on. Data compression is and will be an issue of growing importance.

Well, now relax and get yourself some ERDBEEREIS. 🙂

Cheers,

— Andre M. Maier

Posted in Bit-Twiddling, Information Theory, Uncategorized | Tagged , , , , , | Comments Off on Never waste your memory! (Huffman Encoding)

Pointers and References – Part 3 (Kinky Stuff)

Once in a while, I show my students some fancy examples of what you can (but shouldn’t) do with pointers. Most students would be watching the screen with baffled looks on their faces. Those who cannot find any interest in such experiments should seriously consider changing their subject of study, because they do not have the necessary intrinsic motivation to become a ruler of the binary world. 😉

Here are two easy-to-understand examples in C code.

A brief note for fellow teachers and college professors: Of course there are much more tricks you can do. Once you have deep background knowledge about CPUs and storage management, you’ll have an inexhaustible magic hat that allows you to instantly “pull out” any trick during a lecture. Avoid showing such tricks in classes with a high number of less motivated students. In such classes it might be more fun joining your students to a nearby pub instead. 😉

1. Magic Numbers

Question: What is the output of the following program?

#include <stdio.h>

int main() {

  int a = 1919184449;
  int b = 1632444517;
  int c = 175269225;
  int var1 = 1801808965, var2 = 1852797556;
  int var3 = 1668508521, var4 = 1701606760;
  int var5 = 1952797728, var6 = 1851879028;
  int var7 = 2663;
  printf( "%s", &a );
  return 0;

}

Answer:

Andre Maier
Elektronikschule Tettnang

So why’s that? Simply because of four factors playing together.

  • An array of characters (variable a) is a pointer. It points to the start of a character sequence stored in your computer’s memory. Here the only character of the sequence is ‘H’ … which for some strange reason doesn’t seem to have anything to do with the output.
  • The format specifier %s used in the printf-statement retrieves characters from your computer’s memory beginning from the address of the pointer variable provided (a). %s won’t stop retrieving characters before it reaches an “End of Text” character (ASCII value 0). This is why strings in C always need to be terminated by an ASCII zero.
  • Any variable declared in a program will be placed somewhere in your computer’s memory. Depending on the architecture of your computer, subsequent variables may be placed directly before or after antecedent variables.
  • Any integer value causes a specific bit pattern in the memory. Depending on the architecture of your CPU bytes may be switched (depending on whether you are running the program on a “little endian” or a “bit endian” CPU).

Got the trick?

What I did is that I just choose int values which cause exactly the pit pattern of the ASCII values of the text I want to display. Because of my processor’s architecture (Intel/AMD) I needed to swap the bytes … you won’t need this step if you run the program on Motorola architecture. The char array a just serves as a staring point for %s. The ASCII zero value (binary 0000 0000, 1 byte) is hidden in the bit pattern of woo.

Well, it is obvious why you should never write such programs in real life: Just try to delete a certain letter from the text, for example. 😉

2. Cast the Impossible

You probably know how a type cast is working. For example, if you assign the value 1.678 to an integer variable i, your computer will just truncate all decimal places (so the result is i = 1). Some programming languages, such as Java, will probably warn you against some “loss of precision” and/or require explicit type casting. It is obvious that this is the most useful way to handle such casts.

What happens behind the curtain is that the representation of the value changes from IEEE754 format to the “usual” base 2 integer representation. The IEEE754 format is used for representing floating point numbers. Mathematically spoken, IEEE754 is a base 2 exponential representation that consists of a signum, a mantissa and an exponent. (I guess I’ll cover this in one of my future postings.)

The change of representation happens automatically. It happens every time when you assign a float value to an integer variable.

We could now raise the following questions:

Is there a way to assign the IEEE754 bit pattern directly to an integer variable without changing its representation in memory? Can we bypass the well-intentioned change of representation?

(If your answer is: Who would want to do this anyway? … Stop reading and get your hands off your poor computer!)

The answer is: YES! We can! 😉

Let’s take a look at the following program.

#include <stdio.h>

int main() {

   float f = 0.1;
   int* int_ptr = (int*) &f;
   int int_value = *int_ptr;
   printf( "%x\n", int_value );

}

The output of the program is 3dcccccd, which is the IEEE754 representation of the floating point number 0.1.

Here is how it works: In the second line of code inside function main() we declare a pointer to int and assign to it the address of the float variable f. The compiler would (of course) notice that we are going to mess up our program, because the address of f is pointing to a float variable instead of pointing to an int variable. That’s why we need to “cheat” by explicitly casting the float address to an int pointer. It’s like telling the compiler “I know, I know … but I really intended to do this”.

If we now access the content of the memory where the int pointer is pointing to … voilá! We directly access the bit pattern of the floating point number while your computer “thinks” it is “looking” at an integer number.

Oh, for those of you who are sure I wouldn’t be able to create any related assignments: Have you ever tried to apply bit twiddling operations, e.g. bitwise &, on a floating point number? I know several practical applications of this technique which could easily be used for nice assignments! HARHARHARRR! 😉

What you could see here is that pointers allow you to cast everything into anything you want it to be — even if it doesn’t seem to make sense. If you like you can have your computer interpreting the memory address of a function as a IEEE754 floating point number — which really wouldn’t make any sense, I guess.

That’s all for now, folks. While writing this posting a large number of new topics and ideas for further postings (mostly computer basics) crossed my mind. Let’s see what comes up next.

Have a great time!

— Andre M. Maier

Posted in Pointers, Uncategorized | Tagged , , , | Comments Off on Pointers and References – Part 3 (Kinky Stuff)

Pointers and References – Part 2 (Intermediate Stuff)

This is my second posting on pointers and references. In part 1 you could read about the basic nature of pointers. Now we will have a look on two very common examples of how pointers are being used.

1. Passing large data structures to functions

If a large amount of information is passed to functions (methods) by value, this consumes a huge amount of stack memory. So passing addresses which refer to a place where the actual information is being found is more efficient. If you want to pass a text string (array of chars in C) to a function, you might want to use a char pointer which refers to the first character of the text string. All other characters of the text string will follow subsequently; the ASCII zero character (EOT) indicates the end of the text string.

void function( char* text ) {
  // dereferencing and using text
  ...
}

If you call the function above, you just need to pass the address of a character array.

function( &text ); // where text is declared as char text[]

Yet another example of large data types in C are structures. These should always be passed by reference, too.

Java is a programming language for those who don’t want to think about the nuts and bolts of memory management. So it automatically wraps all large data types into objects. These objects are always handled by reference.

So if a method is defined as

public void method( String text ) {
  // using text
}

its parameter is a reference, even though the programmer won’t notice this fact on the first glance. In fact, he will only notice its reference-like behavior in specific situations, for example if he tries to compare two text strings by ==. This operator compares the value of the two string references, which (in most cases) has nothing to do with the content of the strings.

2. List programming

Using pointers can come in handy when working with lists, because there is a feature called pointer arithmetic. This means that you can increment or decrement a pointer in order to have it pointing to the next (or to the previous) storage address. Consider the following snippet of C code:

int a[] = { 3, 4, 5, 6 };
int* a_ptr = a;
a_ptr++;
printf( "%d\n", *a_ptr );

a_ptr is declared to be a pointer to int, but we actually assign to it the address of an array of int values a. Since an array variable always contains the address of the array instead of its values, we don’t need any & operator in the second line. In the third line of code the pointer a_ptr is incremented. It is now pointing to the next address in storage, that is those of the second element of the array (4).

What happened here is that we accessed an array element by reference instead by its index. It is crucial for the compiler to know the size of whatever datatype a_ptr may be pointing to. If you increment an int-pointer it will increment by the size of int (which may be 4 byte on your PC and 2 byte on a 8051 microcontroller). Other datatypes will be handeld respectively.

Cool stuff, eh? This way you could do linked lists, binary trees, whatever fancy things you like.

This is a great opportunity, however, to come to the other side of the coin when working with pointers.

  • What would happen if you changed a_ptr++ to a_ptr– in the code snippet above? (What’s in the memory before the array?)
  • What would happen if you declared a_ptr to be a pointer to char and you add an explicite type cast to assign the address of the int-array to it? (It surely would be incremented by the size of char …)

I’ll leave the answers to you. Get a C-Compiler (comes with every Linux Live CD) and have a try. You’ll understand in an instant why pointers can be evil and why there is no such thing in Java. 😉

In my next posting, I’m going to show you some of my kinky (but mostly useless) pointer gimmicks I sometimes use in my lectures to impress my students. Of course there is no magic about it, but it’s great to be admired by the unenlightened. 😉

See you in my next lecture!

— Andre M. Maier

Posted in Pointers, Programming Essentials, Uncategorized | Tagged , , , | Leave a comment

Pointers and References – Part 1 (Rookie Stuff ;)

Pointers are subject of fear for a large number of people. Some of them hate pointers because they can cause nasty problems that are difficult to debug, others hate them because they never really understood what pointers actually are. Indeed, a person who had never learned assembly language will find it hard to understand the nature and the consequences of pointers. Therefore, let’s start at the very beginning.

As you already know, all variables must be declared prior to their first usage in many programming languages.

int a;

A declaration will cause the system to allocate 32 bits somewhere in your computer’s memory. This is where a value (number) you assign to this variable will go. In many cases a programmer might not be interested in where exactly this place is. In fact, in your PC a variable might be ending up in different places each time you are running your program (*).

In many situations the programmer would not be interested on which memory address the value of his variable is ending up. There are some situations, however, where you can do fancy stuff by working with addresses rather than values.

Consider, for example, that you want to pass a large amount of data (e.g. stored in an array) to a function or method. If you would pass this data by value, this would require a large amount of stack memory to be used for local storage of the data. The reason is that all parameters of a function or method are being stored in the same way local variables are being stored: On a local variable stack. In most systems the stack size is (very) limited, because large stacks would negatively influence the runtime of function invocations.

So it might be much wiser to pass the address where in memory the data can be found instead of passing the whole bunch of data. In case of arrays three pieces of information would be sufficient to be known inside the function:

  • the address of the first array element
  • the size of each element (determined by the data type)
  • the length of the array (number of elements or end)

Working with addresses requires the compiler to handle a special data type: The pointer, sometimes referred to as reference.

Some people say that a pointer is not a variable, which is not exactly true. A pointer is a variable, but its value is neither a phone number nor a text message. Instead, the value of the pointer variable is the address in your computer’s memory under which the phone number or text message can be found. As we say, a pointer variable is pointing to a value stored somewhere else in memory.

Some programming languages (such as C) allow declaration of pointer variables for all kinds of data types. Some languages (such as Java) do not allow declaration of pointers for primitive data types, but use pointers for complex data types (e.g. arrays, objects, …). Other languages do not support any pointers at all (BASIC).

Let’s have a look at C to get an impression of how pointers are handled.

A pointer only makes sense when there is an existing value that can be pointed to. The following code snippet shows the declaration of a variable a and a pointer variable named pointer_var. The asterisk before the variable name indicates that this variable is a pointer.

int a;
int *pointer_var;

pointer_var is now declared to hold addresses under which int values are being stored.

If you now want pointer_var to contain the address of variable a you just have to add the following line of code.

pointer_var = &a;

The ampersand symbolizes the words “address of“.

Now there are two ways of assigning values to variable a.

1. Directly (by value), which is the way you know and you probably find the most convenient.

a = 5;

2. Indirectly (by reference), which implies using the address of a stored in the pointer variable.

*pointer_var = 5;

What make the syntax difficult to understand for some people is the different meaning of the asterisk. Here it is used for “dereferencing” the pointer. You can read *pointer_var like this : “Value that is stored at the address which is given by pointer_var“.

That’s all for a brief introduction of what pointers actually are. A more advanced topic on pointers will follow.

So long,

— Andre M. Maier

(*) This is different in computers that do not use any operating system, such as microcontrollers.

Posted in Pointers, Programming Essentials, Uncategorized | Tagged , , , | Comments Off on Pointers and References – Part 1 (Rookie Stuff ;)

Parity

Data transfer inevitably threatens data integrity. It does not matter whether you save and restore files on your hard disk or you transmit data over long distances. Bits can always get twisted by interfering electric and electromagnetic fields. TCP/IP uses CRC checksums which often is too complex and too performance-consuming to be used in simple communication systems (e.g. RS-232).

In such simple systems it can be sufficient to use a parity bit to ensure (or at least to improve) data integrity. Since the parity bit is just a bit, its power is limited. It allows you to detect an error, but it won’t tell you which data bit is wrong. Also, if any even number of bits in a word have been affected by interference at the same time, you won’t even see any error at all.

To understand what a parity bit is simply imagine any word of data bits, for example the byte 01000011 (which is 0x43 or ASCII-letter ‘C’). Now attach a bit to this word which ensures that the total word (including the added bit) contains an even number of 1s.

In the example above: 101000011

If the word of data contained only two 1s, you had to add 0. The bit added is called parity bit. In this case we ensure even parity, but you can also opt for odd parity.

Most CPUs internally provide a parity bit often located in the PSW (program status word). It automatically indicates the parity of certain register (e.g. accumulator). Usually the parity bit is determined by a parity decoder. This is a logic circuit which consists of cascaded XOR-Gates. You can easily see the XOR dependency when setting up an according boolean equation. No magic involved.

But have you ever thought of how the parity of n bits could be calculated by software — just for fun?

A hardware parity decoder XOR-combines a bit with the result of the previous bit, which is XOR-combined with the result of the previous bit, which is XOR-combined with … you get the idea.

We can describe this process of subsequent XOR-ing mathematically by the following relationship.

Even Parity, mathematically expressedWhat it represents is a loop which loops over the whole word (from 0 to n-1). In each step it XORs the previous result and a specific bit out out of the data word. The shifting operator (>>) allows us to extract each bit out of the squence by using a mask that has the LSB set.

For those of you who are not feeling comfortable with mathematical descriptions, here is an example program in C. It calculates the even parity of an eight bit word (0…7).

for( i = 0; i < 8; i++ ) {
   parity = parity ^ ( data & 0x01 );
   data = data >> 1;
}

That’s all for now. Have a try and play with it! 🙂

— Andre M. Maier

Posted in Bit-Twiddling, Uncategorized | Tagged , | Comments Off on Parity

Masking

In this posting I’m going to explain a bit-twiddling technique called masking. It is used to extract (and alter) specific bits in a word of bits, for example a byte. You might be familiar with IP subnet masks in network engineering, which one practical application of masking.

You may need some deeper understanding of how masking actually works, if you want to set up registers in a microcontroller system or if you want to fiddle with the guts (e.g. UART) of your PC.

Masking allows you to set or to reset specific bits in a byte (or word) without “touching” any other bits in the word. Here is an example assignment.

Assume that a is a variable of an 8-bit datatype (e.g. unsigned char in C). Further assume that you want to set the MSB (Most Significant Bit, or Bit No. 7) without changing the state of any other bits.

unsigned char a;
a = ... // already coded: some codes that may set or reset the
        // bits 0 to 6 of a

// TBD: Insert code that only sets the MSB (Bit 7) of a without
//      changing bit 0 ... bit 6

If you solved this problem by using something like this,

a = 0x80;

you would also set or reset other bits in the variable (which we did not want to do).

The solution is masking. You just need to remember two basic things about logic operators.

OR allows you to force a bit to HIGH (1)
AND allows you to force a bit to LOW (0)

The reason is that if you use OR on two bits the result will always be 1 whenever at least one of the bits is 1. If you use AND on two bits the result will always be 0 whenever at least one of the bits is 0.

OR and ANDSo in our example above we need to use OR in order to force the MSB to 1. The code in C would be:

a = a | 0x80;

The value 0x80 is called mask. It only has those bits set which shall be set in the result (only the MSB in this case, because 0x80 is 1000 0000 when written in binary).

If you want to force bits to 0 be sure to use the AND operator. Note that the mask needs to be built in a different way. All bits which you want to be 0 in the result must be 0 in the mask. Bits you want to leave unaffected need to be 1 in the mask.

For example, let’s now reset Bit No. 2 (2² … which is the third bit from the right) of variable a.

We need to use AND with the mask 1111 1011 binary (= 0xFB hexadecimal), because we only want to reset bit 2.

The code in C is

a = a & 0xFB;

Now it is time to have some exercise. What is the value of variable a after the execution of the following code?

unsigned int value = 0xCC;
value = value | 0x05;
value = value & 0xA0;

See you!

— Andre M. Maier

Addendum
Christian Enchelmaier, who was one of my former students, sent me the following C code. It is a very nice and easy-to-read implementation of how masking could
be done in a convenient way. The only disadvantage is that due to subsequent masking single bits this code will require a greater number of machine cycles than the code in the examples above.

#define BIT_1 (1 << 0)
#define BIT_2 (1 << 1)
#define BIT_3 (1 << 2)

char val = 0;

// Set bits
val |= BIT_1;
val |= BIT_2;
val |= BIT_3;

// Clear bit
val &= ~BIT_2;

Thanks to Christian!

Posted in Bit-Twiddling, Uncategorized | Tagged , , , , | Comments Off on Masking

Conditional Assignments

Many programs require implementing some code which assigns values to variables based on certain conditions. Here is an example:

if( a < 5 )
   b = 3;
else
   b = 8;

The same in abbreviated form (Java):

b = ( a < 5 ) ? 3 : 8;

In most cases there is nothing wrong about such code. However, let’s have a look at this:

if( a == true )
   b = false;
else
   b = true;

It is easy to see that the code above can be replaced by the following simple statement.

b = !a;

Whenever there is a simple mathematical dependency between the variable used in the condition and the value to be assigned, you should express this dependency mathematically. So never do something like this:

switch( n ) {
   case 0: m = 2; break;
   case 1: m = 3; break;
   case 2: m = 4; break;
   case 3: m = 5; break;
   // ... and so on
}

If there is no simple mathematical dependency to be found, you also should consider the following question before coding the conditional assignment:

Is “assignment” really the only task to be performed if a certain condition occurs, and is it unlikely that further conditional code needs to be added in future?

If the answer is yes, it might be helpful to consider using a lookup-table for conditional assignments. Let me show you an example:

Imagine that you have an integer variable which indicates the day of week (1=Monday, 2=Tuesday, and so on). Let’s further assume that you want to convert this number into text.

A straightforward solution could be this:

switch( dayOfWeek ) {
   case 0: text = "Monday";
   case 1: text = "Tuesday";
   case 2: text = "Wednesday";
   case 3: text = "Thursday";
   case 4: text = "Friday";
   case 5: text = "Saturday";
   case 6: text = "Sunday";
}

However, in various programming languages, compilers, and platforms the following code may be way faster in execution.

String[] day = { "Monday", "Tuesday", "Wednesday", "Thursday",
                 "Friday", "Saturday", "Sunday" }; 

text = day[ dayOfWeek - 1 ];

Lookup-tables will only provide appropriate solutions in situations where the selector is an integer value, of course. In some cases they might be worth a thought, though. (Wow, a tongue-twister …)

In C you can do fancy stuff by using such tables: Just create an array that contains pointers to functions and invoke them based on the value of an integer variable. (This technique is called “function pointer array”.)

That’s all for now. Have fun!

— Andre M. Maier

Posted in Programming Essentials, Uncategorized | Tagged , , , , | Comments Off on Conditional Assignments

Simple Math: Truncating and Rounding Numbers

If you need to truncate or to round floating point numbers you should always use functions from your compiler’s math library. These functions have been thoroughly tested and there is no reason why you want to implement such algorithms manually — except you are the one who is being asked to design a math library.

Nevertheless, you might be interested in the principle behind these functions. There are a many websites explaining the nuts and bolts of various algorithms that can be used for rounding up, rounding down, rounding to the nearest, etc. You will notice that it is not difficult to understand such algorithms since they just require some basic knowledge about numbering systems.

This was supposed to become a short posting, so I will focus only on two basic examples.

Truncating

Given that a is a floating point number which is to be truncated to the third decimal digit. b is the variable to contain the truncated number (result). The following line of code will do the job.

int b = ((int) ( a * 1000.0 )) / 1000.0;

a is multiplied by 10³, because this will “shift” the decimal point three digits to the right. By this way the third digit right of the decimal point will become the first digit left of the decimal point.
Example: 3.14159265 * 1000 = 3141.59265
In the next step we need to cast the number to integer which truncates all digits right of the decimal point.
Example: (int) 3141.59265 = 3141
You got it … A floating point division that reverses the previous multiplication will do the rest.

Rounding

Rounding follows exactly the same principle as shown above. The difference is that prior to truncation a number is added, which increments the least significant digit of the result if the digit right to the least significant digit is greater than or equal to 5. If we add 0.0005, for example, the 10⁻³ weighted digit will be incremented if the 10⁻⁴ weighted digit is greater than 0.0005.

a = a + 0.0005;
int b = ((int) ( a * 1000.0 )) / 1000.0;

Simple math, isn’t it?

Cheers,

Andre M. Maier

Posted in Programming Essentials, Uncategorized | Tagged , | Comments Off on Simple Math: Truncating and Rounding Numbers

Loops

A loop allows to repeatedly execute a sequence of instructions. From the CPU’s view a loop simply means resetting the program counter (PC) which always points to the currently executed instruction.

       ; Example in some pseudo assembly language
       ; showing an unconditional loop (infinite loop)
       ; ---------------------------------------------
0000h: ; here is the code
0001h: ; within the loop
0002h: jmp 0000h

In the last line the jump instruction resets the program counter, so it will be pointing to the first instruction within the loop. If you grew up in the 80’s and enjoyed owning a home computer you might remember an equivalent unconditional loop in BASIC.

10 PRINT "Good ole times! Where did they go?"
20 GOTO 10

And here is the proof that C isn’t any better than BASIC.

start: printf( "Oh my God!\n" );
       goto start;

In most cases we may want to create conditional loops that repeat code only a certain number of times. In assembly language the unconditional jmp instruction would need to be replaced by a conditional jump, such as jnz (jump if not zero).

Higher programming languages such as BASIC, C, Java, … provide a rich set of keywords to conveniently create different kinds of loops. In Java, for example, there are four different ways of creating a loop, actually there are five depending on what your definition of a loop is. Here are the most basic loops in Java.

// Example 1: while loop (top-controlled)
while( expression ) {
    // Code to be repeated while expression is true
}

// Example 2: do...while loop (bottom-controlled)
do {
    // Code to be repeated while expression is true
} while( expression );

// Example 3: for loop
for( int i = 0; i < 10; i++ ) {
    // Code to be repeated while i < 10, whereas i starts at 0
    // and is incremented after each repetition
}

The bottom-controlled do…while loop is being used whenever the code within the loop should be executed at least one time. This can be useful if you want to repeat user input until he or she has entered a valid value, for example. The for loop should only be used if you know the exact number of repetitions in advance. In other words, the exact number of repetitions should become clear to the reader of the code just by looking at the for(…) line. Never write-access your counter variable within the for loop.

The fourth type of loop in Java is called a for…each loop, although the word each does not appear as a keyword. It was introduced to make iterations over data collections (e.g. arrays) more convenient. Here is an example: If a is an array of int-values, n gets the value of each element successively.

// Example 4: for ... each loop
for( int n : a ) {
    System.out.println( n );
}

Yet another way of repeating code is Recursion. It means that a function (or method in OOP languages) invokes itself.

/**
 * Example 5: Recursion
 */

public static void m1( int n ) {
    n++;
    System.out.println( n );
    if( n >= 10 )
        return;
    else
        m1( n );
}

public static void main( String[] args ) {
    m1( 0 );
}

The example above displays the numbers from 1 to 10 (inclusively) on the screen. Recursion is close to the way our brains are thinking (“repeat the same method until a certain condition is reached”). However, it is the least efficient and most dangerous way to create a loop. Here’s why (briefly explained):

  • Each time a method is invoked, your computer has to “remember” (store) the place where to return to after the method has been executed. Local variables and other data related to the method also need to be stored.
  • Accessing memory is very time consuming, so Recursion always is a lot higher in execution time than conventional loops are.
  • The place where this data is stored is called Stack, a limited amount of memory which can overflow. In most cases it is hard (if not impossible) to predict when this overflow will occur, because it depends on many factors (e.g. the stack size of the machine that is running your program, the data types and number of local variables, …)

So you may want to avoid Recursions in your programs.

Well, that’s all for this posting.
See you later,

— Andre M. Maier

PS: Did you know that goto is a reserved keyword in Java, which is neither supported nor working?

Posted in Programming Essentials, Uncategorized | Tagged , , , | Comments Off on Loops