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 :
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 :
OK, look at Lehmer's idea. His idea can be formulated as this :
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 :
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 ?
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 :
The number of sequence before it started over again is called the period.
| Sequence | Period |
|---|---|
| 3, 4, 7, 3, 4, 7, 3, 4, 7, ... | |
| 10, 11, 11, 11, 11, ... | |
| 3, 9, 2, 6, 7, 3, 9, 2, 6, 7, ... |
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 :
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;
(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).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 :
function srand:real;
{ everything is just the same as myrandom function except
myrandom := seed mod howbig; is changed into : }
myrandom:= seed / MAX_LONGINT;
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