Complex ? Not so...




Hi ! We meet again ! Ready to step to this chapter ? This time, we're going to discuss complex data type. One of it has been discussed, record. As I promised in chapter 7, I would certainly explain thoroughly all the weirdos.

It all begins with type. It is not necessarily before var section, but if you want to use it as a new variable type, you MUST place it before the var section.

Let's analogue this to the record we have discussed. Record simply declared in type section and then we can freely use it as if it is a new variable type. You CAN define new variable types. Look at these examples :


type
   car        = (Honda, Toyota, Mercedes, Volvo, Ford);
   chesspiece = (King, Queen, Rook, Bishop, Knight, Pawn);
   str20      = string[20];
   byteptr    = ^byte;  { This kind of type will be discussed on lesson 2 }

var
  name  : str20;
  mycar : car;
  piece : array [1..32] of chesspiece;
  look  : byteptr;

Let's examine str20=string[20]; Variable name is a str20 type. It means that name is a string variable of 20 characters. We knew that string can be limited in length, but this type can't. You can use name as if it is a normal string variable.

Look at car and chesspiece types. Is it true ? Yes, it IS. Actually, they are treated as integers. These kind of variables are called enumerated types. You can not assign integers to mycar and to piece. You assign their rightful contents instead. Example :



begin
  mycar:=1;            { Illegal }
  mycar:=Honda;        { Legal }
  if mycar=Volvo then  { Legal }
  begin
    clrscr; writeln('I have a volvo');
  end;
  piece[1]:=Pawn;      { Legal }
end.

Is it true that compiler treat it as an integer ? Yes, it is. Therefore, Pascal provides these commands : Ord, Pred, Succ. Ord is used to know their integer contents. So :


   Ord(Honda) = 0, Ord(Toyota) = 1, Ord(Mercedes) = 2, Ord(Volvo) = 3,
   Ord(Ford)  = 4.

   Ord(King) = 0, Ord(Queen) = 1, Ord(Rook) = 2, Ord(Bishop) = 3, and so on

Ord can also be used to get the ASCII number of a character, example :

  n:=Ord('A');      { n = 65 }

Pred is used to decrement the enumerated types. It is similar to Dec.

  n:=Pred(Ford);    { n = Volvo }         Dec(x);  { x := x - 1 }
  n:=Pred(Bishop);  { n = Rook  }

  x:=Toyota;
  n:=Pred(x);       { n = Honda }

Succ is the complement : incrementing enumerated types. Similar to Inc.

  n:=Succ(Mercedes); { n = Volvo }        Inc(x);  { x := x + 1 }
  x:=Rook;
  n:=Succ(x);        { n = Bishop }

Easy, right ?? Now, let's look at this special feature :


type
  car = (Honda=1, Toyota, Fiat, Ford=5, Volvo=7, Mercedes);

And look at this :


  Ord(Honda)    = 1
  Ord(Toyota)   = 2
  Ord(Fiat)     = 3
  Ord(Ford)     = 5
  Ord(Volvo)    = 7
  Ord(Mercedes) = 8

Got what I mean ? You can do that instead of creating constants for similar behavior. This really makes codes more readable.

Yup, this is a short chapter. So, I decided to give extras :

Random number generator !

It is a very theoritic, but I'll make it short and fun. Stripped down any unnecessary theory.

Actually, computer is a deterministic machine. What does that mean ? It means that it could not do everything itself. Instead, it only does what the program wants. So, there is NO random generator. People simulate it. Therefore comes a jargon pseudorandom number.

Wait a minute ... how could people simulate it ? Well, look at the following idea :

  1. Von Neumann idea about squaring numbers and have some digits of them. It is obsolete and has many weakness. So, don't bother to discuss it.
  2. Lehmer idea about linear function. This is brilliant, but it has weakness. If we don't handle it carefully, it may fall into disrandomness.

OK, look at Lehmer's idea. His idea can be formulated as this :

xn+1 = ( a xn + c ) mod m

Where a, c, and m are predefined constants; n is the index.

A pretty easy and straight-forward function to implement. It has several weakness. Three of them are :

  1. Need a number to start with.
  2. If we don't choose a, c, and m carefully, that function may fall into disrandomness.
  3. The coming number may be negative, as the formula neglects negative numbers.

ad. 1.

The number to start with is called the seed (x0). If we choose the same seed, it generates the same sequence of numbers. Suppose a, c, and m is 9, 5, and 8 consequently. If we always take the seed (x0) 0, what we all get is the same sequence of : 5, 2, 7, 4, 7, ... The solution is that we must take different seed everytime. How ? Ask user to define the seed ? No way ! That's why we must start every random generator with randomize. Randomize simply select a seed. The seed is taken from timer ticks, which is always incremented each time. No one ever knows how much is it. The only thing for sure is that it always change. Now try this program : (Program 1)


uses crt;
var
  i : byte;
begin
  clrscr;
  randomize;
  for i:=1 to 20 do write(random(100):8);
  readkey;
end.

Run it for several times and inspect the sequence of numbers displayed on screen carefully. It always change everytime you run it, right ? Now, remove the randomize. Run it for several times and inspect the sequence of numbers. You see that without randomize, every time you run the program, you will find the same sequence. This is the weakness. Got what I mean ?

ad. 2.

Well, random function in Borland Pascal, or many other programs seem to have chosen a, c, and m quite good so that the generated numbers seemed random. Well, the implementation in the program is :
(Program 2)


var
  seed : longint;

procedure myrandomize;
begin
  seed:=meml[0040:006c];  { This how to get timer ticks }
end;

function myrandom (howbig:word) : word;
begin
  seed:=(seed*a+c) mod m;
  myrandom:=seed mod howbig;
end;

Add the myrandomize and myrandom routines into program 1. Then, replace all random and randomize with myrandom and myrandomize. Think about nice number for a, c, and m. Then run it for several times. See the problem ?

OK, the common problems are :

  1. Non random sequence, like this :
    0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, ...
    2, 4, 6, 8, 0, 2, 4, 6, 8, 0, ...
  2. We've got a repeating short sequence, like this :
    3, 4, 7, 3, 4, 7, 3, 4, 7, ...
    4, 5, 4, 5, 4, 5, ...
    3, 9, 2, 6, 7, 3, 9, 2, 6, 7, ...
    No ! It's not a random generator ! It's a sequence generator !
  3. Good sequence, but ended with the same short sequence, or even the same number, like this :
    10, 11, 11, 11, 11, 11 ....
    5, 2, 7, 4, 7, 4, 7, 4, 7, 4, ...
    Well, needless to say, it's definitely not a random generator.
  4. Incrementing sequence. It's known as Lattice problem, like this :
    3, 4, 7, 6, 7, 10, 9, 10, 13, 12, 13, 16, ...
    See ? It may seem random, but let's look at this arrangement :
    3, 4, 7,
    6, 7, 10,
    9, 10, 13,
    12, 13, 16, ...
    Got what I mean ? It is the same sequence, but just adding all of them with three, then start over again. Again : It's not a random number !

The number of sequence before it started over again is called the period.

SequencePeriod
3, 4, 7, 3, 4, 7, 3, 4, 7, ...
3
10, 11, 11, 11, 11, ...
1
3, 9, 2, 6, 7, 3, 9, 2, 6, 7, ...
5

To get a good random sequence is that it seems that the nevers reoccurs, it is simply generate new, erratic number. In order to make that 'illusion', we must generate a sequence with a very very long period.

The period is closely related to m. The period never exceed m, so that we must give m a very big value, say 2,000,000,000. A good random number generator has a random sequence with period of m.

Now, take a time, choose your a, c, and m. Here's a hint :
let m be 2,147,483,647
let c be 1
let a be 16807
This was from S.K. Park and L.W. Miller research in 1988.

It's quite good. Try it ! We've still get 2 problems more :

  1. Multiplication overflow.
  2. Signed bit set.
  1. Multiplication overflow.
    We could handle it by using mathematical method. Most of the times you may ignore the overflow. It will not have much effect on your numbers. So, you may skip this if you want to. Yes, yes, I understand your reason why we should care about this. But it seldom happens. The idea is from multiplicative attitude :
    
                 x * (a+b) = x * a + x * b
       
    Suppose n is a+b. You should divide n into 2 numbers right ? If you have a divisor (any number), called y, n could be easily divided into a and b which are :
                 a = (n div y) * y
                 b = n mod y
       
    Then we replace it with a and b :
    
                 x * n = x * y * (n div y) + x * (n mod y)
       
    It's pretty tricky. You must choose y so that x * y * (n div y) will not overflow. So, what's the point ? We see that seed*a may cause overflow. Hence, you must replace it into :
    
                 seed * a = a * y * (seed div y) + a * (seed mod y)
       
    Yes, but you shall never implement this directly. We know that it is still cause an overflow. How can it be done ? We know that a * (seed mod y) will never cause overflow if a * y is always ways less than maximum limit of the long integer. The maximum limit of long integer is 2,147,483,647, we call it MAX_LONGINT. To check whether the equation causes overflow, we do this :
    
                 temp = MAX_LONGINT - a * (seed mod y)
       
    If temp is less than a * y * (seed div y) means that it WILL cause overflowing. So, you may wonder how it can be overcome. Suppose :
    
                 z = a * (seed div y)
       
    Then, you may easily guess :
    
                 (z - temp / y) * y
       
    Will not cause overflow. Yup, wait a minute Sherlock ! temp / y is a rational number, the compiler will complain ! How can we get rid of it ? We change the equation above to :
    
                 (z - temp div y) * y - temp mod y
       
    Phew ! Pretty lengthy, huh ? So, how is the final equation like ?
    
          seed * a = (z - temp div y) * y - (temp mod y) + a * (seed mod y)
       
    OK ! OK ! You are bored, so that how could we implement this into program ? Watch this :
    function random (howbig : word) : word;
    const
      a           = 16807;
      c           = 1;
      m           = 2147483647;
      y           = m div a;     { suppose to be 127773 }
      MAX_LONGINT = 2147483647;  { same as m }
    var
      z, temp : longint;
    begin
      z    := a * (seed div y);
      temp := MAX_LONGINT - a * (seed mod y);
    
      { seed := seed * a + c  }
      seed := (z - temp div y) * y - (temp mod y) + a * (seed mod y) + c;
      
      { set loopback for seed }
      if seed < 0 then seed := seed + MAX_LONGINT;
    
      seed := seed mod m;
    
      myrandom := seed mod howbig;
    end;
    

    That's it ! You may wonder what if for is. Well, it does tackle the second problem. Here is the explanation. You may just rip that code and never know what the inside.
  2. Signed bit set.
    In our talk just now, we assume that a * y * (seed div y) is always causing overflow. If it doesn't, means that :
    
                  (z - temp div y) * y - (temp mod y)
       
    will always be negative. We don't want negative seed here since it will be catastrophic. Why is it called SIGNED BIT SET ? It is because to differ a number from negative to positive, computer only use sign bit. If it is a negative, the sign bit set (on), when it is positive, it is cleared (off).
    So, how to cure this ? Easy, just add it with MAX_LONGINT, and we should have got rid of it. This will certainly clear off the sign bit.

This Lehmer's function is adequate for daily purposes. For scientific ones, it may not be enough. Therefore, there is another method called Uniform Random Deviates, invented by Paul L'Ecuyer. We would not discuss it now, since it is quite complicated. But you know that the Lehmer's above will have a period of 2,147,483,647. Uniform Random Deviates will create a period of about 108 !! Quite a slam bang ! Even this period is not enough for scientific uses ! However, combining both will result a period about 2,3 x 1018 ! It should be adequate for just any purposes.

How can we implement random numbers to generate :

  1. Fraction from 0 to 1 ?
    Suppose you have a function of srand, that generates such fraction :
           function srand:real;
           { everything is just the same as myrandom function except
             myrandom := seed mod howbig; is changed into : }
    
           myrandom:= seed / MAX_LONGINT;
    

  2. Integers from a to b ?
    Suppose you have a function of rand, that generates such integer :
           function rand(lower, upper : word): word;
           { everything is just the same as myrandom function except
             myrandom := seed mod howbig; is changed into : }
    
           myrandom:= lower + (seed mod (upper - lower + 1));
    

Actually, there are a lot more to discuss : Random table, Random number with no duplication, scrambling arrays, etc. But I think you had enough for this time. So, adios amigos, my friend ! See ya on the quiz !


Where to go ?

Back to main page
Back to Pascal Tutorial Lesson 1 contents
To the quiz
Back to Chapter 9 about records
To Chapter 11 about sets
My page of programming link
Contact me here


By : Roby Joehanes, © 1997, 2000