Can someone translate the code below to VBA?

TIA


/*

COMBO

a simple but very good combination generator.
It combines, by addition mod 2^32,
x(n)=x(n-1)*x(n-2) mod 2^32
and
y(n)=30903*y(n-1) + carry mod 2^16
The period of the first is 3*2^29, on odd integers, and the
period of the second, a multiply-with-carry generator, is
30903*2^15-1=1012629503, so the period of combo exceeds 2^60.
This generator is simple to program in Fortran or C and quite
fast.

*/

/*
Simple combo, period 2^60.5
x(n)=x(n-1)*x(n-2) mod 2^32 added to
period of x(n)=x(n-1)*x(n-2) is 3*2^29 if both seeds are
odd, and one is +or-3 mod 8.
easy to ensu replace seed x with 8*seed+3, and y with 2*seed+1
*/


#define ulong unsigned long

static ulong combo_x = 3;
static ulong combo_y = 1;
static ulong combo_z = 1;
static ulong combo_v;

void seed_rand_combo(ulong seed) {
combo_x = seed * 8 + 3;
combo_y = seed * 2 + 1;
combo_z = seed | 1;
}

ulong rand_combo(void) {
combo_v = combo_x * combo_y;
combo_x = combo_y;
combo_y = combo_v;
combo_z = (combo_z & 65535) * 30903 + (combo_z 16);
return combo_y + combo_z;
}

What is the source of this algorithm? What properties are claimed for
it besides a long period?

Note that a long period does not guarantee a good RNG. For instance,
the sequence 0,1,2,3,... implemented in the VBA decimal data type would
have an even longer period, but is not very random. This algorithm is
clearly more random than that trivial example, but without knowing the
results of various tests, it is unclear whether it is really "very good".

This algorithm does not translate well into VBA. Its efficiency depends
critically on language features that are not present in VBA. You would
do better to compile it in C as a .dll and call it from there.

VBA does not support an Unsigned Long data type, so you would have to
use either the Double or Decimal data type with modulo reductions. The
algorithm relies on Unsigned Long wrapping around on itself, i.e. that
4294967295 + x = x - 1
Not only will you have to use modulo reductions, but if you use Double
data type, then you will have to take extra care with combo_x*combo_y
else it will overflow the Double precision within the first 10 calls.

Less severe lost efficiencies include
seed | 1
a bitwise OR that returns seed if seed is odd or seed+1 if seed is even.
combo_z & 65535
a bitwise AND that efficiently returns MOD(combo_z,65536).
combo_z 16
a right bit shift that efficiently returns FIX(combo_z/65536)

The modulo reductions have to be done manually, because the Unsigned
Long range exceeds the reliable working range of both the VBA and
worksheet MOD functions
http://groups.google.com/groups?thre...gp13.phx .gbl

That said, here is a (very slow) VBA translation. Perhaps someone knows
some tricks to do it more efficiently.

Jerry

Public combo_x As Double
Public combo_y As Double
Public combo_z As Double
Public combo_v As Double

Sub seed_rand_combo(seed As Double)
seed = Fix(Abs(seed))
combo_x = seed * 8 + 3
combo_x = combo_x - Fix(combo_x / 4294967296#) * 4294967296#
combo_y = seed * 2 + 1
combo_y = combo_y - Fix(combo_y / 4294967296#) * 4294967296#
combo_z = Fix(seed / 2) * 2 + 1
combo_z = combo_z - Fix(combo_z / 4294967296#) * 4294967296#
End Sub

Function rand_combo() As Double
If combo_v = 0 Then Call seed_rand_combo(0#)
Dim a As Double, b As Double, c As Double, d As Double
a = Fix(combo_x / 65536)
b = combo_x - a * 65536
c = Fix(combo_y / 65536)
d = combo_y - c * 65536
' combo_x = a*2^16 + b
' combo_y = c*2^16 + d
' combo_x*combo_y = a*c*2^32 + (b*c+a*d)*2^16 + b*d
' combo_v = combo_x * combo_y mod 2^32
combo_v = (b * c + a * d) * 65536 + b * d
combo_v = combo_v - Fix(combo_v / 4294967296#) * 4294967296#
combo_x = combo_y
combo_y = combo_v
combo_z = (combo_z - Fix(combo_z / 65536) * 65536) * 30903 _
+ Fix(combo_z / 65536)
rand_combo = combo_y + combo_z
rand_combo = rand_combo - Fix(rand_combo / 4294967296#) * _
4294967296#
End Function

DiZzY wrote:

Can someone translate the code below to VBA?

TIA


/*

COMBO

a simple but very good combination generator.
It combines, by addition mod 2^32,
x(n)=x(n-1)*x(n-2) mod 2^32
and
y(n)=30903*y(n-1) + carry mod 2^16
The period of the first is 3*2^29, on odd integers, and the
period of the second, a multiply-with-carry generator, is
30903*2^15-1=1012629503, so the period of combo exceeds 2^60.
This generator is simple to program in Fortran or C and quite
fast.

*/

/*
Simple combo, period 2^60.5
x(n)=x(n-1)*x(n-2) mod 2^32 added to
period of x(n)=x(n-1)*x(n-2) is 3*2^29 if both seeds are
odd, and one is +or-3 mod 8.
easy to ensu replace seed x with 8*seed+3, and y with 2*seed+1
*/


#define ulong unsigned long

static ulong combo_x = 3;
static ulong combo_y = 1;
static ulong combo_z = 1;
static ulong combo_v;

void seed_rand_combo(ulong seed) {
combo_x = seed * 8 + 3;
combo_y = seed * 2 + 1;
combo_z = seed | 1;
}

ulong rand_combo(void) {
combo_v = combo_x * combo_y;
combo_x = combo_y;
combo_y = combo_v;
combo_z = (combo_z & 65535) * 30903 + (combo_z 16);
return combo_y + combo_z;
}

George Marsaglia mentioned this generator in the documentation for his Random Number CDROM
http://www.isds.duke.edu/~rlw/marsaglia/cdmake.ps
where he notes that it seems to pass all tests in his DIEHARD battery. Thus it apparently is a "very good" generator.

In that document, he neither claims credit nor lists a source for this algorithm. Therefore I would still be interested in information about its source.

--
Jerry
Excel MVP


"Jerry W. Lewis" wrote:

What is the source of this algorithm? What properties are claimed for
it besides a long period?