News:

Printed Amstrad Addict magazine announced, check it out here!

Main Menu
avatar_AMSDOS

Testing those Assembly 8bit Random Number Generators

Started by AMSDOS, 12:36, 07 November 15

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Alcoholics Anonymous

#50
Quote from: ronaldo on 20:27, 20 November 15
In any case, thank you very much for your considerations and contribution to this discussion. I think we all have the opportunity to learn a lot in this matter :D .

It's one of those things that's fun to think about too.   Incidentally for entropy I also tend to use time spent in the menu screen for the seed.  I have used the quick-and-dirty R register to measure that time in the past but then realized you can't get more than 128 different seeds that way and in reality probably much less depending on the length of the code path.   That means possibly much less than 128 different games.  A counter is better.

Not to derail the discussion but I've also snuck in use of R to generate "random" events inside a quicksort implementation (shocker!!):


      ; enable equality dispersal
   
      jp m, right_squeeze_0    ; if item[lo=pivot] < item[i]
     
      or a
      jr nz, left_squeeze_0    ; if item[lo=pivot] > item[i]
     
      ; item and pivot are equal
     
      ld a,r                   ; instruction count
      and 31                   ; use prime number
      jp pe, left_squeeze_0    ; if parity is even (random event)


The problem being solved here is if quicksort gets an array of equal elements it can degrade to a bubble sort so this is supposed to disperse equal elements randomly to the left and right partitions.  I've taken R, ANDed with a small mask (it's modulo 32 cycles of execution time now) and used parity to decide if the element should go left or right.  The value of R will not be very random because it will depend on a finite number of code paths spiced up a bit by the user comparison function and the data that determines when swaps are necessary.  I still haven't tested this yet but will be doing so when I do some sorting benchmarks.

ronaldo

@Alcoholics Anonymous: if balance between both sets is the goal, why not send alternatively to one then the other?

Alcoholics Anonymous

Quote from: ronaldo on 23:17, 20 November 15
@Alcoholics Anonymous: if balance between both sets is the goal, why not send alternatively to one then the other?

I'm out of registers to remember that information.  There's even a parameter on the top of the stack so adding another one there would lead to some contorted gymnastics to access both.  I'm also trying to avoid using EXX or index registers in the implementation.  If the R thing works, it will be a simple fast solution.  I can already see that "AND 31" was a bad choice because it leads to execution length mod 32 cycles.  The z80 has a lot of instructions that are a multiple of four length so this probably causes cycles shorter than 32 to appear from the AND.  Something relatively prime with z80 cycle lengths and maybe mixing in some bits from the top of R would be better I think.

Powered by SMFPacks Menu Editor Mod