Can Delphi randomize string 'Delphi'?

[Mike Torrettinni 198]

I've been randomizing 6 characters string and after 205,329,862,927 tries in last 12h, still no luck for 'Delphi' 😉

I would assume after 205 billion tries it could generate it's own name!?

 

It's pretty fast in randomizing 'D', 'De', 'Del', 'Delp', 'Delph':

D found in 0 ms and 121 random strings.
De found in 0 ms and 4512 random strings.
Del found in 10 ms and 277252 random strings.
Delp found in 115 ms and 2362835 random strings.
..................Delph found in 8654 ms and 180720440 random strings. 

but 'Delphi' is still going...

 

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.Math, System.Diagnostics;

const
  cChars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
function GetRandomString(aNoOfChars: integer): string; inline;
var i: Integer;
begin
  SetLength(Result, aNoOfChars);
  for i := 1 to aNoOfChars do
    Result[i] := cChars[Random(Length(cChars)) + 1];
end;

const
  cPhrases: array[1..6] of string = ('D', 'De', 'Del', 'Delp', 'Delph', 'Delphi');

var vSW: TStopWatch;
    c: Int64;
    vLen: integer;
    vRndString, vPhrase: string;
begin
  Randomize;

  for vPhrase in cPhrases do
  begin
    vSW := TStopWatch.StartNew;
    c := 0;
    vLen := Length(vPhrase);
    vRndString := GetRandomString(vLen);
    while vPhrase <> vRndString do
    begin
      Inc(c);
      vRndString := GetRandomString(vLen);
      if c mod 10000000 = 0 then // progress, so we know it's still working
        write('.');
    end;
    writeln(Format('%s found in %d ms and %d random strings.', [vPhrase, vSW.ElapsedMilliseconds, c]));
  end;
  readln;
end.

 

[Pat Foley 51]

shouldn't cPhrases array be 0 based? 

[Mike Torrettinni 198]

Oh, you think this could be the issue? 

I thought index of arrays is not important if you don't use index to loop it. I don't use index in this case, but for in.

Edited February 28, 2021 by Mike Torrettinni

[Attila Kovacs 629]

1 hour ago, Mike Torrettinni said:

I would assume after 205 billion tries it could generate it's own name!?

Why would you assume that? Because it's written in Delphi or because you don't know the basics of randomness?

[Pat Foley 51]

Was thinking that its not getting up to 6 letters...  So you saying simply throwing 6 dice with 52 lettered faces take more 2^10 throws. 

  

Edited February 28, 2021 by Pat Foley
added dice analogy

[Vandrovnik 214]

Maybe the reason is that you are using (probably 32bit) pseudo-random numbers, not true random numbers. These 32 bits create 4.29e9 seeds for random number generator, while 6 letters from your 52 letters is 19.77e9 combinations. In fact you could try to set the seed to all numbers from 0 to 255^4-1 and see, whether it creates desired result.

 

If you have 64bit random number generator, it could reach the goal, I guess.

[Mike Torrettinni 198]

24 minutes ago, Vandrovnik said:

Maybe the reason is that you are using (probably 32bit) pseudo-random numbers, not true random numbers. These 32 bits create 4.29e9 seeds for random number generator, while 6 letters from your 52 letters is 19.77e9 combinations. In fact you could try to set the seed to all numbers from 0 to 255^4-1 and see, whether it creates desired result.

 

If you have 64bit random number generator, it could reach the goal, I guess.

If I compile for 64bit, would that be using 64bit random number generator or I need specialized library for this?

[Mike Torrettinni 198]

Could I assume if I use password 'Delphi' for a profile, nobody will be able to brute-force guess it, if they run similar random generator? 😉

Edited February 28, 2021 by Mike Torrettinni

[Attila Kovacs 629]

But they don't use random in bruteforcing as it has no benefits.

[stijnsanders 35]

Aah, that makes me think of the infinite monkeys theorem (and also)

[Vandrovnik 214]

57 minutes ago, Mike Torrettinni said:

Could I assume if I use password 'Delphi' for a profile, nobody will be able to brute-force guess it, if they run similar random generator? 😉

No, you cannot assume this.

[Mike Torrettinni 198]

25 minutes ago, Vandrovnik said:

No, you cannot assume this.

OK, good to know.

[Attila Kovacs 629]

You could run this to check if Delphi's random() is able to generate the consecutive numbers of 29 4 11 15 7 8 which are the characters of 'Delphi' taken from the desired (zero based) set 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'.

 

It iterates 4.29 billion possibilities in only 20 seconds on my notebook.

  vRndString := '';
  z := Low(integer);
  RandSeed := z;
  vSW := TStopWatch.StartNew;
  while z < MaxInt do
  begin
    if Random(52) = 29 then
      if Random(52) = 4 then
        if Random(52) = 11 then
          if Random(52) = 15 then
            if Random(52) = 7 then
              if Random(52) = 8 then
              begin
                vRndString := 'Delphi';
                WriteLn(Format('%s found in %d ms with seed of %d', [vRndString, vSW.ElapsedMilliseconds, RandSeed]));
                Break;
              end;
    Inc(z);
    RandSeed := z;
  end;
  if vRndString = '' then
    WriteLn(Format('not found in %d ms', [vSW.ElapsedMilliseconds]));
  ReadLn;

 

And as an example you could use 'VWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTU' with a seed of -1929919901 to get 'Delphi'.

 

  for vPhrase in cPhrases do
  begin
    RandSeed := -1929919901;
  ...

 

 

 

Edited February 28, 2021 by Attila Kovacs

[David Heffernan 2345]

@Mike Torrettinni now that we all know your password I suggest you change it! 

[Mike Torrettinni 198]

24h and almost 400 billion tries, still no 'Delphi'. Experiment done ☹️

 

[Attila Kovacs 629]

That was a waste of time and energy.. You should read more RTL code and the answers to your questions!!

 

 

Edited March 1, 2021 by Attila Kovacs

[Kryvich 165]

According to the probability theory, there is a 1/19 770 609 664 chance that on the next try you will get the desired 6-letter word. So the fact that after 400 billion attempts it has not been received looks suspicious, but not impossible. (19 770 609 664 = 52*52*52*52*52*52).

 

By the way, here are the probabilities of finding a word with fewer characters:

1-letter word: 1/52,

2-letter word: 1/2 704,

3-letter word: 1/140 608,

4-letter word: 1/7 311 616,

5-letter word: 1/380 204 032,

6-letter word: 1/19 770 609 664.

Edited March 1, 2021 by Kryvich

[David Heffernan 2345]

There seems to be a lot of hating on @Mike Torrettinni here, but this is actually a reasonably subtle issue. What @Attila Kovacs has pointed out is that Delphi's 32 bit linear congruential generator (LCG) PRNG algo in Random is not capable of generating that specific sequence.  This isn't so much a weakness of Delphi, rather it's just a feature of 32 bit LCG, true weaklings in the world of PRNGs.

 

If you want to generate sequences of length more than a handful of values, then this PRNG is not the right choice.

[David Heffernan 2345]

3 minutes ago, Kryvich said:

According to the probability theory, there is a 1/19 770 609 664
chance that on the next try you will get the desired 6-letter word. So the fact that after 400 billion attempts it has not been received looks suspicious, but not impossible. (19 770 609 664 = 52*52*52*52*52*52).

LCG's are deterministic, and @Attila Kovacs showed that Delphi's LCG won't ever produce that sequence. Probability isn't really the issue here, because we have pushed this PRNG so far beyond its zone of effectiveness that we can no longer reason about it using probability. 

[Stefan Glienke 2002]

52^6 is bigger than 32bit so of course a 32bit RNG might not yield it. In fact its over 4 times more than 32bit so only like every 4th possible 6 letter combination would ever be yielded.

Bonus hint: try a lowercase d 😉

Edited March 1, 2021 by Stefan Glienke

[Mike Torrettinni 198]

2 hours ago, Stefan Glienke said:

52^6 is bigger than 32bit so of course a 32bit RNG might not yield it. In fact its over 4 times more than 32bit so only like every 4th possible 6 letter combination would ever be yielded.

Bonus hint: try a lowercase d 😉

Well, 'delphi' is not really worth even trying 😉