math.rand() in Berry appears to not very good.....

[trlafleur]

math.rand() in berry appears to not be very good.....

The plot is over 4800 samples.... over a range of 1-198
math.rand was seeded each time

math.srand( int (tasmota.rtc()['utc'] ))        # seed random number
var random = math.rand() % (198) + 1

Is there a better random function in Tasmota that can be called from Berry??
random() as used in Arduino, tends to be more uniform... I have NOT tested it on ESP32...

[sfromis]

Seeding every time is breaking it. Don't do that. At least not with such a terribly bad seed.

Another random source in Berry is crypto.random(8); generates n random bytes.

[trlafleur]

I have tried a number of variants, including one seed per boot... results were just as bad!
where is crypto.random(8) defined?? do I need to seed it?? where is the source code??

[sfromis]

Taking 4800 random numbers after a single seed, I got a lot better results than your plot. And UTC in seconds is a very low-entropy seeding, only varying a few bit in a simple pattern.

crypto.random was mentioned by s-hadinger some time ago, it is part of the cryptographic features integrated in Berry to facilitate coding the Matter support. It is no more complex than what I mentioned, generate a specified number of random bytes, based on esp_fill_random, hardware random number generator getting entropy from RF noise samples. Getting to numbers takes an extra step, like 3 random bytes as a number up to 2**24-1.

[trlafleur]

We have tested using the crypto.random() function in our code, as you can see in the plot, it's still not very flat... statistically it's probably very good but for the ability to select all numbers randomly in a range, it is very bumpy...

var index_found = true
 var x1
  while (index_found)
      x1 = crypto.random(1)[0]
       if ( (x1 >= 1) && (x1 <= 198) )
          index_found = false
       end
   end

A few years back in a commercial music player developed for a company I was involved in, an implantation of the Miller Shuffle Algorithm was developed to solve this issue. It guarantees over a range that all numbers in the range will be randomly selected. We are in the process of implementing it as an extension to the Berry Math Library. If interested, we will do a pull request.

https://github.com/RondeSC/Miller_Shuffle_Algo

static int m_millershuffle(bvm *vm)
{
  unsigned int si, r1, r2, r3, r4, rx, rx2;
  const unsigned int p1=24317, p2=32141, p3=63629;  // for shuffling 60,000+ indexes

  if (be_top(vm) >= 3 && be_isnumber(vm,1) && be_isnumber(vm,2) && be_isnumber(vm,3)) {
    unsigned int inx = be_toint(vm,1);
    unsigned int shuffleId = be_toint(vm,2);
    unsigned int listSize = be_toint(vm,3);

    shuffleID+=131*(inx/listSize);  // have inx overflow effect the mix
    si=(inx+shuffleID)%listSize;    // cut the deck

    r1=shuffleID%p1+42;   // randomizing factors crafted empirically (by automated trial and error)
    r2=((shuffleID*0x89)^r1)%p2;
    r3=(r1+r2+p3)%listSize;
    r4=r1^r2^r3;
    rx = (shuffleID/listSize) % listSize + 1;
    rx2 = ((shuffleID/listSize/listSize)) % listSize + 1;

  // perform conditional multi-faceted mathematical spin-mixing (on avg 2 1/3 shuffle ops done + 2 simple Xors)
    if (si%3==0) si=(((unsigned long)(si/3)*p1+r1) % ((listSize+2)/3)) *3; // spin multiples of 3 
    if (si%2==0) si=(((unsigned long)(si/2)*p2+r2) % ((listSize+1)/2)) *2; // spin multiples of 2 
    if (si<listSize/2) si=(si*p3+r4) % (listSize/2);
    
    if ((si^rx) < listSize)   si ^= rx;			// flip some bits with Xor
    si = ((unsigned long)si*p3 + r3) % listSize;  // relatively prime gears turning operation
    if ((si^rx2) < listSize)  si ^= rx2;
    
    be_pushint(vm,si);
  } else {
    be_pushint(vm,0);
  }
  be_return(vm);
}

[sfromis]

Insisting on a flat-ish distribution of all numbers in a range is simply not random numbers, and a shuffle algorithm is deliberately to avoid numbers being "too random". It may indeed be very useful for some use cases, of which a music player is a great example. Users hate it when randomness gives them same tracks again within a short time, then they complain that it is not random, I just heard that track already this hour. Like when roulette players do not "want" red 12 times in a row, even if it is good randomness.

I ran a quick test with other random number generators, and they provide very similar deviations from the average number of times each slot is hit, compared to both math.rand and crypto.random from Berry. I consider all of these to be good random number generators as long as you do not break them by seeding every time, or such.

But sure, a shuffle generator can be a nice addition instead of actually random numbers.

[dkoneill]

I've written a Miller Shuffle extension and tested it within stand-alone berry and will port that over to Tasmota and we'll give it a try locally in the jukebox. It was my experience as well that users didn't like random playlists for the reasons given and shuffling was an improvement. The shuffling algorithms used the music service also took into account the name of the artist, the album, the year of the song, spacing, and other dimensions to provide a better experience.

[sfromis]

Here's the random numbers drawn in a weekly lotto game in Denmark, year 2021, strictly audited sets of balls for high quality randomness. And a pretty bumpy ride, just as it should be.

Of course, the shuffling inherent in drawing balls does detract a bit from numbers being fully random, but with only a low number drawn each week, the difference due to no repeats does not become major.

[lalo-uy]

Do not forget that random is in hi numbers. 52 weeks is no to hi. How plots looks if generated 100.000 times? El El sáb, 30 de set. de 2023 a la(s) 20:23, sfromis < ***@***.***> escribió:

…

Here's the random numbers drawn in a weekly lotto game in Denmark, year 2021, strictly audited sets of balls for high quality randomness. And a pretty bumpy ride, just as it should be. [image: image] <https://user-images.githubusercontent.com/47082390/271798809-b921e965-fb52-48c2-aca6-abe7d462cb69.png> — Reply to this email directly, view it on GitHub <#19624 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACXBW4OKRDQBDC76KBQHILTX5CSXZANCNFSM6AAAAAA5NBMPHY> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[sfromis]

I did not forget, I just argued against the expectation that random should not be bumpy, and the first suggestion of "too bumpy" was based on only 4800 numbers, and getting better after fixing the flaw in what was first posted. And the "improved " version was with a much lower number of samples, maybe near 1200 instead of 4800, thus getting closer to the lotto numbers example. Your "reminder" of "hi numbers" is just two orders of magnitude more.

Did a similar plot with another random number generator in same order of magnitude as the 2nd originally posted plot, and getting very similar bumpiness, as expected.

[sfromis]

Here's the code above ported to Berry, without needing to be integrated in the Berry runtime. Doing a speed comparison with math.rand(), a simple loop summing 2000 numbers took 160 ms vs 46 ms on an ESP32-C3. The speed of this should be fine for most purposes.

This code can be stored in the Tasmota file system as millershuffle.be. Usage in start comment block.

#-

import millershuffle
var ms = millershuffle.create(123,100)  # shuffleID 123, listSize 100
print(ms.random())                      # next random number in shuffle sequence
print(ms.random(8))                     # reset index in sequence and get random number


See the original code for more info:
https://github.com/RondeSC/Miller_Shuffle_Algo/

Discussed in this thread:
https://github.com/arendst/Tasmota/discussions/19624

-#

var millershuffle_module = module("millershuffle")

class MillerShuffle
  var inx, shuffleID, listSize
  def create(shuffleID, listSize)
    self.shuffleID = shuffleID
    self.listSize = listSize
    self.inx = 0
    return self
  end
  def random(inx)
    if inx == nil
      inx = self.inx
    end
    var listSize = self.listSize  # local var for better speed
    var p1 = 24317, p2 = 32141, p3 = 63629 # for shuffling 60,000+ indexes (only needs 32bit unsigned math)
    var randR = self.shuffleID + 131 * (inx / listSize) # have inx overflow effect the mix
    # compute fixed randomizing values once for a given shuffle
    var r1 = randR % p3
    var r2 = randR % p1 # Now, per Chinese remainder theorem,
    var r3 = randR % p2 # (r1,r2,r3) will be a unique set
    var r4 = randR % 2749
    var halfN = listSize / 2 + 1
    var rx = (randR / listSize) % listSize + 1
    var rkey = (randR / (listSize * listSize)) % listSize + 1
    var si = (inx + randR) % listSize # cut the deck
    # perform the conditional multi-faceted mathematical mixing (on avg 2 5/6 shuffle ops done + 2 simple Xors)
    if si % 3 == 0
      si = (((si / 3) * p1 + r1) % ((listSize + 2) / 3)) * 3 # spin multiples of 3
    end
    if si <= halfN # improves large permu distro
      si = halfN - (si + r3) % (halfN + 1)
    end
    if si % 2 == 0 # spin multiples of 2
      si = (((si / 2) * p2 + r2) % ((listSize + 1) / 2)) * 2
    end
    if si < halfN
      si = (si * p3 + r3) % halfN
    end
    if si ^ rx < listSize # flip some bits with Xor
      si ^= rx
    end
    si = (si * p3 + r4) % listSize # relatively prime gears churning operation
    if si ^ rkey < listSize
      si ^= rkey
    end
    self.inx = (inx + 1) % listSize
    return si
  end
end

millershuffle_module.init =
  def (m)
    return MillerShuffle()
  end
return millershuffle_module

[dkoneill]

This is terrific. When declaring an item of var, are integers represented as 32 bit unsigned or some other value?

Also, If I could recommend a modification to the random() function with relation the incrementing of inx. The Miller Shuffle algorithm works across the length of the list of items to be shuffled, for example, if we are shuffling a deck of cards, the index should range from 0..51. Therefore, a revision to the function could look like this

def random(inx)
    if inx == nil
      inx = self.inx + 1
    end
    inx = inx % self.listSize  
    self.inx = inx
...

[sfromis]

Good point about inx modulo listSize. Code amended, also to have it use inx 0 first time, instead of 1.

Default setup is that numeric vars in Berry are 31-bit signed integer, or single-precision floating point if resulting from non-integer operations. Maybe this would reduce the available max list size, or cause issues? Did a test using signed ints, and the shuffle seemed to work fine generating all numbers, but not using a very large list size.

[dkoneill]

Good catch on the initial value needing to be zero. Do you have a repository for this code already?

[sfromis]

No, you can copy the code from here.

I'd not protest if the code is included in the original repository for the algorithm, and am not claiming any sort of copyright.

[dkoneill]

Here's a repository https://github.com/dkoneill/millershuffle_berry
I made another modification to modulo the input value to random() when it is not nil.

[sfromis]

I've noticed that, a month ago, there was a "significant update" to the https://github.com/RondeSC/Miller_Shuffle_Algo repo. I've not looked into integrating that in the Berry port, or how beneficial that might be.

[dkoneill]

I'll take a look over the next week. The update referenced is to the javascript implementation within the demo .html file.