Groups | Search | Server Info | Login | Register

Groups > comp.lang.forth > #134224

Re: Generating a random sequence of Forth words

Show all headers | View raw

Am 30.09.2025 um 18:33 schrieb Anton Ertl:
> I wanted to generate a random sequence consisting of a number, NOOP,
> and DROP.  When EVALUATEing the sequence, starting with an empty
> stack, it should end with an empty stack, and should not underflow the
> stack.
> 
> I implemented this twice.  The first attempt just generated a random
> word/number in the normal case, and a specific kind of word/number in
> the boundary cases:
> 
> : genseq {: u -- :}
>      0 u 0 do
>          case
>              dup 0= ?of 1+ ." 9 " endof
>              dup i + u u>= ?of 1- ." drop " endof
>              dup i + 1+ u u>= ?of ." noop " endof
>              rnd 3 um* nip 1- dup case
>                  -1 of ." drop " endof
>                  0  of ." noop " endof
>                  1  of ." 8 " endof
>              endcase
>              +
>              0 endcase
>      loop
>      drop ;
> 
> When I do 16 GENSEQ with seed 1234, I get the following sequence:
> 
> 9 drop 9 8 8 noop drop drop 8 noop drop noop noop 8 drop drop
> 
> The requirements are distributed across several places in this word,
> which I did not like.  I also did not like the non-randomness of the
> sequence of DROPs at the end, and the non-randomness of the 9 whenever
> the stack is empty.  I also found that I needed to add a clause for
> when the stack depth is one less than the number of remaining words.
> 
> So I thought about other ways to do it.
> 
> Eventually I came up with the following approach: Starts with counters
> for the different kinds of words/numbers.  Whenever one word/number is
> generated, its counter is reduced.  At each step the probability of
> generating a kind of word/number is proportional to the remaining
> counter for that word/number.  The same-depth requirement is
> implemented by having the same initial counter for the number and
> DROP.  The no-underflow requirement is implemented by skipping the
> output of a DROP if the count of remaining DROPs = the count of the
> remaining numbers.
> 
> Here's the code:
> 
> create counts 3 cells allot
> 
> : initcounts ( u -- )
>      dup 3 / dup counts ! dup counts 2 th ! 2* - counts cell+ ! ;
> 
> : .counts ( -- )
>      counts 3 cell array>mem mem+do
>          i @ 4 .r
>      loop ;
> 
> : countsth-- ( u -- )
>      -1 counts rot th +! ;
> 
> : select1 ( u -- )
>      \ u is the index of the word
>      dup case
>          0 of ." 9 "    countsth-- endof
>          1 of ." noop " countsth-- endof
>          2 of counts @ counts 2 th @ u< if
>                  ." drop " countsth--
>              else
>                  drop endif
>          endof
>      endcase ;
> 
> : sum ( addr u -- u2 )
>      \ addr u is an array with u elements, u2 is the sum of the elements
>      0 -rot cell array>mem mem+do
>          i @ +
>      loop ;
> 
> : genseq ( u -- )
>      initcounts
>      begin
>          counts 3 sum dup while
>              rnd um* nip ( sum )
>              3 0 u+do ( sum1 )
>                  counts i th @ 2dup u< if
>                      i select1 then
>                  - loop
>              drop
>      repeat
>      drop ;
> 
> The code is much longer, but I like it better.  The requirements are
> concentrated in two places.
> 
> 16 GENSEQ generates
> 
> 9 9 noop noop drop noop 9 drop noop drop noop 9 drop 9 noop drop
> 
> for seed 123.  A disadvantage of this approach is that it does not
> generate a word/number on each iteration through the main loop.  I
> have thought about how to achieve this, but the result would be quite
> a bit more complex; it's also only a minor issue.  E.g., for
> generating 1000 words/numbers with seed 123, the main loop has 1036
> iterations.
> 
> The second approach takes quite a bit more time; for generating a
> million words/numbers into a string on a Zen 4, 192_876_892 cycles
> compared to 146_644_156 cycles.
> 
> The original goal was to produce a sequence where various parts of the
> text interpreter have branch mispredictions; the less predictable the
> sequence, the better.  In this respect the second sequence is
> significantly better.  For a sequence of 1000 words/numbers,
> text-interpreted 1000 times, the number of mispredictions is:
> 
> 728_322 first approach
> 821_813 second approach
> 
> (with 247_125 mispredictions coming from (mainly) Gforth startup).
>

How about
1) quick generation of a suboptimal list
2) create an array of pointers to the list elements
3) random shuffle the array e.g.
https://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Generating a random sequence of Forth words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2025-09-30 16:33 +0000
  Re: Generating a random sequence of Forth words minforth <minforth@gmx.net> - 2025-10-01 11:20 +0200
    Re: Generating a random sequence of Forth words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2025-10-01 17:10 +0000
  Re: Generating a random sequence of Forth words Hans Bezemer <the.beez.speaks@gmail.com> - 2025-10-01 17:11 +0200
    Re: Generating a random sequence of Forth words minforth <minforth@gmx.net> - 2025-10-01 20:42 +0200
      Re: Generating a random sequence of Forth words dxf <dxforth@gmail.com> - 2025-10-02 19:49 +1000
        Re: Generating a random sequence of Forth words albert@spenarnc.xs4all.nl - 2025-10-02 13:07 +0200
          Re: Generating a random sequence of Forth words dxf <dxforth@gmail.com> - 2025-10-03 18:22 +1000
        3dup again (was: Generating a random sequence of Forth words) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2025-10-02 20:44 +0000
          Re: 3dup again (was: Generating a random sequence of Forth words) albert@spenarnc.xs4all.nl - 2025-10-03 11:02 +0200
            Re: 3dup again minforth <minforth@gmx.net> - 2025-10-03 11:09 +0200
              Re: 3dup again anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2025-10-04 08:04 +0000
          Re: 3dup again Hans Bezemer <the.beez.speaks@gmail.com> - 2025-10-05 11:29 +0200
  Re: Generating a random sequence of Forth words antispam@fricas.org (Waldek Hebisch) - 2025-10-15 19:19 +0000
    Re: Generating a random sequence of Forth words anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2025-10-24 15:55 +0000

csiph-web