Author Topic: Bad random numbers, or TIMER limitation...?  (Read 7757 times)

0 Members and 1 Guest are viewing this topic.

Offline Statsman1

  • Newbie
  • Posts: 36
  • I'm just a jerk, but a hero is what I want to be.
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #15 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?

Good decisions come from experience.
Experience comes from bad decisions.

Offline Cobalt

  • QB64 Developer
  • Forum Resident
  • Posts: 878
  • At 60 I become highly radioactive!
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #16 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.
Granted after becoming radioactive I only have a half-life!

Offline Statsman1

  • Newbie
  • Posts: 36
  • I'm just a jerk, but a hero is what I want to be.
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #17 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.

Good decisions come from experience.
Experience comes from bad decisions.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #18 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.  

Offline Statsman1

  • Newbie
  • Posts: 36
  • I'm just a jerk, but a hero is what I want to be.
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #19 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.

Good decisions come from experience.
Experience comes from bad decisions.

Offline Richard

  • Seasoned Forum Regular
  • Posts: 364
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #20 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)

Offline Bert22306

  • Forum Regular
  • Posts: 206
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #21 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

Offline Statsman1

  • Newbie
  • Posts: 36
  • I'm just a jerk, but a hero is what I want to be.
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #22 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!
Good decisions come from experience.
Experience comes from bad decisions.

Offline Richard

  • Seasoned Forum Regular
  • Posts: 364
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #23 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.

Offline Pete

  • Forum Resident
  • Posts: 2361
  • Cuz I sez so, varmint!
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #24 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
Want to learn how to write code on cave walls? https://www.tapatalk.com/groups/qbasic/qbasic-f1/

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #25 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.

Offline Richard

  • Seasoned Forum Regular
  • Posts: 364
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #26 on: October 26, 2021, 05:40:20 pm »
@Pete


refer to the following

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).

Offline Pete

  • Forum Resident
  • Posts: 2361
  • Cuz I sez so, varmint!
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #27 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
Want to learn how to write code on cave walls? https://www.tapatalk.com/groups/qbasic/qbasic-f1/

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • View Profile
    • Steve’s QB64 Archive Forum
Re: Bad random numbers, or TIMER limitation...?
« Reply #28 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. 
 
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Richard

  • Seasoned Forum Regular
  • Posts: 364
    • View Profile
Re: Bad random numbers, or TIMER limitation...?
« Reply #29 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:-



  [ You are not allowed to view this attachment ]  



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.