Random number?

[raidho36]

this proverb applies to physics and engineering, not math and computer science

I think it applies everywhere around. Your math proof was pretty much for spherical cases in vacuum.

what assumptions are invalid

First off, normal distribution. That's the deal breaker, one may skip the rest of the proof right from here. Then goes the thing that you can only estimate distribution, and estimation works like shit in general and only gives reasonable output for some marginal cases, but you use it anyway. And lastly you measure unrepresentative selection of values, which is downright invalid.

Sorry about not having that C code at hand. You'd have to simply beleive me regardless. Have some miracously recovered from flash drive early version file. I'm not entirely sure if it was from the project in quesiton. You may take a look at this other file (http://love2d.org/forums/download/file.php?id=7884), just if you think I'm one of those Mr.BallGuy-level programmers. It's not entirely representative either, since it's an early draft, too.

I just realize that the periodic length of the sequence is 65536.

Not necessairly. Record those 65k randoms into a table and run random another 65k times checking for matches.

Random seeding will not solve this, however.

If you re-seed by OS time then it does breaks current pattern. Of course if you will seed random by random without it influenced by unrelated events then you will get similar sequences nevertheless. I never claimed that something as simple as batatinha proposed would ever work.

[batatinha]

For the third experiment, can you please run it once, then wait for some seconds and then run it again and show the output of these two runs?

Sure...

>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0

Weird? =\

@vrld
No, i'm seeding it, see:

Code: Select all

pattern = {}
pattern[1] = {}
pattern[2] = {}
pattern[3] = {}
pattern[4] = {}
pattern[5] = {}
pattern[6] = {}
pattern[7] = {}
pattern[8] = {}
pattern[9] = {}
pattern[10] = {}

require('socket')

function generatePattern(n)
	r = nil
	math.randomseed(socket.gettime()*10000)
	for a = 1,n do
		r = math.random(1, 10)
		table.insert(pattern[r], r)
	end
end

print('Generating 10000 random numbers with time generated seed')
generatePattern(10000)
print('Result:')
for k,v in pairs(pattern) do
	print('Number '.. k ..' generated '.. #v ..' times')
end

[Plu]

Are you sure that "socket.gettime()*10000" generates large integers? If it's running microtime that number might barely go above 1, which means you're still pretty much seeding the same number every time. Can you print out the actual seeds you're using?

[batatinha]

Can you print out the actual seeds you're using?

Here it is:

>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541256406
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541288594
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541319844
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541406719
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541433281
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541518125
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0
>lua -e "io.stdout:setvbuf 'no'" "random.lua"
Generating 10000 random numbers with time generated seed
using seed: 13721541657031
Result:
Number 1 generated 967 times
Number 2 generated 967 times
Number 3 generated 987 times
Number 4 generated 1015 times
Number 5 generated 1036 times
Number 6 generated 995 times
Number 7 generated 1000 times
Number 8 generated 1016 times
Number 9 generated 1019 times
Number 10 generated 998 times
>Exit code: 0

[vrld]

this proverb applies to physics and engineering, not math and computer science

I think it applies everywhere around. Your math proof was pretty much for spherical cases in vacuum.

Seeing that we are talking about math here it's only appropriate to actually use math to argue about it, don't you think? If not, please suggest an alternative.

what assumptions are invalid

First off, normal distribution.

1. Why?
2. The Lua manual states that math.random() draws from a uniform distribution.
3. You can verify that the distribution is uniform by experiment (see batatinha's posts)
4. It doesn't matter, since entropy is defined independent of the distribution.

Then goes the thing that you can only estimate distribution, and estimation works like shit in general and only gives reasonable output for some marginal cases, but you use it anyway.

That you can only estimate the true distribution is only a technicality and was only included to show that I take you and your concerns seriously¹: As I already wrote, the strong law of large numbers guarantees that the mean of samples drawn from a distribution approaches the expected value of the distribution. For a binary random variable (which by sampling from math.random(1,2) we have) about 100 samples are sufficient to get a reasonable estimate the expected value². The code I posted uses way more samples than that.

You'd have to simply beleive me regardless.

I'm a skeptic, so I can not. You can change my view by either providing proof or strong reasoning.
The code you attached does not seem to use random numbers - are you sure it's the right one?

One more thing:

if you think I'm one of those Mr.BallGuy-level programmers

What does that have to do with anything? It is o.k. to be arrogant, but if you are you should be able to afford it. You have shown that you can't.

¹ It would be nice if you did the same for us.
² Trust me, I get paid for this stuff.

[Automatik]

This makes it obvious why same seed gives same sequence. This would be quite good enough, nevertheless it may be not. To increase entropy, you must interfere with an algorithm, particularry by modifying at random multiplication and addition values, or just the seed itself. To do that, you must somehow find a data that could not be predicted, i.e. being really random. Hardware random generators has noise generators which naturally source them truily random stream of data. Software emulation must gather "noise" from some of the sources available. One of such sources is user input. The other is natural fluctiations in program execution flow.

I meant, why math.randomseed(math.random()) is more random? You are still using the same source of data.

The whole point to use it in games is so the player won't see any pattern, not encryption or something.

But the thing is that math.random, is good enough for most people, and for the rest, there is love.math.random.

[Boolsheet]

batatinha, the issue that your seed isn't working as expected probably comes from the fact that you're trying to give it a 43-bit long number and somwhere in the conversion process (be it Lua oder VC++) this gets turned into 0. math.randomseed calls the C function srand that expects the type unsinged int which is 32-bit on most of today's systems. Limit the number you get from gettime by doing a modulo operation on it and the conversion will work as expected.

Code: Select all

math.randomseed((socket.gettime()*10000) % 2^31)

Edit: Changed code to 2^31. They probably use a signed int somewhere in the code making the conversion undefined if it's larger than that.

[Robin]

You'd have to simply beleive me regardless.

I'm a skeptic, so I can not. You can change my view by either providing proof or strong reasoning.

This is why this thread is pointless. The only argument raidho36 is willing (and maybe able) to provide is "just trust me, alright?". This isn't going to work.

By the way, just for kicks, I went and repeated batatinha's experiment. I modified the source code slightly (see below) and ran it with LÖVE rather than Lua, because I don't have Luasocket installed.

Code: Select all

local pattern = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

require('socket')

function generatePattern(n)
   math.randomseed(socket.gettime()*10000)
   for a = 1,n do
      local r = math.random(1, 10)
      pattern[r] = pattern[r] + 1
   end
end

print('Generating 10000 random numbers with time generated seed')
generatePattern(10000)
print('Result:')
for k,v in pairs(pattern) do
   print('Number '.. k ..' generated '.. v ..' times')
end

Result:

Code: Select all

$ love .
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 1002 times
Number 2 generated 1039 times
Number 3 generated 989 times
Number 4 generated 1022 times
Number 5 generated 976 times
Number 6 generated 986 times
Number 7 generated 976 times
Number 8 generated 1020 times
Number 9 generated 1050 times
Number 10 generated 940 times
$ love .
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 1042 times
Number 2 generated 1007 times
Number 3 generated 1014 times
Number 4 generated 948 times
Number 5 generated 986 times
Number 6 generated 974 times
Number 7 generated 1023 times
Number 8 generated 952 times
Number 9 generated 1040 times
Number 10 generated 1014 times
$ love .
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 984 times
Number 2 generated 1032 times
Number 3 generated 976 times
Number 4 generated 1032 times
Number 5 generated 1024 times
Number 6 generated 977 times
Number 7 generated 972 times
Number 8 generated 1022 times
Number 9 generated 1046 times
Number 10 generated 935 times
$ love .
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 1014 times
Number 2 generated 969 times
Number 3 generated 1011 times
Number 4 generated 1061 times
Number 5 generated 994 times
Number 6 generated 987 times
Number 7 generated 1001 times
Number 8 generated 965 times
Number 9 generated 1020 times
Number 10 generated 978 times
$ love .
Generating 10000 random numbers with time generated seed
Result:
Number 1 generated 1014 times
Number 2 generated 1022 times
Number 3 generated 996 times
Number 4 generated 999 times
Number 5 generated 1000 times
Number 6 generated 1037 times
Number 7 generated 1057 times
Number 8 generated 951 times
Number 9 generated 942 times
Number 10 generated 982 times

Summary: the numbers are completely different each time.

[micha]

You (micha and raidho36) are both right: You will not only start from a different position, but you will also "shuffle" the list.

I was talking about the algorithm that was posted above:

Code: Select all

#define RAND_MAX 0x00010000 /* that would be 65536 */
static unsigned int seed = 1;
void srand ( int s )
{
  seed = s;
}

unsigned int rand ( void )
{
  seed = seed * 0x00FACEXD + 0xDEADBEEF;
  return seed % RAND_MAX;
}

Since the factor 0x00FACEXD and the offset 0xDEADBEEF don't change, the list will not be shuffled. That might be different for the implementation of math.random() in Lua. I don't know how it is implemented there.

I just realize that the periodic length of the sequence is 65536.

Not necessairly. Record those 65k randoms into a table and run random another 65k times checking for matches.

For the reasons above, the two lists will be the same up to a cyclic rotation.

[raidho36]

For the reasons above, the two lists will be the same up to a cyclic rotation.

Only that rand doesn't return ALL bits that revolve arond inside, there's a little more is going on. So pattern may be way longer than RAND_MAX, and even than INT_MAX for that matter.

The only argument raidho36 is willing (and maybe able) to provide is "just trust me, alright?". This isn't going to work.

How am I supposed to re-code you exactly the program I used back then, so you could see it? Besides, I'm not proposing here to possess ultimate randomness power, I simply claim that additional randomizing slightly improves pseudo-random generated pattern by breaking it apart at really random positions. You don't even have to really apply this in your programs, you will most likely never notice the pattern if you use random just like normal. But if you do, randomization helps. Random mess of small randomly torn chunks of a total pattern is better than plain total pattern. You don't need any real experiment to confirm this, a simple common sense gives you an idea that it's true. But if you want it that bad, I can write you a random.dll that has very short internal pattern since it will only use, like, 4 bits or something, and then you can perform real experiment, as a proof of concept.

why math.randomseed(math.random()) is more random?

It's not any more random, I just used the wrong term (and already acknowledged it). I mean that it makes noticeable patterns less likely.

The code you attached does not seem to use random numbers - are you sure it's the right one? What does that have to do with anything?

I'm not even sure if it's from the right project, as I said. It was just for the sake of displaying (a part) of my programming abilities. Just because I'm not in friends with this advanced extent of math theory doesn't makes me bad programmer from practical point of view. Speaking of problems with entropy analysis, if random will return you 50 1-s and 50 2-s in a pattern like 1-1-1-2-2-1-2-2, this kind of estimation function wouldn't adequately assess randomness anyway. And what the hell, it only assess distribution, nothing to do with randomness. I don't know why haven't I mentioned that first even though it's painfully obvious. And oh I'm terribly sorry if you only value theoretical knowledge. See above.