Category : Files from Magazines
Archive   : JAN94.ZIP
Filename : ALLEY.ASC

_ALGORITHM ALLEY_
by Tom Swan

Listing One

(* ------------------------------------------------------------------------ *(
** midsqr.pas -- Middle-Square Random Number Generator. Note: This method **
** method is considered obsolete and is listed for reference only. **
** Copyright (c) 1993 by Tom Swan. All rights reserved. **
)* ------------------------------------------------------------------------ *)
program MidSqr;
const
m4 = 10000; { 10 ^^ 4 }
m8 = 100000000; { 10 ^^ 8 }
var
Seed: LongInt;
procedure RandomInit(StartingSeed: LongInt);
begin
Seed := StartingSeed
end;
{ Square the eight-digit seed; return middle eight digits of 16-digit result. }
function RandomInt: LongInt;
var
p0, p1: LongInt;
begin
p0 := seed mod m4;
p1 := seed div m4;
Seed :=
(((p1 * p0 + p1 * p0) + (p0 * p0 div m4)) +
((p1 * p1 mod m4) * m4) ) mod m8;
RandomInt := Seed
end;
var
N: Integer;
begin
Writeln;
Writeln('Middle-Square Random Number Generator (obsolete)');
Writeln;
RandomInit(45086273);
for N := 1 to 100 do
Write(RandomInt:10);
Writeln
end.


Listing Two

(* ------------------------------------------------------------------------- *(
** longmult.pas -- Demonstrate 32-bit multiplication **
** Copyright (c) 1993 by Tom Swan. All rights reserved. **
)* ------------------------------------------------------------------------- *)
program LongMultTest;
const
m4 = 10000; { 10 ^^ 4 }
m8 = 100000000; { 10 ^^ 8 }
var
p, q, p1, p0, q1, q0: LongInt;
low, mid, high: LongInt;
begin
p := 12345678; { First value }
q := 87654321; { Second value }
p1 := p div m4;
p0 := p mod m4;
q1 := q div m4;
q0 := q mod m4;
low :=
(((p0 * q1 + p1 * q0) mod m4) * m4 + p0 * q0) mod m8;
mid :=
(((p1 * q0 + p0 * q1) +
((p0 * q0) div m4)) +
((((p1 * q1)) mod m4) * m4)) mod m8;
high :=
((((((p1 * q0 + p0 * q1) +
((p0 * q0) div m4)) +
((((p1 * q1)) mod m4) * m4)) div m4) +
((((p1 * q1)) div m4) * m4))) mod m8;
Writeln('low = ', low);
Writeln('mid = ', mid);
Writeln('high = ', high);
Writeln;
Writeln(p, ' * ', q, ' = ', high, low)
end.


Listing Three

(* ------------------------------------------------------------------------- *(
** linear.pas -- Linear Congruential Random Number Generator **
** Copyright (c) 1993 by Tom Swan. All rights reserved. **
)* ------------------------------------------------------------------------- *)
program Linear;
const
m4 = 10000; { 10 ^^ 4 }
m8 = 100000000; { 10 ^^ 8 }
b = 31415621; { constant multiplier }
var
Seed: LongInt;
I: Integer;
function LongMult(p, q: LongInt): LongInt;
var
p1, p0, q1, q0: LongInt;
begin
p1 := p div m4;
p0 := p mod m4;
q1 := q div m4;
q0 := q mod m4;
LongMult :=
(((p0 * q1 + p1 * q0) mod m4) * m4 + p0 * q0) mod m8
end;
procedure RandomInit(StartingSeed: LongInt);
begin
Seed := StartingSeed
end;
function RandomInt: LongInt;
begin
Seed := (LongMult(Seed, b) + 1) mod m8;
RandomInt := Seed
end;
function RandomRange(R: LongInt): LongInt;
begin
RandomRange := ((RandomInt div m4) * R) div m4
end;
begin
Writeln;
Writeln('Linear Congruential Random Number Generator');
Writeln;
RandomInit(1234567);
for I := 1 to 32 do
Write(RandomInt:10);
Writeln;
for I := 1 to 32 do
Write(RandomRange(32768):10);
end.


Listing Four

(* ------------------------------------------------------------------------- *(
** fibo.pas -- Fibonacci Random Number Generator **
** Copyright (c) 1993 by Tom Swan. All rights reserved. **
)* ------------------------------------------------------------------------- *)
program Fibo;
var
List: array[1 .. 17] of WORD;
I, J: Integer;
procedure RandomInit;
var
N: Integer;
begin
List[17] := 1;
List[16] := 2;
for N := 15 downto 1 do
List[N] := List[N+1] + List[N+2];
I := 17;
J := 5
end;
function RandomInt: WORD;
var
K: WORD;
begin
K := List[I] + List[J];
List[I] := K;
I := I - 1;
J := J - 1;
if I = 0 then I := 17;
if J = 0 then J := 17;
RandomInt := K
end;
var
N: Integer;
begin
Writeln;
Writeln('Fibonacci Random Number Generator');
Writeln;
RandomInit;
for N := 1 to 100 do
Write(RandomInt:10);
Writeln
end.


Listing Five

(* ------------------------------------------------------------------------- *(
** combine.pas - Combination Random Number Generator. Combines Algorithm #16 **
** (Linear Congruential Random Number Generator) with #17 (Fibonaccii Random **
** Number Generator) to create a table-driven combination generator. **
** Copyright (c) 1993 by Tom Swan. All rights reserved. **
)* ------------------------------------------------------------------------- *)
program Combine;
const
m4 = 10000; { 10 ^^ 4 }
m8 = 100000000; { 10 ^^ 8 }
b = 31415621; { constant multiplier }
maxIndex = 100; { array of Values }
var
List: array[1 .. 17] of WORD;
Values: array[1 .. maxIndex] of LongInt;
I, J: Integer;
Seed: LongInt;
function LongMult(p, q: LongInt): LongInt;
var
p1, p0, q1, q0: LongInt;
begin
p1 := p div m4;
p0 := p mod m4;
q1 := q div m4;
q0 := q mod m4;
LongMult :=
(((p0 * q1 + p1 * q0) mod m4) * m4 + p0 * q0) mod m8
end;
function LinearRandomInt: LongInt;
begin
Seed := (LongMult(Seed, b) + 1) mod m8;
LinearRandomInt := Seed
end;
procedure RandomInit(StartingSeed: LongInt);
var
N: Integer;
begin
Seed := StartingSeed;
List[17] := 1;
List[16] := 2;
for N := 15 downto 1 do
List[N] := List[N+1] + List[N+2];
I := 17;
J := 5;
for N := 1 to maxIndex do
Values[N] := LinearRandomInt
end;
function FiboRandomInt: WORD;
var
K: WORD;
begin
K := List[I] + List[J];
List[I] := K;
I := I - 1;
J := J - 1;
if I = 0 then I := 17;
if J = 0 then J := 17;
FiboRandomInt := K
end;
function RandomRange(R: LongInt): LongInt;
var
V: Integer;
begin
V := 1 + (FiboRandomInt mod 100);
RandomRange := ((Values[V] div m4) * R) div m4;
Values[V] := LinearRandomInt
end;
var
N: Integer;
begin
Writeln;
Writeln('Combination Random Number Generator');
Writeln;
RandomInit(7654321);
for N := 1 to 1000 do
Write(RandomRange(65536):10)
end.


Example 1: Pseudocode for Algorithm #15 (middle-square method,
obsolete)

const
m4 = 10000;
m8 = 100000000;
var
Seed: Integer

function NextRandom: Integer;
begin
Seed <- ((Seed * Seed) / m4) mod m8;
NextRandom <- Seed;
end;



Example 2: Pseudocode for Algorithm #16 (linear-congruential
method)

const
m4 = 10000;
m8 = 100000000;
b = 31415621;

r = 65536;
var
Seed: Integer

function NextRandom: Integer;
begin
Seed <- ((Seed * b) + 1) mod m8;
NextRandom <- ((Seed / m4) * r) div m4;
end;


Example 3: Pseudocode for Algorithm #17 (Fibonacci method)

var
List: array[1 .. 17] of WORD;
I, J: Integer;


function NextRandom: Integer;
var
K: Integer;
begin
K <- List[I] + List[J];
List[I] <- K;
I <- I - 1;
J <- J - 1;
if I = 0 then I <- 17;
if J = 0 then J <- 17;
NextRandom <- K;
end;