Cool code of the day:
Cool code of the day:
begin
Randomize;
with TEnumerable.Range(1, 49).Shuffled do
Writeln(Take(6).ToArray.ToString, ' Zusatzzahl: ', Skip(6).First);
Readln;
end.
begin
Randomize;
with TEnumerable.Range(1, 49).Shuffled do
Writeln(Take(6).ToArray.ToString, ' Zusatzzahl: ', Skip(6).First);
Readln;
end.
Attila Kovacs LOL, da merkt man, dass ich kein Lotto spiele :p
ReplyDeleteOk, that makes it even a one liner:
Writeln(TEnumerable.Range(1, 49).Shuffled.Take(6).ToArray.ToString, ' Superzahl: ', Random(10));
FWIW, in TArray.Shuffle you can run the loop
ReplyDeletefor i := index to index + count - 2 do
rather than
for i := index to index + count - 1 do
No need to swap the final element with itself.
Hmmm, it looks like your implementations runs afoul of the bias mentionned in
ReplyDeleteen.wikipedia.org - Fisher–Yates shuffle - Wikipedia
David Heffernan Right, I'll fix that - thanks for your review.
ReplyDeleteEric Grange Which one you mean?
If I did not do something completely wrong it has even distribution (apart from the problem with the random generator but I did not want to get into that and write a better one than what Random provides).
This is some test code:
const
Size = 7;
MaxIndex = Size-1;
TotalRuns = 1000000 * size;
var
pos: array[0..MaxIndex,0..MaxIndex] of Integer;
nums: array[0..MaxIndex] of Integer;
n, i: Integer;
begin
for n := 1 to TotalRuns do
begin
for i := 0 to MaxIndex do
nums[i] := i;
TArray.Shuffle(nums);
for i := 0 to MaxIndex do
Inc(pos[nums[i], i]);
end;
for n := 0 to MaxIndex do
begin
for i := 0 to MaxIndex do
Write(Format('%.3f ', [pos[n,i] / TotalRuns]));
Writeln;
end;
Readln;
end.
David Heffernan When I looked at the code I thought it could need some optimization to do less calculations over and over so I changed it:
ReplyDeleteclass procedure TArray.Shuffle(var values: array of T; index,
count: Integer);
var
i: Integer;
temp: T;
begin
while count > 1 do
begin
i := Random(count) + index;
Dec(count);
temp := values[index];
values[index] := values[i];
values[i] := temp;
Inc(index);
end;
end;
Stefan Glienke Your original implementation is correct, it is a uniform shuffle. And l your revised version with a while loop is also correct. Eric Grange was mistaken.
ReplyDeleteIt's nice to see a correct shuffle!
Stefan Glienke using Delphi's low-quality Random function ensures the resulting shuffle is unsuitable for any practical purposes (outside testing sort functions... maybe).
ReplyDeleteThe wikipedia article f.i. lists the case of shuffling a deck of 52 playing cards has an illutration of not enough internal state in the random PRNG.
Typically this means if someone were to use your shuffle implementation in a card game, then kowing the first 5 cards of a deck would be enough to predict the rest of the deck.
This is because 5-6 cards combinations are already way above 2^32... and in practice the Delphi PRNG maintains way less than 32 bits of random.
I would not be surprised if knowing the order of any 3 to 4 cards in the shuffled array would be enough to provide above-the-odds prediction of the whole deck (ie. knowing your hand would give knowledge of other player's hands).
Eric Grange That is what I meant with "apart from the problem with the random generator". Is there any RNG for Delphi that would be capable to do so?
ReplyDeleteEric Grange That's a different issue though, and not what you said in your original comment. Right?
ReplyDeleteStefan Glienke plenty of them, mORMot has a cross-platform one based on AES256, or you can use CryptGenRandom in Windows.
ReplyDeleteIn practice for a casual card game (ie. no money involved) a decent 64bit PRNG would be enough, even if there is not enough state for a full 52 card deck, there will be enough to fool basic inspections.
A 32bit LCG PRNG on the other hand has low enough entropy that it can be attacked without even realizing you are attacking the PRNG... Real-world story: a few years ago, a friend was experimenting with a "deep learning" AI, turned out the AI was decent when decks were shuffled with the Delphi Random it had been trained against, but hopeless when the Random function was switched to XorShift... and never achieved any edge when trained against higher quality PRNGs.
Wikipedia has some nice graphics illustrating LCG issues
en.wikipedia.org - Linear congruential generator - Wikipedia
And for instance Delphi Random has "scratch lines" when plotted in a bitmap (shameless plug)
https://www.delphitools.info/2011/12/13/pimp-your-random-numbers-with-xorshift/
Basically anything that relies on random needs to either use a cryptographic-quality generator or (better) take its random from a user-provided interface of some sort.
/sub
ReplyDeleteGave it a try just for fun: shuffling a 52 cards deck, if you can estimate the time at which "randomize" was called with a second of precision, then knowing just 4 cards allows guessing the whole deck around 20% of the time...
ReplyDeleteAnd its takes a matter of seconds: a single thread can brute-force millions of shuffles per second, and the randomize entropy is just a few million values per second.
Even without any clue on the random seed, scouring the whole 32bit seed space in near-real-time should be definitely feasible with a GPU :)
Eric Grange That's still not the issue that you originally raised though is it?
ReplyDeleteDavid Heffernan He did not mentioned an issue but pointed to the wikipedia article which lists several issues which include the "poor random implementation will make shuffle predictable". Which is why I asked which he meant in particular. When I implemented it I knew about the random problem but did not care much about it but just the possible issues with the implementation of the algo itself (like the off by one error that leads to a non uniform result)
ReplyDeleteEric Grange Point taken. So what will happen when not using the RTL Random but another like the one you implemented for DWS?
Delphi random -> shuffle unsafe vs script kiddy with a single-core cpu, unsuitable for Monte Carlo and most non-cryptographic purposes uses
ReplyDeleteXorshift or Mersenne Twister class -> shuffle safe vs script kiddie if you periodically re-seed from cryptographic seed, but not vs a rich script kiddy with plenty of AWS cloud credits.
Even with a weak seed they are typically usable for Monte Carlo and many non-cryptographic purposes
Cryptographic random -> safe against most attacks, suitable for any purposes (but at a higher computational cost)
Eric was clearly talking about the mechanics of the shuffle algo rather than the underlying PRNG. We all know the limitations of Random. If he'd talking about that he wouldn't have qualified the original statement.
ReplyDeleteAnyway, the shuffle algo is fine. The PRNG choice probably shouldn't be made by Spring, if you want to make the library more flexible. It would be nice if there was a standard Delphi PRNG interface that could be plugged into by third parties so that code like you shuffle didn't need to know about the details of the PRNG.
David Heffernan Agreed. Making it pluggable shouldn't be an issue though. I am wondering if a simple proc variable would be enough that will be used by the library. It might get initialized using System.Random but you can change it for better PRNG. Or if it also would need some more logic like the re-seeding.
ReplyDeleteIn an ideal world Emba would make pluggable RNG part of the RTL and all Delphi libraries could partake.
ReplyDeleteA simple TProc as you suggest would suffice. The user could control the seeding outside your library.
/sub
ReplyDeleteThis seems interesting, stumbled upon it maybe year ago. : pcg-random.org - PCG, A Family of Better Random Number Generators
ReplyDeletePretty good down to earth explanation of it (and lot of general info of random number generators) :
https://www.youtube.com/watch?v=45Oet5qjlms
PCG looks interesting indeed! Prompted me to look up a bit on it, however... it looks like it's a bit outdated now, being from 2014 ;-)
ReplyDeleteThis page lists several fast PRNGs with good quality, top contenders are 2015 & 2016 algorithms, :
xoroshiro.di.unimi.it - xoroshiro+/xorshift*/xorshift+ generators and the PRNG shootout
For "purepascal" I guess xorshift128+ would be the fastest, xoroshiro128+ would need some asm since the Delphi compiler won't optimize to rotate instructions.
Posted a xoroshiro128+ Delphi version in bitbucket.org - egrange / DWScript
ReplyDelete/ source / Source / dwsRandom.pas
— Bitbucket
It appears about 20% faster than Delphi's Random function in 32bit (with a bit of MMX asm though)