1) copy the array in ArrayTemp
2) grab a random number in the interval 0..[:len $ArrayTemp]
3) pick the item from the array
4) reconcatenate the array to eliminate the picked item
when the [:len array]=0 i had picked all values.
The prng used is an implementation of Marsaglia's MWC (semi-implementation because it uses floats). The big random number was modulo-normalized to the wanted interval. I only could get very poor distribution, only a little better if iterated a few times taking the result and xoring it with the seeds but to get acceptable results it costed too much cpu.
I turned then to an LFSR, and i'm pleased with the results, works faster and has better (apparent) randomization, doesn't need filters on its results nor any operation on arrays except for grabbing each time a unique value between 0 and [:len array]. It will initialize and give exactly all the numbers in a permutation of the interval, only one time.
The LFSR can be improved, especially the seeding and finding some nondeterministic way to traverse the sequence just one time and then stop, and also to not have a sequence truncated in the first run. I couldn't find solutions for these (and have to resume the main program) so for now i just put some ifs here and there to catch them. OTOH the central part, where the operations on the register are carried, is done using an optimal functional branch to decide whether to apply the tapmask, and that compensates for the extra fluff.
The time required (running inside a VM in an amd X2 1.7Ghz) for generating a 0..16384 sequence was 00:01:29.642229. I look forward to see how it does in a RB.
Neither algorithm has good crypto properties on its own, but for trivial operations they are useful. That said: a LFSR can be used as a base for some well known ciphers/checksums and a lot more, while mwc afaik is just a fast and simple prng with relatively big period.
Just starting to explore all this, and found it quite fascinating.
If you know how i can improve them, let me know!
multiply with carry
Code: Select all
# usage: call after setting prngParams = {low;high}
# also see comments on maxnum
# GLOBALS ---------------------------------------------------------------
# debug settings
:global dbgMisc;
# params /result
:global prngParams;
:global prngResult;
:global prngMWC;
# START SCRIPT ----------------------------------------------------
# copy params to local scope
:local Low [:tonum [:pick $prngParams 0]];
:local High [:tonum [:pick $prngParams 1]];
:if ($High <= $Low) do={
:set prngResult $Low;
} else={
# to fill distribution array set maxnum > 1
# and dbgMisc = true
:local distribution {};
:local contador 0;
:local maxnum ($High / 4);
:if ($maxnum > 1) do={
:for i from=0 to=($High-$Low) do={
:set distribution ($distribution,0);
}
}
:do {
# time seed
:local seed1 "";
{
:local time [:tostr [/system clock get time]];
:for i from=0 to=([:len $time] -1) do {
:local char [:pick $time $i ($i+1)];
:if ($char!=":") do={:set seed1 ($seed1 . $char)};
};
:set seed1 [:tonum $seed1];
}
# firewall counters seed
:local seed2 0
:foreach item in=[/ip firewall filter find bytes>0] do={
:set seed2 ($seed2+[/ip firewall filter get $item bytes]);
};
:foreach item in=[/ip firewall nat find bytes>0] do={
:set seed2 ($seed2+[/ip firewall nat get $item bytes]);
};
:foreach item in=[/ip firewall mangle find bytes>0] do={
:set seed2 ($seed2+[/ip firewall mangle get $item bytes]);
};
# uptime seed
:local seed3 "";
{
:local uptime [:tostr [/system resource get uptime]];
:for i from=0 to=([:len $uptime] - 1) do {
:local char [:pick $uptime $i ($i+1)];
:if ($char!=":") do={:set seed3 ($seed3 . $char)};
};
:set seed3 [:tonum $seed3];
}
# cpu load seed
:local seed4 [/system resource get cpu-load];
# conntrack seed
:local seed5 0;
{
:foreach connection in=[/ip firewall connection find] do={
:local src [:tostr [/ip firewall connection get $connection src-address ]];
:local dst [:tostr [/ip firewall connection get $connection dst-address ]];
:local timeout [:tostr [/ip firewall connection get $connection timeout ]];
:for i from=0 to=([:len $src] - 1) do {
:local char [:pick $src $i ($i+1)];
:if ([:typeof [:find ":," $char]]="nil") do={:set seed5 ($seed5 + [:tonum $char])};
};
:for i from=0 to=([:len $dst] - 1) do {
:local char [:pick $dst $i ($i+1)];
:if ([:typeof [:find ":," $char]]="nil") do={:set seed5 ($seed5 + [:tonum $char])};
};
:for i from=0 to=([:len $timeout] - 1) do {
:local char [:pick $timeout $i ($i+1)];
:if ($char!=":") do={:set seed5 ($seed5 + [:tonum $char])};
};
};
}
# acumulator seed
:local seed6;
:if ([:typeof $prngMWC]!="num") do={
:set seed6 64;
} else {
:set seed6 $prngMWC;
};
:local mz (($seed1 ^ $seed3 ^ $seed6) + 1);
:local mw (($seed2 ^ $seed4 ^ $seed5) + 1);
:set mz (36969 * ($mz & 65535) + ($mz >> 16));
:set mw (18000 * ($mw & 65535) + ($mw >> 16));
:set prngMWC (($mz << 16) + ($mw & 65535));
# normalize
:set prngResult ($prngMWC - ( $prngMWC / ($High + 1)) * ($High + 1) + $Low);
:if ($maxnum > 1) do={
:set distribution ([:pick $distribution 0 ($prngResult-$Low)],([:tonum [:pick $distribution ($prngResult-$Low) ($prngResult-$Low+1)]]+1),[:pick $distribution ($prngResult-$Low+1) [:len $distribution]]);
}
:set counter ($counter+1);
} while ($counter < $maxnum);
:if ($dbgMisc) do={
:for i from=0 to=([:len $distribution]-1) do={
:put "$($i+$Low): $([:pick $distribution $i]* 100 / $maxnum )%";
};
:put $prngParams;
:put $prngResult;
};
};
Code: Select all
# Binary Galois LFSR 1/63 bits, periods 0-1..(2^63)-1
# based on:
# http://en.wikipedia.org/wiki/Linear_feedback_shift_register
# http://stackoverflow.com/questions/693880/create-random-number-sequence-with-no-repeats/3181296#3181296
# usage: call first time after setting prngParams={low,high,true} for initializing
# 0 <= Low <= High <= ((2^63)-1)
# then keep calling ((high - low) + 1) times with prngParams={low,high,false}
# to get the permutated interval one item at a time, in prngResult
# when no more numbers are inside the LFSR, prngResult starts to be -1
# GLOBALS ---------------------------------------------------------------
# debug settings
:global dbgMisc;
# params / result prng
:global prngParams;
:global prngResult;
# register state
:global prngSeed;
:global prngLFSR;
:global prngSeq;
:global prngMask;
# START SCRIPT ----------------------------------------------------
# copy params to local scope
:local Low [:tonum [:pick $prngParams 0]];
:local High [:tonum [:pick $prngParams 1]];
:local Initialize (!![:pick $prngParams 2]);
# adjust interval to 0..prngMax
:local prngMax ($High - $Low + 1);
# initialization
:if ($Initialize = true) do={
# time seed
:local seed1 2;
{
:local time [:tostr [/system clock get time]];
:for i from=0 to=([:len $time] -1) do {
:local char [:pick $time $i ($i+1)];
:if ($char!=":") do={:set seed1 ($seed1 * ([:tonum $char] + 1))};
};
}
# firewall counter seed
:local seed2 0
:foreach item in=[/ip firewall filter find bytes>0] do={
:set seed2 ($seed2+[/ip firewall filter get $item bytes]);
};
:foreach item in=[/ip firewall nat find bytes>0] do={
:set seed2 ($seed2+[/ip firewall nat get $item bytes]);
};
:foreach item in=[/ip firewall mangle find bytes>0] do={
:set seed2 ($seed2+[/ip firewall mangle get $item bytes]);
};
# uptime seed
:local seed3 2;
{
:local uptime [:tostr [/system resource get uptime]];
:for i from=0 to=([:len $uptime] - 1) do {
:local char [:pick $uptime $i ($i+1)];
:if ($char!=":") do={:set seed3 ($seed3 * ([:tonum $char] + 1))};
};
}
# cpu load seed
:local seed4 ([/system resource get cpu-load] * 16);
# conntrack seed
:local seed5 "";
{
:local t "";
:local s "";
:local d "";
:foreach connection in=[/ip firewall connection find] do={
:local timeout [:tostr [/ip firewall connection get $connection timeout ]];
:for i from=0 to=([:len $timeout] - 1) do {
:local char [:pick $timeout $i ($i+1)];
:if ($char!=":") do={:set t "$t$char"};
};
:local src [:tostr [/ip firewall connection get $connection src-address ]];
:for i from=0 to=([:len $src] - 1) do {
:local char [:pick $src $i ($i+1)];
:if ([:typeof [:find ":." $char]]="nil") do={:set s "$s$char"};
};
:local dst [:tostr [/ip firewall connection get $connection dst-address ]];
:for i from=0 to=([:len $dst] - 1) do {
:local char [:pick $dst $i ($i+1)];
:if ([:typeof [:find ":." $char]]="nil") do={:set d "$d$char"};
};
};
:set seed5 "$t$s$d";
}
# checksum seeds
:local prngPreSeed (($seed1 ^ $seed2 ^ $seed3 ^ $seed4) | 1);
:set prngSeed 0;
:for i from=[:len $seed5] to=0 do={
:local charnum [:tonum [:pick $seed5 $i]];
:set prngSeed ($prngSeed ^ ($prngPreSeed / ($charnum + 1)));
}
# :put "prngPreSeed=$prngPreSeed, seed1=$seed1, seed2=$seed2, seed3=$seed3, seed4=$seed4, seed5=$seed5";
# :put "prngSeed=$prngSeed";
# array of arrays with taps for maximal period, indexed by bit width (1..63)
:local tapsfor {\
"";\
"";\
"";\
"3,2";\
"4,3";\
"5,3";\
"6,5";\
"7,6";\
"8,6,5,4";\
"9,5";\
"10,7";\
"11,9";\
"12,6,4,1";\
"13,4,3,1";\
"14,5,3,1";\
"15,14";\
"16,15,13,4";\
"17,14";\
"18,11";\
"19,6,2,1";\
"20,17";\
"21,19";\
"22,21";\
"23,18";\
"24,23,22,17";\
"25,22";\
"26,6,2,1";\
"27,5,2,1";\
"28,25";\
"29,27";\
"30,6,4,1";\
"31,28";\
"32,22,2,1";\
"33,20";\
"34,27,2,1";\
"35,33";\
"36,25";\
"37,5,4,3,2,1";\
"38,6,5,1";\
"39,35";\
"40,38,21,19";\
"41,38";\
"42,41,20,19";\
"43,42,38,37";\
"44,43,18,17";\
"45,44,42,41";\
"46,45,26,25";\
"47,42";\
"48,47,21,20";\
"49,40";\
"50,49,24,23";\
"51,50,36,35";\
"52,49";\
"53,52,38,37";\
"54,53,18,17";\
"55,31";\
"56,55,35,34";\
"57,50";\
"58,39";\
"59,58,38,37";\
"60,59";\
"61,60,46,45";\
"62,61,6,5";\
"63,62"\
};
# determine $prngMax bit width
:local highB $prngMax;
:local bits 0;
:while ($highB > 0) do={
:set highB ($highB >> 1);
:set bits ($bits + 1);
};
:if ($bits < 3) do={ :set bits 3 };
# get taps for a $bits wide register
:local taps [:toarray [:tostr [:pick $tapsfor $bits]]];
# get feedback function
:set prngMask 0;
:for i from=0 to=([:len $taps]-1) do={
:set prngMask ($prngMask | (1 << ([:tonum [:pick $taps $i]]-1)));
};
# init register with the seed
:set prngLFSR $prngSeed;
# init seq counter
:set prngSeq 0;
};
# if we haven't finalized the sequence
:if ($prngSeq < $prngMax) do={
:do {
# shift the register until it's high bit is 1 and then apply the mask
# we end up with next seq number
:do {
:set prngLFSR (($prngLFSR >> 1) ^ (-($prngLFSR & 1) & $prngMask));
} while ($prngLFSR > $prngMax);
# if our first result is 0 we cheat
:set prngResult ($prngLFSR-1);
:if (($prngSeq=0) && ($prngLFSR=0)) do={
:set prngLFSR ($prngLFSR+1);
};
} while (($prngSeq=0) && ($prngResult=-1));
# keep the seq count
:set prngSeq ($prngSeq+1);
# move result to the original range
:set prngResult ($prngResult+$Low);
} else={
# if we completed the sequence then exit
:set prngResult -1;
};
:put $prngResult;
just glad to know it is useful to you.