QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: Statsman1 on October 25, 2021, 08:18:02 pm

Title: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 25, 2021, 08:18:02 pm
Hey guys...

Picture 6 horses in a race, using the TIMER function at the START and FINISH to calculate elapsed time.  They finish with the following times (in seconds)...

Racer 1    31.30453     
Racer 2    31.48992     
Racer 3    31.50592     
Racer 4    31.8607     
Racer 5    32.23148     
Racer 6    32.41687

Then picture 6 different horses in a race, but same distance as race 1.  This time, the results (in seconds) are...

Racer 7    30.93375     
Racer 8    30.94975     
Racer 9    31.11914     
Racer 10  31.30453     
Racer 11  31.48992     
Racer 12  31.50592

Note that Racer 11 and Racer 12 have EXACTLY the same times as Racer 2 and Racer 3.  The fact that all 6 times are not the same is encouraging, but how on earth could two identical times be possible, let alone have it happen twice?

I have seen this happen over a series of races...duplicate times (but not duplicate places in finish) come up a LOT.  For instance, the time 32.77441 has happened 6 times in 30 races.  That just doesn't seem to be right.

I have used the RANDOMIZE (-TIMER) and RANDOMIZE (TIMER) functions within the program - the first is used to determine how far forward the horse moves (the maximum is 3 pixels, the minimum is 1 pixel, so in practice, thus the average is 2 pixels).   The second is invoked after every horse has moved, to calculate a random-length system delay between each move.  To me, this means a new seed is generated every single time the program accesses the routine used to create the delay, I then take the average of 100 random numbers, and use this as the delay..maybe I misunderstand this function.

        Randomize (Timer)
        L = 0
        For J = 1 To 100
            K = Rnd(1) / 1000
            L = L + K
        Next J

        m = L / 10

        _Delay (m)

Anyway, I get that over running a series of random numbers between 1 and 3 will average 2, and that if you do that constantly over the same distance, you will get very similar times to complete the race...but introducing that random delay should be enough to avoid timing duplication down to the 100,000th of a second, shouldn't it?


Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 08:52:00 pm
I think if you don't Randomize Timer, you will have to go through a million numbers or so before repeats. I'd do it once at the beginning after you have your program debugged so that your starts are always different. RND uses a formula and patterns will show up according to formula.

I've taken all the points on the screen shuffled them and drew them before recyling another set of points. That covers the screen once before repeats. You could do same with race times!
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 25, 2021, 09:01:52 pm
Thanks bplus...

I use RANDOMIZE (-TIMER) at the very start of my program, and it is called only once.

Are you saying I shouldn't bother with the second RANDOMIZE (TIMER)?  Or is there just a better way to pick a random number? 

All I am doing is trying to figure out how the heck two separate events can time exactly the same to the 5th decimal point when everything that contributes to that time is a series of apparently random numbers.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 09:06:24 pm
Yes, I don't think you will see repeat number unless you reseed RANDOMIZE often.

Try getting repeat with Randomize Timer only at start, only once.

PS I am wondering why you are putting Timer in parenthesis and about -Timer, I suppose it's OK? just strikes me as odd.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 09:15:45 pm
No repeats for 10,000
Code: QB64: [Select]
  1. Dim r(1 To 10000)
  2. For i = 1 To 10000
  3.     r(i) = Rnd
  4.     For j = 1 To i - 1
  5.         If r(i) = r(j) Then Beep: repeats = repeats + 1
  6.     Next
  7. Print "Repeats = "; repeats
  8.  
  9.  
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 09:20:13 pm
I am running 100,000 been quiet except for CPU ;-))

I think you have to go to 1,000,000 to start getting repeats.

!00,000 done no repeats.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 25, 2021, 09:27:57 pm
So I just have RANDOMIZE (TIMER) at the start, no other occurrences of a randomize.

These are the sorted times of 10 races, 6 racers in each...still a ton of duplications.

45.81797
46.00336
46.00336
46.00336
46.01936
46.01936
46.18875
46.37414
46.37414
46.55953
46.74492
46.77141
46.78741
46.93031
46.93031
46.9568
47.1157
47.1157
47.1157
47.1317
47.1317
47.30109
47.30109
47.48648
47.67188
47.68787
47.88375
47.88375
47.88375
47.89975
47.89975
48.25453
48.41344
48.41344
48.42944
48.43992
48.59883
48.59883
48.78422
48.96961
48.96961
48.96961
49.34039
49.52578
49.73766
50.08195
50.47922
50.66461
50.85
51.03539
51.59156
51.77695
51.96235
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 11:28:31 pm
That's weird have to see code that generates numbers I guess.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 25, 2021, 11:44:14 pm
Here's another test sorting the 10,000 items:
Code: QB64: [Select]
  1. Dim Shared sa(1 To 10000)
  2. For i = 1 To 10000
  3.     sa(i) = 100 * Rnd
  4. QSort 1, 10000
  5. For i = 1 To 10000
  6.     Print sa(i)
  7.     If i Mod 20 = 0 Then Sleep: Cls
  8.     If i > 1 Then
  9.         If sa(i) = sa(i - 1) Then Beep: repeats = repeats + 1
  10.     End If
  11. Print "Repeats"; repeats
  12.  
  13. Sub QSort (Start, Finish) 'sa needs to be   DIM SHARED !!!!     array
  14.     Dim i As Long, j As Long, x$
  15.     i = Start
  16.     j = Finish
  17.     x = sa(Int((i + j) / 2))
  18.     While i <= j
  19.         While sa(i) < x
  20.             i = i + 1
  21.         Wend
  22.         While sa(j) > x
  23.             j = j - 1
  24.         Wend
  25.         If i <= j Then
  26.             Swap sa(i), sa(j)
  27.             i = i + 1
  28.             j = j - 1
  29.         End If
  30.     Wend
  31.     If j > Start Then QSort Start, j
  32.     If i < Finish Then QSort i, Finish
  33.  
  34.  
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: SMcNeill on October 26, 2021, 01:25:43 am
        Randomize (Timer)
        L = 0
        For J = 1 To 100
            K = Rnd(1) / 1000
            L = L + K
        Next J

        m = L / 10

        _Delay (m)


There's so much strange stuff going on above, I have no idea where to even start diagnosing it...

        For J = 1 To 100
            K = Rnd(1) / 1000
            L = L + K
        Next J

First, why do we need to get 100 different random numbers between 0 and 0.9999999?  Just for the value of L?  At 100 rolls, you're going to hit mighty damn close to the average of 0.5 overall.  100 rolls * average value of 0.5 = 50.  Of course, you /1000 each time, so L is going to be close to 0.05. 

I'm willingto bet a cookie that L never varies more than 0.002 from 0.05.  I'll bet a box of cookies that it never varies more than 0.005 from that average.

But then m is L / 10, which makes it ~0.005....

Which then introduces an incredibly small delay into the code...

Which is for, "introducing that random delay should be enough to avoid timing duplication down to the 100,000th of a second..."

???

It sounds to me like all this is inside a main loop and you're trying to move your randomizer seed manually each pass, but that 0.005 second delay isn't changing the seed but by a miniscule value, letting you generate the same repetitive values over and over...

Fix for this? 

Drop the FOR loop, and the _DELAY completely. 

RND works off a formula.  A delay doesn't do anything to it, but in this case your use of RANDOMIZE TIMER repeatedly in a short timeframe is keeping your seed value close to the same entry point in the RND formulas.

Move RANDOMIZER TIMER outside all your other loops.  Run it once when the program starts and be done with it.  After that, basically strip out all you have and stick with a simple bit below in your main loop.

K = RND
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 10:05:26 am
Thank you, Steve, for the insight here.  I have removed the second RANDOMIZE and only triggering one RANDOMIZE (TIMER) at the beginning of the program.  The goal of that 100-loop accumulation was simply to introduce a random delay on each sweep of the code that determines movement of the horses, because I am consistently getting identical times, which is really what I am asking about.

I agree 100 percent that the mean of a series of random numbers between 0 and .999999 approaches .5, and that loop wasn’t doing much, except that probably WASN’T exactly .5, and because _DELAY can use 1/1000ths, it should have been enough to prevent the identical times (to the 1/100000th) happening.  It wasn’t.

I am not the most optimized coder, no question about that, but when I time events using TIMER, with that precision, I still cannot figure out how I am getting identical times all the way to the 1/100000th of a second.  That should be, to my mind, quite impossible….or, since anything is possible, FAR less frequent.

There is too much code to paste here, but the gist of it is….

BEGIN
START RACE
StartTime = TIMER
Race is 1,440 pixels long
Begin Loop
Random numbers between 1 and 3 determine how many pixels forward each horse moves
All 6 horses move, in random order
All horses move forward
Eventually, each horse has moved 1,440 pixels (enough passes of 1, 2 or 3 have happened to add up to 1,440)
First horse crosses finish line
FirstTime = TIMER
FirstTime = FirstFinish - StartTime
Second horse crosses finish line
SecondFinish = TIMER
SecondTime = SecondFinish - TIMER
.
.
.
Sixth horse crosses finish line
SixthFinish = TIMER
SixthTime = SixthFinish - StartTime
End of loop
Race is done - display results
END

Sometimes, there are EXACT ties in a race.  Dead heats happen in horse races, I have no issue with that, though, again, a tie to the 1/100000th of a second seems kind of wildly unlikely.

But run a few of these, and I get some identical times, all the way down to the 1/100000 of a second (I posted a list of 10 races x 6 times).  The 4th place finisher in race #6 will have the identical time to the 2nd place finisher in race #3, for example.  Again, to the 1/100000th of a second.  That just should NOT happen. 

I tried this.  If I run a race where all horses move 3 pixels at a time, all 6 finish at basically the same time, but the first horse to move that last cycle wins by 2/100th of a second.  Makes sense, there is processing time being used.  However, all the other 5 horses have the exact same time down to the 5th decimal place.  Something is strange about this type of thing.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 26, 2021, 11:57:29 am
Here's your horse race man.
Code: QB64: [Select]
  1. Width 120
  2. Const track = 100
  3. Dim horses(1 To 6)
  4. Dim loops(1 To 6)
  5. Dim stillRunning, i
  6.  
  7. stillRunning = 1
  8. While stillRunning = 1
  9.     stillRunning = 0 ' clear flag
  10.     For i = 1 To 6
  11.         If horses(i) <= track Then
  12.             loops(i) = loops(i) + 1
  13.             stillRunning = 1 'set flag
  14.             horses(i) = horses(i) + Rnd * .25
  15.         End If
  16.     Next
  17.     Cls
  18.     Print
  19.     For i = 1 To 6
  20.         Color i
  21.         Print Tab(Int(horses(i))); horses(i)
  22.         Print
  23.     Next
  24.     Color 15
  25.     Locate 1, 1
  26.     For i = 1 To 6
  27.         Print Tab(100); "|"
  28.         Print
  29.     Next
  30.     _Limit 60
  31. Print "And the results are in:"
  32. For i = 1 To 6
  33.     Color i
  34.     Print i, loops(i)
  35.  

And yes you will get allot of repeat "times" because the average of a bunch of random numbers condenses around an average. You can even see about what the average is by the distribution of "times".

Notice I did not use timer but just counted how many "steps" it took each horse to get past the end of the track

Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 01:34:07 pm
Hey bplus!

Thanks for this, and yes, I know that the averages condense to a single value (for instance, the average of random numbers between 1 and 3 will end up narrowing down to 2).  My issue is that the TIMER function spits out exactly the same times to the 1/100000th of a second over a small sample size of events.

I have done the same thing you did…I count the number of loops it takes to finish a race (because I thought that was the cause) and the number of loops is almost always different.  Here, 11 races in question took the following number of loops to finish…

600, 610, 613, 604, 603, 609, 611, 619, 596, 604, 612

The average of that is 607, which actually never happened in those races.

So if a race that took 613 loops produced a 2nd place finish in 34.123456 seconds, how on earth did another race that took 596 loops have a 4th place finisher in 34.123456 seconds as well? 

The fact that those two events use TIMER to achieve the EXACT SAME TIME is my issue.  Not the random numbers generated to do it.

Maybe I am the only guy who thinks that two things that time to that level of identical accuracy is odd.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 26, 2021, 02:07:06 pm
Hi Statsman1

I set up a different view of horse racing. Here I start off favoring each horse with increasing probabilities for winning or being faster whatever you want to call it the higher the horse number the more likely it would win but only by small fraction.

It takes 1000 races to see the order of horses and 10,000 to confirm the order for sure!
Code: QB64: [Select]
  1. _Title "Horse Race #2" 'b+ 2021-10-26
  2.  
  3. ' I want to split the odds evenly between 6 horses but I don't want the 2nd worse horse be twice as likely to win as worse
  4. ' the 3rd worse.
  5.  
  6. 'The sum of 1 + 2+ 3.. + 6 = 6(7)/2 = 21
  7. 'so give each horse 21 + n/21 = 6 * 21 + 21 = 126 + 21 = 147
  8. ' or (21 + n/21)/147
  9. Dim pHorse(1 To 6)
  10. 'check that adds to 1.0
  11. For i = 1 To 6
  12.     pHorse(i) = (21 + i) / 147
  13.     total = total + pHorse(i)
  14.     If i = 1 Then Print i, pHorse(i)
  15.     If i > 1 Then Print i, pHorse(i), pHorse(i) - pHorse(i - 1)
  16. Print "Total p ="; total
  17.  
  18. ' that looks like a horse race, in the short run any horse can win in the long haul the better horses will win more orderly
  19. Dim races(1 To 6), nRaces
  20. nRaces = 10
  21.  
  22. moreRaces:
  23. For race = 1 To nRaces
  24.     ' A race
  25.     Cls
  26.     Print "A day at the Races, and any horse can win!"
  27.     Print "Horse:", "'Speed':"
  28.     For i = 1 To 6
  29.         p = Rnd * pHorse(i) * 100
  30.         Print i, p
  31.         races(i) = races(i) + p
  32.     Next
  33.     _Delay 25 / nRaces
  34. Print "After"; nRaces; " races, these are the averages for horses"
  35. Print "Horse:", "'Speed':"
  36. For i = 1 To 6
  37.     Print i, races(i) / nRaces
  38. If nRaces < 10000 Then nRaces = nRaces * 10: Erase races: GoTo moreRaces
  39.  
  40.  

At any single day at the races you don't have a clue which is the best horse, nor really after 10. 100 and things start to fall in place but still surprises.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 26, 2021, 02:11:45 pm
Yeah dump the idea of Randomize with Timer, not needed except at start of program to get different results each time you start the app, Unless You Start at Exactly the Same Timer Each Day!!! (That might make a clever prank.)
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 02:23:55 pm
I wonder if...

A=RND
Randomize(TIMER + A)

...would work.

I really appreciate all time you are taking to look at this, but again - it isn't about the various results, it is about using TIMER.  If you used the TIMER function to actually time how long each race took each horse, and you had a number of horses in different races run in the exact same time, down to the 1/100000th of a second...wouldn't you think that was a bit strange?

Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Cobalt on October 26, 2021, 02:35:02 pm
There is a reason we refer to it as "Pseudo-Random" cause its not truly random. If you do a search you will find posts from some time ago where this was discussed.

If you want numbers that are far closer to truly random you'll need to poll those from a site such as RANDOM.ORG.

otherwise you will just have to make due.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 02:49:35 pm
Thank you, everyone, for their efforts to help me.

I cannot stress enough that it is NOT the random numbers I question, it is the TIMER function.  The use of random numbers only contributed to why the various events should take different lengths of time.  But I cannot seem to get that point across...I know how random numbers work, I know how the mean is calculated, I know that over time, the random numbers will all converge to the mean, I know that there are no truly random numbers...I know all of that.

I question why separate events that take different cycles to complete can still have identical times to 1/100000th of a second.  Identical to the second...sure.  Even to 1/10th or 1/100th, occasionally.  But 1/100000th of a second?  No, that makes no sense to me.

I wish I hadn't brought up the random numbers, though I did think maybe something was amiss there, initially, maybe I could have made my question about TIMER and my odd results more clear.

Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 26, 2021, 03:06:14 pm
Timer polling is very inaccurate but it may be improved by increasing the precision of the Type variable though Single may be as good as it gets and specifying Timer(Accuracy) maybe .0001 is better than .001? According to Wiki .001 is it!

Code: QB64: [Select]
  1. t = Timer
  2.     i = i + 1
  3.     Print i
  4. Print "With no timer accuracy set and default precision on t."
  5. Print "zzz..."
  6. i = 0
  7. t = Timer(.00001)
  8. While Timer(.00001) = t
  9.     i = i + 1
  10.     Print i
  11. Print "With a finer tuned accuracy on timer and type variable to hold value."
  12.  
  13.  
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 03:19:42 pm
Thank you, bplus...I will try implementing the more-accurate storage of TIMER, maybe that changes things a bit.

Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Richard on October 26, 2021, 04:04:33 pm
@Statsman1

I do not know if it is of use to you but...

I use QB64 code to measure time intervals down to 100 nano seconds (rather than TIMER)
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Bert22306 on October 26, 2021, 04:36:42 pm
Could this also be related to the problem with the QB64 PRNG, when you cycle through a set of RND that is a power of 2? I'd say, to be on the safer side, always go through an odd number of RND in the loop?

See this, and how it creates a nice colorful pattern, over time.

Code: [Select]
Rem  Program creates dots using random x and y coordinates
Rem
Rem  To eliminate pattern, make sure the number of Rnd variables in
Rem  the loop are not a power of 2.
Rem -------
Do
    Call Initialize
    Call DrawDots
Loop
End

Sub Initialize
    _Title "Random Number Distribution"
    Screen _NewImage(840, 480, 12)
    Cls
End Sub

Sub DrawDots
    Randomize Timer
    Color 9
    Print "First random number this cycle"; Rnd
    Do
        x = Rnd * 840
        y = Rnd * 480
        c = 1 + Int(Rnd * 15)
        a4 = Rnd
        a5 = Rnd
        a6 = Rnd
        a7 = Rnd
        a8 = Rnd
        a9 = Rnd
        a10 = Rnd
        a11 = Rnd
        a12 = Rnd
        a13 = Rnd
        a14 = Rnd
        a15 = Rnd
        a16 = Rnd
        PSet (x, y), c
        _Delay .005
        If InKey$ = Chr$(27) Then Exit Do
    Loop
    Cls
    Locate 15, 35
    Input "Start with new seed (y/n)"; cont$
    If cont$ = "n" Then End
End Sub
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 04:39:39 pm
@Statsman1

I do not know if it is of use to you but...

I use QB64 code to measure time intervals down to 100 nano seconds (rather than TIMER)

It might be just what I need, if you can offer some code to try!  Thank you!
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Richard on October 26, 2021, 04:52:54 pm
@Statsman1


Code: QB64: [Select]
  1. version$ = "Precision_timer-999"
  2. DECLARE DYNAMIC LIBRARY "kernel32"' Acquiring high-resolution time stamps  ' https://docs.microsoft.com/en-us/windows/win32/sysinfo/acquiring-high-resolution-time-stamps
  3.     SUB QueryPerformanceCounter (BYVAL lpPerformanceCount AS _UNSIGNED _OFFSET)
  4.     SUB QueryPerformanceFrequency (BYVAL lpFrequency AS _UNSIGNED _OFFSET)
  5. DIM SHARED PerformanceCount AS _INTEGER64
  6. DIM SHARED StartingCount AS _INTEGER64
  7. DIM SHARED dElapsedTime AS DOUBLE
  8. DIM SHARED dElapsedTimeOLD AS DOUBLE
  9. QueryPerformanceFrequency (_OFFSET(Frequency))
  10. QueryPerformanceCounter (_OFFSET(StartingCount))
  11.  
  12. TIMERe:dElapsedTimeOLD = dElapsedTime
  13. x#=sqr(2)
  14. TIMERe
  15. print:print "Time to compute SQR(2) =";:PRINT USING "####.#"; (dElapsedTime - dElapsedTimeOLD)*1000000;:print " micro-seconds"
  16.  
  17. SUB TIMERe
  18. QueryPerformanceCounter (_OFFSET(PerformanceCount))
  19. dElapsedTime = (CDBL(PerformanceCount - StartingCount)) / Frequency
  20.  
  21.  


The above code is basically a Windows thing - for CRITICAL timings one would have to  calibrate the clocks using external hardware and be aware of factors such as time-ageing of the computer crystal, temperature variations of crystal frequency, the manufacturing tolerance of the crystals (e.g. +/- 50ppm is common), etc. However for your setup (and everything is relative to your set-up) - you may not have to be concerned with calibration etc.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Pete on October 26, 2021, 04:59:28 pm
@Richard

Have you ever experienced priority issues, where the OS places focus on a background process and corrupts the timing results?

Pete
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: bplus on October 26, 2021, 05:29:15 pm
Honestly don't see a reason to Randomize Timer at particular timings if all you need is a random (like) number???
What am I missing?

I did have a need to Randomize (seed) when I used seeds to repeat the exact sequence of RND values so I wouldn't have to store the numbers for later to repeat same "random" pattern. It was for firework trails.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Richard on October 26, 2021, 05:40:20 pm
@Pete


refer to the following

https://www.qb64.org/forum/index.php?topic=2276.180 (https://www.qb64.org/forum/index.php?topic=2276.180)   Reply #180


Answer:-    YES (millions of times)


In the above mentioned post (reply #180) which (briefly) shows the timing distributions of performing the same task (say 128 times) and comparing doing the same task many different ways (i.e. all the colorful histograms) - IF windows was not present, then one would expect the timings to be a very "tight cluster" (at the bottom LHS of the picture is an example of "fairly tight clusters" - here there is "minimal QB64 code (i.e. empty loops - essentially  TIMERe: (no code done here) : TIMERe - and so Windows doing its priority thing has relatively minor effects).  In the mainstream part of the picture (where a number of QB64 code lines (i.e. >= 3) is inserted between TIMERe:...TIMERe timing points - the "cluster" is "EXPANDED" (the mean of the cluster rightfully has to be greater than without code obviously) - the EXPANSION  of the cluster is the result of 2 factors. #1 is Windows priority (a you mentioned) and #2 is "memory cache effects" (more details on this if you want ???).

In a nutshell, YES windows priority will have an effect on timings (more noticeable for each "additional line of QB64 code") for BOTH the "high precision timer-999.bas" AND also any implementation of TIMER (standard QB64 even with millisecond resolution, ! # and ## variants).

In fact, my "lazy" approach to having random numbers is simply monitor the non-reproducible timings resulting from Windows doing its priority thing.

I suppose the moral of the story is to repeat the timings (many times) - reject the outlying ones, adjust for memory cache effects (very tricky to do), establish the relevant "tight cluster distribution of timing results", and average this (with the usual statistical guff).
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Pete on October 26, 2021, 06:27:54 pm
@Richard Thanks. That's  what I thought. In the old days, there were properties you could set to run an exe at a priority level, but even setting one to high priority was not enough to prevent OS interference. So while all the theory of how to time events is valid, the practical application of such theories is not obtainable unless you could run such a program on some non-OS system, built to boot to the exe and only include the rendering software to display the program, provided none of that software required access to Windows libraries.

Pete
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: SMcNeill on October 26, 2021, 07:34:19 pm
Thank you, Steve, for the insight here.  I have removed the second RANDOMIZE and only triggering one RANDOMIZE (TIMER) at the beginning of the program.  The goal of that 100-loop accumulation was simply to introduce a random delay on each sweep of the code that determines movement of the horses, because I am consistently getting identical times, which is really what I am asking about.

I agree 100 percent that the mean of a series of random numbers between 0 and .999999 approaches .5, and that loop wasn’t doing much, except that probably WASN’T exactly .5, and because _DELAY can use 1/1000ths, it should have been enough to prevent the identical times (to the 1/100000th) happening.  It wasn’t.

I am not the most optimized coder, no question about that, but when I time events using TIMER, with that precision, I still cannot figure out how I am getting identical times all the way to the 1/100000th of a second.  That should be, to my mind, quite impossible….or, since anything is possible, FAR less frequent.

There is too much code to paste here, but the gist of it is….

BEGIN
START RACE
StartTime = TIMER
Race is 1,440 pixels long
Begin Loop
Random numbers between 1 and 3 determine how many pixels forward each horse moves
All 6 horses move, in random order
All horses move forward
Eventually, each horse has moved 1,440 pixels (enough passes of 1, 2 or 3 have happened to add up to 1,440)
First horse crosses finish line
FirstTime = TIMER
FirstTime = FirstFinish - StartTime
Second horse crosses finish line
SecondFinish = TIMER
SecondTime = SecondFinish - TIMER
.
.
.
Sixth horse crosses finish line
SixthFinish = TIMER
SixthTime = SixthFinish - StartTime
End of loop
Race is done - display results
END

Sometimes, there are EXACT ties in a race.  Dead heats happen in horse races, I have no issue with that, though, again, a tie to the 1/100000th of a second seems kind of wildly unlikely.

But run a few of these, and I get some identical times, all the way down to the 1/100000 of a second (I posted a list of 10 races x 6 times).  The 4th place finisher in race #6 will have the identical time to the 2nd place finisher in race #3, for example.  Again, to the 1/100000th of a second.  That just should NOT happen. 

I tried this.  If I run a race where all horses move 3 pixels at a time, all 6 finish at basically the same time, but the first horse to move that last cycle wins by 2/100th of a second.  Makes sense, there is processing time being used.  However, all the other 5 horses have the exact same time down to the 5th decimal place.  Something is strange about this type of thing.

From what you describe above, here's basically your program as best as I can reproduce it without the actual source:

Code: QB64: [Select]
  1. Const HorseSteps = 3
  2. Screen _NewImage(1440, 720, 32)
  3. f = _LoadFont("courbd.ttf", 32, "monospace")
  4.  
  5.     RaceInSession = 0
  6.     Do
  7.         Cls
  8.         steps = steps + 1
  9.         If RaceInSession = 0 Then
  10.             For i = 0 To 5: Horse(i) = 0: FinishTimer(i) = 0: Next
  11.             StartTime = Timer
  12.             RaceInSession = -1
  13.         End If
  14.         Finished = -1
  15.         For i = 0 To 5
  16.             If Horse(i) < 1440 Then
  17.                 Horse(i) = Horse(i) + Int(Rnd * HorseSteps) + 1 '1 to horsesteps per loop
  18.             Else
  19.                 If FinishTimer(i) = 0 Then FinishTimer(i) = Timer - StartTime
  20.             End If
  21.             Line (Horse(i) - 40, 50 * i)-Step(40, 40), -1, BF
  22.             If FinishTimer(i) = 0 Then Finished = 0
  23.         Next
  24.         _Limit 90 / HorseSteps
  25.         _Display
  26.     Loop Until Finished
  27.  
  28.     For i = 0 To 5
  29.         Locate 10 + i, 1: Print "Horse Time: "; FinishTimer(i)
  30.     Next
  31.     Print
  32.     Print "Race Again (Y/N)"
  33.     _Display
  34.     Do
  35.         a$ = UCase$(Input$(1))
  36.         If a$ = "N" Then System
  37.     Loop Until a$ = "Y"
  38.  
  39.  

Now, as to WHY you're running into so many duplicated times, it's once again a process of AVERAGES in your program.

1440 pixels, with each horse taking a step from 1 to 3 pixels.  That's an average of 720 steps for each horse,,,

This type of routine creates a BELL CURVE of probability, with the center values becoming much, much more likely to be the overall result of the running.   For example, let's flip a coin 3 times...  Our possible results are:

Head, head, head
head, head, tail
head, tail, head
head, tail, tail
tail, head, head
tail, head, tail
tail, tail, head
tail, tail, tail

Now, count heads as 0 and tails as 1 and what's your sums?
0
1
1
2
1
2
2
3

1 chance for 0, 3 chances for 1, 3 chances for 2, 1 chance for 3

You've created a bell curve such that the center values are much more likely to occur than the extreme values.  The more times you flip a coin, the greater the extreme between the highest point of the bell curve and the lowest point of that same curve.

In 720 flips of a 3-sided coin, the central probability is going to occur with a quite likely chance.  So much so, that you're ending up with horses which are finishing with basically equal times to their runs.

So how do we fix this type issue of averaging and bell curve probability?

Increase the range of each action and roll fewer dice overall. 

100 coin flips is going to give you a number mighty damn close to 50, with little overall variance.
25 rolls of a four-sided dice is going to give a number mighty close to 50, but with a larger range of variance.
5 rolls of a  twenty-sided dice is going to give a number somewhat close to 50, but with a MUCH larger range of variance.
1 roll of a hundred-sided dice would end up giving you an overall average of 50, but with an equally distributed variance from 1 to 100...


For the above, to change the number of steps and reduce the number of loops, all you have to do is change the value of the HorseSteps constant.  Instead of 720 steps from 1 to 3 pixels, go for steps from 1 to 12 pixels, reducing the number of loops considerably, and spreading out the bell curve of your total times further apart in your program. 
 
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Richard on October 26, 2021, 08:17:51 pm
@Pete @Statsman1

So to sum up (if it is not already obvious) - by running the SQR(2) program (as in  Precision_timer-999.bas above) - in a loop of 20 iterations I get the following:-



  [ This attachment cannot be displayed inline in 'Print Page' view ]  



The first timing is 0.4 micro-seconds (previously when run got 0.5 microseconds). Keep in mind that Windows (because this is all a windows thing) has a resolution of 0.1 micro-seconds - so there is already a round-off error or uncertainty of +/- 0.05 micro-seconds. So a timing of 0.0 microseconds might need to be actually reported as 0.0 micro-seconds +/- round-off uncertainty   and resolving to 100 nano-seconds stated accuracy (by Windows) --->

0.0 +/- 0.1 microseconds 
0.1 +/- 0.1
...
0.4 +/- 0.1 

etc

So if do calculations to highest resolution, but really just work with >= 1 microseconds values then have a somewhat "useable" timing system.


In this simple case (SQR(2)) code - being only one QB64 line - when working with timings >=1 micro-second (i.e. ignore the fraction of micro-second counts) - then the effect of Windows priority may not be so bad. The aspect of "memory cache effects" may not even be relevant in your case since typically the hardware cannot establish the need to cache program code (to make repetitive code run even faster like in say a loop). In the case of the 20 loops being performed, MAYBE at a lower (slower) "cache level" the relevant machine code has been prefetched into a cache and so from loop number 2 to 20, the program runs faster.


Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Statsman1 on October 26, 2021, 09:24:51 pm
@Richard ...

Thank you very much for the code.  I modified it to behave somewhat in the way I am trying to do my thing...

Code: QB64: [Select]
  1. version$ = "Precision_timer-999"
  2. Declare Dynamic Library "kernel32" ' Acquiring high-resolution time stamps  ' https://docs.microsoft.com/en-us/windows/win32/sysinfo/acquiring-high-resolution-time-stamps
  3.     Sub QueryPerformanceCounter (ByVal lpPerformanceCount As _Unsigned _Offset)
  4.     Sub QueryPerformanceFrequency (ByVal lpFrequency As _Unsigned _Offset)
  5. Dim Shared PerformanceCount As _Integer64
  6. Dim Shared StartingCount As _Integer64
  7. Dim Shared dElapsedTime As Double
  8. Dim Shared dElapsedTimeOLD As Double
  9.  
  10. For reps = 1 To 20
  11.     QueryPerformanceFrequency (_Offset(Frequency))
  12.     QueryPerformanceCounter (_Offset(StartingCount))
  13.  
  14.     TIMERe: dElapsedTimeOLD = dElapsedTime
  15.  
  16.     dist = 1440
  17.     draws = 0
  18.     Do
  19.  
  20.         steps = Int(Rnd(1) * 3) + 1
  21.         dist = dist - steps
  22.         draws = draws + 1
  23.  
  24.     Loop Until dist < 0
  25.  
  26.     TIMERe
  27.  
  28.     Print "Time to take 1440 steps =";: Print Using "####.###"; (dElapsedTime - dElapsedTimeOLD) * 1000000;: Print "    Loops =";: Print draws
  29.  
  30. Next reps
  31.  
  32.  
  33. Sub TIMERe
  34.     QueryPerformanceCounter (_Offset(PerformanceCount))
  35.     dElapsedTime = (CDbl(PerformanceCount - StartingCount)) / Frequency

...and attached the results in the first attachment.  I then did the same for 14,400 steps, if you will, and the results are in the second attachment.

Those outliers that you talk about - I guess that can be lived with, as that would impact every horse in a race, not just one.  I am encouraged by the results of the second run - the more loops, the more varied the times seem to be, even for the same number of loops to complete the test.
Title: Re: Bad random numbers, or TIMER limitation...?
Post by: Richard on October 26, 2021, 10:16:42 pm
@Statsman1

Thanks for letting me know about your success with the program.

Just for your info, the two lines immediately following the FOR reps  =  1 to 20 statement can be moved to just outside the loop (i.e. place line before FOR...)

The "frequency" relates to a conversion factor to convert (eventually) computer crystal cycles to 1 second counts - as it is highly unlikely that you would change the clock speed of the computer (or that the processor + hardware is even capable to achieve this on "older computers") - it only needs to be "determined once" (I think the value for all MS compatible computers is 1000000 (or 10000000) - it is actually not determined by windows in any manner I think).

The "StartingCount" I believe relates to clock counts (as 100 nano-second counts) since the computer was restarted (or is it since JAN 1 1972 or something)? In either case for your computer session (i.e. since you did a restart) - likewise it only has to be established once per run.

In fact because you are measuring a time interval of an event (race time) - you are only working with the DIFFERENCE (from start to finish) - so the subtraction of StartingCount (in both TIMERe instances cancel out mathematically). Similarly with Frequency (which can  be taken as being CONSTANT) - that too can be taken out (i.e. program calculate using number of 100 nanosecond counts (= Performance count) and when you finally report (print/display the results then divide Difference in PerformanceCounts by 10000000 to convert to seconds. You may gain a timing improvement of 1 to 10 nanoseconds!. :)

As far as the outliers go - and I am still trying to find a work-around to the problem - in my case (referring to reply # 180 mentioned above) - the outlier WAS usually NOT the first timing in any of my loops (which had a number of code line between timing points) - which is a "killer" in trying to determine which code module was "faster".

So if the outlier occurred within your group of events (rather than start) - it might have the effect (say) of a horse "jumping the rails" to take a short cut to the finish line (or to go back to the starting gate). :)