A very long time in the past I ported the Mersenne Tornado pseudo-random quantity generator to pl/sql. That algorithm, and my port, are displaying their age so I began different mills. A more moderen method is discovered within the xoshiro/xoroshiro household by David Blackman and Sebastiano Vigna discovered right here.
I’ve chosen xoshiro256** as certainly one of their “all-purpose, rock-solid
mills”. Just like the Mersenne Tornado, the unique supply is written in c and makes use of quite a few bit manipulations to generate new values from the prior ones.
Whereas PL/SQL has the BITAND operate, it doesn’t have any others that immediately apply to numeric sorts. It could have been attainable to make use of RAW values and the UTL_RAW bundle, however I discovered it simpler to maintain true to the unique implementation by creating my very own bit-wise OR, XOR, shift, and rotation capabilities.
Implementing 64-bit integer subtype (virtually)
One other complexity is that c has the uint64_t kind. That’s, a 64-bit unsigned integer. Whereas PL/SQL NUMBER sorts can maintain such values, their is not any direct correlation. Ideally I’d create an integer subtype constrained with a RANGE clause of 0..18446744073709551615 (2^64-1). Nonetheless, there isn’t a authorized syntax to assist that definition. As of 23ai, the RANGE clause solely applies to subtypes of PLS_INTEGER which is, itself, restricted to signed 32-bit values. So I settled for a 20-digit integer utilizing:
SUBTYPE uint64_t IS NUMBER(20, 0)
Then, in my calculations I apply a 64-bit masks to make sure overflows are dealt with in a approach that mimics the c uint64_t.
Bit-wise operators
As talked about above, among the c syntax has no corresponding pl/sql operator or operate. Specifically:
- | – OR
- ^ – XOR
- >> – Shift proper
Luckily, BITAND and arithmetic is enough to create OR and XOR. Multiplying or dividing by powers of two will replicate bit shifts left or proper respectively.
FUNCTION bitor(p_a IN uint64_t, p_b IN uint64_t)
RETURN uint64_t
IS
BEGIN
RETURN BITAND(p_a + p_b - BITAND(p_a, p_b), c_64bitmask);
END bitor;
FUNCTION bitxor(p_a IN uint64_t, p_b IN uint64_t)
RETURN uint64_t
IS
BEGIN
RETURN BITAND((p_a + p_b) - (BITAND(p_a, p_b) * 2), c_64bitmask);
END bitxor;
FUNCTION shl64(p_n IN uint64_t, p_bits IN bits_t)
RETURN uint64_t
IS
BEGIN
-- Apply 64-bit masks to make sure outcomes are inside correct vary
RETURN CASE p_bits WHEN 0 THEN p_n ELSE BITAND(p_n * (2 ** p_bits), c_64bitmask) END;
END shl64;
FUNCTION shr64(p_n IN uint64_t, p_bits IN bits_t)
RETURN uint64_t
IS
BEGIN
-- Apply 64-bit masks to make sure outcomes are inside correct vary
RETURN CASE p_bits WHEN 0 THEN p_n ELSE BITAND(p_n / (2 ** p_bits), c_64bitmask) END;
END shr64;
It wasn’t technically essential to make use of a CASE for shifts of 0 bits, nevertheless it appeared extra pure to seize that particular case fairly than pressure the additional math steps to provide a consequence we already knew. That is merely a choice on my half and each shl64 and shr64 could possibly be simplified to let 0 run the identical as some other shift worth. Additionally of observe, each of the shift capabilities apply the 64-bit masks to make sure there the outcomes at all times fall within the supposed 0-18446744073709551615 vary.
The final particular bit operation is rotation, the xoshiro code itself consists of the rotl logic which might then be transformed to PL/SQL utilizing the capabilities above:
FUNCTION rotl(p_x uint64_t, p_k IN bits_t)
RETURN uint64_t
IS
-- static inline uint64_t rotl(const uint64_t x, int okay) {
-- return (x > (64 - okay));
-- }
BEGIN
RETURN CASE WHEN p_k = 0 THEN p_x ELSE bitor(shl64(p_x, p_k), shr64(p_x, 64 - p_k)) END;
END rotl;
Pulling all of it collectively
With the bit operations set, implementing the capabilities was pretty straight ahead. There are a number of arrays used throughout the unique c code which I initially applied as varrays, nevertheless it felt synthetic to maintain adjusting the varray indexes to be 1-based vs the 0-based arrays. So, as a substitute, I made a decision to make use of an associative arrays with indexes restricted to 0,1,2,3. The total bundle follows:
CREATE OR REPLACE PACKAGE xoshiro256
IS
-- Based mostly on xoshiro256** by by David Blackman and Sebastiano Vigna
-- unique https://prng.di.unimi.it/xoshiro256starstar.c
-- .///.
-- (0 o)
---------------0000--(_)--0000---------------
--
-- Sean D. Stuber
-- sean.stuber@gmail.com
--
-- oooO Oooo
--------------( )-----( )---------------
-- ( ) /
-- _) (_/
-- It could be good to outline an express RANGE 0.. 18446744073709551615 for the subtype
-- however as of 23ai, solely subtypes of PLS_INTEGER might have a variety.
SUBTYPE uint64_t IS NUMBER(20, 0);
TYPE seed_tab IS TABLE OF uint64_t;
PROCEDURE set_state(p_seed IN seed_tab);
FUNCTION get_next
RETURN uint64_t;
PROCEDURE bounce;
PROCEDURE long_jump;
END;
CREATE OR REPLACE PACKAGE BODY sds.xoshiro256
IS
-- TO_NUMBER('ffffffffffffffff', 'xxxxxxxxxxxxxxxx') = 18446744073709551615 = 2^64-1
c_64bitmask CONSTANT uint64_t := POWER(2, 64) - 1; -- 18446744073709551615
SUBTYPE bits_t IS PLS_INTEGER RANGE 0 .. 63;
SUBTYPE array_index_t IS PLS_INTEGER RANGE 0 .. 3;
TYPE state_array_t IS TABLE OF uint64_t
INDEX BY array_index_t;
g_state state_array_t;
FUNCTION bitor(p_a IN uint64_t, p_b IN uint64_t)
RETURN uint64_t
IS
BEGIN
RETURN BITAND(p_a + p_b - BITAND(p_a, p_b), c_64bitmask);
END bitor;
FUNCTION bitxor(p_a IN uint64_t, p_b IN uint64_t)
RETURN uint64_t
IS
BEGIN
RETURN BITAND((p_a + p_b) - (BITAND(p_a, p_b) * 2), c_64bitmask);
END bitxor;
FUNCTION shl64(p_n IN uint64_t, p_bits IN bits_t)
RETURN uint64_t
IS
BEGIN
-- Apply 64-bit masks to make sure outcomes are inside correct vary
RETURN CASE p_bits WHEN 0 THEN p_n ELSE BITAND(p_n * (2 ** p_bits), c_64bitmask) END;
END shl64;
FUNCTION shr64(p_n IN uint64_t, p_bits IN bits_t)
RETURN uint64_t
IS
BEGIN
-- Apply 64-bit masks to make sure outcomes are inside correct vary
RETURN CASE p_bits WHEN 0 THEN p_n ELSE BITAND(p_n / (2 ** p_bits), c_64bitmask) END;
END shr64;
FUNCTION rotl(p_x uint64_t, p_k IN bits_t)
RETURN uint64_t
IS
-- static inline uint64_t rotl(const uint64_t x, int okay) {
-- return (x > (64 - okay));
-- }
BEGIN
RETURN CASE WHEN p_k = 0 THEN p_x ELSE bitor(shl64(p_x, p_k), shr64(p_x, 64 - p_k)) END;
END rotl;
FUNCTION get_next
RETURN uint64_t
IS
-- uint64_t subsequent(void) {
-- const uint64_t consequence = rotl(s[1] * 5, 7) * 9;
--
-- const uint64_t t = s[1] TO_NUMBER('180ec6d33cfd0aba', 'xxxxxxxxxxxxxxxx'),
1 => TO_NUMBER('d5a61266f0c9392c', 'xxxxxxxxxxxxxxxx'),
2 => TO_NUMBER('a9582618e03fc9aa', 'xxxxxxxxxxxxxxxx'),
3 => TO_NUMBER('39abdc4529b1661c', 'xxxxxxxxxxxxxxxx')) ;
v_s0 uint64_t := 0;
v_s1 uint64_t := 0;
v_s2 uint64_t := 0;
v_s3 uint64_t := 0;
v_dummy uint64_t;
BEGIN
FOR i IN 0 .. 3
LOOP
FOR b IN 0 .. 63
LOOP
IF BITAND(v_jump(i), shl64(1, b)) != 0
THEN
v_s0 := bitxor(v_s0, g_state(0));
v_s1 := bitxor(v_s1, g_state(1));
v_s2 := bitxor(v_s2, g_state(2));
v_s3 := bitxor(v_s3, g_state(3));
END IF;
v_dummy := get_next;
END LOOP;
END LOOP;
g_state(0) := v_s0;
g_state(1) := v_s1;
g_state(2) := v_s2;
g_state(3) := v_s3;
END bounce;
PROCEDURE long_jump
IS
-- /* That is the long-jump operate for the generator. It's equal to
-- 2^192 calls to subsequent(); it may be used to generate 2^64 beginning factors,
-- from every of which bounce() will generate 2^64 non-overlapping
-- subsequences for parallel distributed computations. */
--
-- void long_jump(void) {
-- static const uint64_t LONG_JUMP[] = { 0x76e15d3efefdcbbf, 0xc5004e441c522fb3, 0x77710069854ee241, 0x39109bb02acbe635 };
--
-- uint64_t s0 = 0;
-- uint64_t s1 = 0;
-- uint64_t s2 = 0;
-- uint64_t s3 = 0;
-- for(int i = 0; i TO_NUMBER('76e15d3efefdcbbf', 'xxxxxxxxxxxxxxxx'),
1 => TO_NUMBER('c5004e441c522fb3', 'xxxxxxxxxxxxxxxx'),
2 => TO_NUMBER('77710069854ee241', 'xxxxxxxxxxxxxxxx'),
3 => TO_NUMBER('39109bb02acbe635', 'xxxxxxxxxxxxxxxx')) ;
v_s0 uint64_t := 0;
v_s1 uint64_t := 0;
v_s2 uint64_t := 0;
v_s3 uint64_t := 0;
v_dummy uint64_t;
BEGIN
FOR i IN 0 .. 3
LOOP
FOR b IN 0 .. 63
LOOP
IF BITAND(v_longjump(i), shl64(1, b)) != 0
THEN
v_s0 := bitxor(v_s0, g_state(0));
v_s1 := bitxor(v_s1, g_state(1));
v_s2 := bitxor(v_s2, g_state(2));
v_s3 := bitxor(v_s3, g_state(3));
END IF;
v_dummy := get_next;
END LOOP;
END LOOP;
g_state(0) := v_s0;
g_state(1) := v_s1;
g_state(2) := v_s2;
g_state(3) := v_s3;
END long_jump;
PROCEDURE set_state(p_seed IN seed_tab)
IS
BEGIN
g_state := state_array_t();
FOR i IN 0 .. 3
LOOP
g_state(i) := p_seed(i + 1);
END LOOP;
END set_state;
END;
Choosing a set of fine seed values assist construct higher distributions within the generated sequence. For the needs of illustration although, I’ll use a easy 12345 in every of the seed array components after which generate 10 values with get_next, then bounce and generate 10 extra and at last do a long_jump and generate a last set of 10. This easy framework allowed me to confirm my logic in opposition to the unique doing the identical steps.
DECLARE
x xoshiro256.uint64_t;
BEGIN
xoshiro256.set_state(xoshiro256.seed_tab(12345, 12345, 12345, 12345));
FOR i IN 0 .. 9
LOOP
x := xoshiro256.get_next;
DBMS_OUTPUT.put_line(TO_CHAR(i, '9') || ' ' || LPAD(TO_CHAR(x), 20) || ' ' || TO_CHAR(x, 'xxxxxxxxxxxxxxxx'));
END LOOP;
DBMS_OUTPUT.put_line('--- bounce ---');
xoshiro256.bounce;
FOR i IN 0 .. 9
LOOP
x := xoshiro256.get_next;
DBMS_OUTPUT.put_line(TO_CHAR(i, '9') || ' ' || LPAD(TO_CHAR(x), 20) || ' ' || TO_CHAR(x, 'xxxxxxxxxxxxxxxx'));
END LOOP;
DBMS_OUTPUT.put_line('--- lengthy bounce ---');
xoshiro256.long_jump;
FOR i IN 0 .. 9
LOOP
x := xoshiro256.get_next;
DBMS_OUTPUT.put_line(TO_CHAR(i, '9') || ' ' || LPAD(TO_CHAR(x), 20) || ' ' || TO_CHAR(x, 'xxxxxxxxxxxxxxxx'));
END LOOP;
END;
This produced the next sequences…
0 71107200 43d0280 1 71107200 43d0280 2 9320162918400 87a05000000 3 9320234025600 87a093d0280 4 12773345438245847175 b1440a0000000087 5 12768617581213858983 b1333e0a010f3ca7 6 8945543092777141728 7c24f40c1fee45e0 7 470016407425146078 685d56eab2e5cde 8 3493524090943047400 307b7da6b6ee06e8 9 5886979323815290452 51b2c08124146654 --- bounce --- 0 4581861990845984958 3f960b34763d30be 1 6555207914207083891 5af8c6ddf3247d73 2 1155739510168040853 100a02f60c733595 3 17756807916997691290 f66cdab88d7dc79a 4 18120637618276044033 fb796fe814ec8d01 5 3601654045701872973 31fba545ade89d4d 6 1200605674697995402 10a9688003b1348a 7 2838098080646629052 2762f32adea906bc 8 13449286687953663012 baa576fc3dde3424 9 5139522055796585030 47534014530a7246 --- lengthy bounce --- 0 308148744041885595 446c3a66a996f9b 1 1534996402541018053 154d671868f5bbc5 2 2575119349696104759 23bca967acdf0937 3 1204256562158620046 10b660f67de5cd8e 4 2485655289488877646 227ed250f40e284e 5 2705313921121906326 258b34ad8a63ee96 6 14047681829789752210 c2f364324653db92 7 8712759958851592880 78e9f1053898a2b0 8 16323705335360483007 e28973840c4f6ebf 9 2581999948191718881 23d51b45da0b5de1
This was a enjoyable little train. Finally I’d prefer to increase on it to implement different variations within the xoshiro/xoroshiro suite in addition to embrace assist for splitmix64 as a approach to assist begin with higher seed values.
Questions and feedback, as at all times, are welcome.
