Pseudo Random Bit Pattern generation ideas

Beau Schwabe · 2009-02-21 20:17

Suppose I have 9-Bits, and within the 9-Bits I want a specific number of random bits that would range from 0 to 9.
Anyone have a cleaver code idea for this?
·
Example1:
I want 5 random bits "ON" within the 9-Bits...
·
A few possible results:
%101010101
%110010101
%101100101
%011100110
·
Example2:
I want 3 random bits "ON" within the 9-Bits...
·
A few possible results:
%000010101
%110000001
%001000101
%010000110
·
·
I could·do this with brute force, but I was looking for a small compact elegant solution, I don't care if it's in Spin or Assembly and pseudo random is ok.
·
Thanks
·

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

whicker · 2009-02-21 20:59

Beau, the only thing I can think of is to just shuffle around bits randomly.

in the case of 5 one bits, start with %0 0001 1111

start at the first bit, swap with a random bit location (0 to 8) including itself.
start at the second bit, swap with a random bit.

etc.

not elegant but it would do the job.

Are you trying to do something related to dithering? Where error could be accumulated over more than one 9-bit chunk?

jazzed · 2009-02-21 21:12

Wikipedia mentions the John von Neumann "middle-square method" which I've used on several projects for generating test data. It is primitive but light weight and creates a fair distribution.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Beau Schwabe · 2009-02-21 21:33

whicker,

Interesting... I hadn't thought of it from that end.. starting from the number of bits I wanted "ON' ... I might try that and see which one is faster... I imagine your method would be, because there is no chance of turning on a bit that is already lit up.

Here is my brute force method...

PUB GetRandomDigit(Digit)    ' Digit ranges from 0 to 9
    OldPattern := Pattern 
    Pattern := 0
    if Digit <> 0
       if Digit <> 9 
          repeat
            Pattern := 0
            repeat n from 1 to Digit
              ?Seed 
              Temp := Seed & $FF
              Temp := (9 * Temp)/$FF
              Temp := |<Temp
              If Pattern & Temp == Temp
                 n := n-1
              Pattern := Pattern | Temp
            If Pattern <> OldPattern
               quit
       else
          Pattern := %111111111
    Return Pattern

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Carl Hayes · 2009-02-21 21:52

I'll describe a possible method in a sort of pseudo-Spin. You'll see what I mean.

Result = %000000000
Bitcounter = 0

Repeat
..N := (<random number> // 9)
..If Nth bit of Result not yet set
....Set Nth bit
....Bitcounter := Bitcounter + 1
....If Bitcounter == <desired number>
......quit

Rats, it threw away·my indents.· Putting them back with periods.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
· -- Carl, nn5i@arrl.net

Post Edited (Carl Hayes) : 2/21/2009 9:59:27 PM GMT

heater · 2009-02-21 21:53

If you feel the need for speed put all the possible patterns in a look up table and index it with the random number.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

whicker · 2009-02-21 22:24

Thinking about this further, I guess as a further optimization, if there are more ones than zeroes, like 8 of 9, or %0 1111 1111,
you might as well go %1 1111 1110 and then just shuffle that single zero.

so for zero and nine bits set, the answer is known already.
for 1 to 4 bits set, at most 4 shuffles of 1's are needed.
for 5 to 8 bits set, at most 4 shuffles of 0's are needed.

%000000001
%000000011
%000000111
%000001111

%111110000
%111111000
%111111100
%111111110

The reason I suggest it this way is that the time of completion is known. If you wanted consistent time completion, then 9 swaps would take place regardless of the distribution of 1's to 0's.

Phil Pilgrim (PhiPi) · 2009-02-21 23:11

Beau,

Here's a program that uses the Fisher-Yates shuffle to randomly permute the n least-significant bits of any long. It will do what you want.

[b]CON[/b]

   [b]_clkmode[/b]       = [b]xtal1[/b] + [b]pll16x[/b]
   [b]_xinfreq[/b]       = 5_000_000

   NBITS          = 9

[b]OBJ[/b]

  tv    : "tv_wtext"

[b]PUB[/b] Main | permutation

  tv.start(12)
  permutation := %1111
  [b]repeat[/b]
    permutation := permute(permutation, NBITS)
    tv.bin(permutation, NBITS)
    tv.out(13)
    [b]waitcnt[/b]([b]cnt[/b] + clkfreq)
    
[b]PUB[/b] permute(p, n) | j, k

  'Randomly permute the n least significant bits of p.

  [b]repeat[/b] [b]while[/b] (--n)
    k := |<(||?rand // n)
    j := |<n 
    p := (p & !j & !k) | (p & k <> 0) & j | (p & j <> 0) & k
  [b]return[/b] p

[b]DAT[/b]

 rand          [b]long[/b]      $12345678

-Phil

Beau Schwabe · 2009-02-21 23:17

Phil Pilgrim (PhiPi),

Thanks, I will try tried that out

Edit

Perfect!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Post Edited (Beau Schwabe (Parallax)) : 2/21/2009 11:26:38 PM GMT

jazzed · 2009-02-21 23:29

So you can use the '?' operator [noparse]:)[/noparse] Ok [noparse]:)[/noparse]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Michael O'Brien · 2009-02-21 23:41

Beau,
I don't know if this helps but the center row of bits on Stephen Wolfram's 1-dimensional binary cellular automaton when computing rule 30 is random and ideally fully non-deterministic. The Wolfram CA is based on John von Neumann 29 state and E.F. Codd's 8 state CA's. You would be limited by the size of the array required for simulation and/or if it was toroidal.
Computing the next state of the cell is like moving a 74HC151/251 8-1 line multiplexer across the bit array where - 3 cells at a time form the address on a lookup of the transition rule (30 = 0000:1110)

see
http://mathworld.wolfram.com/Rule30.html

thank you
/michael

Tracy Allen · 2009-02-22 04:13

Beau, if it can't use ? in pasm to generate the random number, maybe it could be an lfsr would do. Executed several times in a row until it again has the correct number of bits. Something like the following. It could be forced to execute at least 9 times to clear out existing bits.

{new 5 of 9 bit pattern snippet}
lfsr5of9       CALL #lfsr1    ' repeatedly calls the lfsr until there are again 5 ones
                  TJNZ sum5bits, #lfsr5of9    ' variable sum5bits=0 when there are 5 of 9 ones
lfsr5of9_ret  RET

lfsr1            XOR x, mask            wc,nr     ' mask for lfsr, carry=1 iff parity odd
    IF_C        ADDS sum5bits, #1   ' will increase number of 1s on odd parity
                   AND x, #$100        wz, nr  ' test bit 9
     IF_NZ     SUBS sum5bits, #1   ' will decrease number of 1s if bit 9 is not zero
                   SHL x, #1         wc      ' okay, shift
     IF_C       OR x,#1       ' and shift in the carry from the XOR
lfsr1_ret      RET  

sum5bits  long  0             ' keeping this at 0 maintains 5 of 9 pattern
x        long  101010101     ' start with a 5 of 9 pattern
mask   long   $802000003    ' for lfsr, a good value for a 32 bit word according to xilinx app note 52

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Phil Pilgrim (PhiPi) · 2009-02-22 05:58

Here's a program I used to compare Spin and assembly versions of the Fisher-Yates shuffle:

[b]CON[/b]

   [b]_clkmode[/b]       = [b]xtal1[/b] + [b]pll16x[/b]
   [b]_xinfreq[/b]       = 5_000_000

   NBITS          = 9

[b]OBJ[/b]

  tv    : "tv_wtext"

[b]PUB[/b] start | permutation, time0, nperline, i

  paddr := @pp
  naddr := @nn
  [b]cognew[/b](@asm_permute, 0)
  tv.start(12)
  permutation := %1111

  nperline := 40 / (NBITS + 1)
  time0 := [b]cnt[/b]
  i := nperline
  [b]repeat[/b] 1000
    permutation := apermute(permutation, NBITS)
{  'Uncomment to display results.
    tv.bin(permutation, NBITS)
    [b]if[/b] (--i)
      tv.out(" ")
    [b]else[/b]
      tv.out(13)
      i := nperline
}
  tv.dec ([b]cnt[/b] - time0)
  
[b]PUB[/b] apermute(p, n)

  'Randomly permute the n least significant bits of p in assembly.

  pp := p
  nn := n
  [b]repeat[/b] [b]while[/b] nn
  [b]return[/b] pp
    
[b]PUB[/b] spermute(p, n) | j, k

  'Randomly permute the n least significant bits of p in Spin.

  [b]repeat[/b] [b]while[/b] (--n)
    k := |<(||?rand // n)
    j := |<n 
    p := (p & !j & !k) | (p & k <> 0) & j | (p & j <> 0) & k
  [b]return[/b] p

[b]DAT[/b]

asm_permute   [b]rdlong[/b]    nn,naddr [b]wz[/b]             'Is there anything to do?
        [b]if_z[/b]  [b]jmp[/b]       #asm_permute            '  No:  Try again.
        
              [b]rdlong[/b]    pp,paddr                '  Yes: Get the bits to permute.

:loop         [b]sub[/b]       nn,#1 [b]wz[/b]                '--nn > 0?
        [b]if_z[/b]  [b]jmp[/b]       #:done                  '  No:  Done.
        
              [b]xor[/b]       rand,taps [b]wc[/b]            'Next random number,
              [b]rcl[/b]       rand,#1                 '  via LFSR.
              
              [b]mov[/b]       acc,rand                'Compute random mod nn
              [b]mov[/b]       accx,nn
              [b]call[/b]      #modulo
              [b]mov[/b]       kk,#1                   'Get second bit into position for swap.
              [b]shl[/b]       kk,mod
              [b]mov[/b]       jj,#1                   'Get first bit into position for swap.
              [b]shl[/b]       jj,nn
              [b]test[/b]      pp,jj [b]wz[/b]                'nz is first bit in pp.
              [b]test[/b]      pp,kk [b]wc[/b]                'c is second bit in pp.
              [b]muxc[/b]      pp,jj                   'Swap bits.
              [b]muxnz[/b]     pp,kk
              [b]jmp[/b]       #:loop                  'Back for all n-1 iterations.

:done         [b]wrlong[/b]    pp,paddr                'Write result.
              [b]wrlong[/b]    nn,naddr                'Write zero to say we're done.
              [b]jmp[/b]       #asm_permute            'Back to wait for more.

modulo        [b]mov[/b]       mod,#0                  'mod := acc // accx.
              [b]mov[/b]       ctr,#32                 '(Wouldn't really need all 32 bits; could be 16.)

:divlp        [b]shl[/b]       acc,#1 [b]wc[/b]
              [b]rcl[/b]       mod,#1
              [b]cmpsub[/b]    mod,accx [b]wc[/b]
              [b]djnz[/b]      ctr,#:divlp
              
modulo_ret    [b]ret[/b]

rand          [b]long[/b]      $12345678               'Random number seed. Anything but 0 is okay.
taps          [b]long[/b]      $8020_0003              'Taps for LFSR. Thanks, Tracy!
naddr         [b]long[/b]      0-0                     'Address of nn.
paddr         [b]long[/b]      0-0                     'Address of pp.

nn            [b]long[/b]      0-0                     'Hub (and cog) container for nn.
pp            [b]long[/b]      0-0                     'Hub (and cog) container for pp.             

acc           [b]res[/b]       1
accx          [b]res[/b]       1
mod           [b]res[/b]       1
jj            [b]res[/b]       1
kk            [b]res[/b]       1
ctr           [b]res[/b]       1

After subtracting the loop overhead, I got the following results per call for the permute routines:

····spermute: 811 µs
····apermute: 92 µs

By reducing the number of bits in the modulo operation to 16 from 32:

····apermute: 67 µs

-Phil

virtuPIC · 2009-02-22 14:58

A completely different approach. You want pseudo randomly set k bits out of a total of n = 9. How many (p) such patterns are possible? Here we get the binomial coefficient: p = n! / ((n - k!) * k!). So you get at most 126 patterns for k = 4 or k = 5.

What about generating a pseudo random number and table lookup?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

Phil Pilgrim (PhiPi) · 2009-02-22 17:22

virtuPIC,

For numbers in this size range (9, 4), that's certainly a solid approach. Now, since you brought it up, can you:

1. write a program that will generate the table?

2. do it without sifting through all 512 binaries and picking just the ones with four bits set?

-Phil

Beau Schwabe · 2009-02-22 19:46

Here is a slightly modified version of Phil's original suggestion.· This version·will·trap any duplicate sequences...· Thanks Phil

PUB RandomizeCharacter(OldPattern,Character)|k,j,p,n     ' Character ranges from 0 to 9
    repeat
      n := 9
      p := |<Character-1
 
      'Randomly permute the n least significant bits of p.
      repeat while (--n)
        k := |<(||?Seed // n)
        j := |<n 
        p := (p & !j & !k) | (p & k <> 0) & j | (p & j <> 0) & k
      if p<>OldPattern or p==|<9-1
         quit  
    return p    
 
DAT
 
Seed                    long      $12345678     '<--- In the final application, this will be seeded with a Real Time Clock.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

virtuPIC · 2009-02-23 07:16

Phil: Yes, I can. But not in the next few hours. Will do it tonight (European time).

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

virtuPIC · 2009-02-23 21:23

Hey Phil, here we go:

'Generates pseudo random values with exactly 4 bits of the lowest nine bits set, all other bits cleared.
'(C) 2009 virtuPIC@gmail.com

'Seeds PRNG and initializes table.
PUB init(seed) | i, i0, i1, i2, i3
  rnd := seed
  i := 0
  i0 := 1
  repeat until i0 => 512
    i1 := i0 << 1
    repeat until i1 => 512
      i2 := i1 << 1
      repeat until i2 => 512
        i3 := i2 << 1
        repeat until i3 => 512
          if i => 126
            abort 'catch internal error (should not be reached)
          tab[noparse][[/noparse]i++] := i0 | i1 | i2 | i3
          i3 <<= 1                   
        i2 <<= 1
      i1 <<= 1
    i0 <<= 1
  if i <> 126
    abort 'catch internal error (should not be reached)

'Returns pseudo random value
'N.B.: values are not perfectly equally distributed! However, mismatch is smaller than 1 PPM.  
PUB fourofnine
  return tab[noparse][[/noparse]||?rnd // 126]

VAR
  long rnd
  word tab[noparse][[/noparse]126]

You can replace the dynamic table init by a table constant generated by an external program like this one:

// Generates table for alternative version of forofnine.spin
// (C) 2009 virtuPIC@gmail.com
#include <stdlib.h>
#include <stdio.h>

int main() {
  int i, i0, i1, i2, i3;
  i = 0;
  i0 = 1;
  while (i0 < 512) {
    i1 = i0 << 1;
    while (i1 < 512) {
      i2 = i1 << 1;
      while (i2 < 512) {
        i3 = i2 << 1;
        while (i3 < 512) {
          if (i >= 126) {
        printf("i too large: %d", i);
        exit(1);
      }
      i++;
      printf("$%x", i0 | i1 | i2 | i3);
      if (i < 126) {
        printf(",");
      }
      printf("\n");
      i3 <<= 1;
    } 
    i2 <<= 1;
      }
      i1 <<= 1;
    }
    i0 <<= 1;
  }
  if (i != 126) {
  printf("i wrong on exit: %d\n", i);
    exit(1);
  }
  return 0;
}

As usual, optimality depends on application. Calculating the table on the prop at start up needs some time. I haven't looked at the size. Cannot tell which version consumes more memory.

And a warning at the end: I have only statically tested the SPIN code. Be prepared for bugs.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

Phil Pilgrim (PhiPi) · 2009-02-23 22:03

virtuPIC,

Nicely done!

-Phil

Beau Schwabe · 2009-02-24 01:37

virtuPIC,

Thanks for posting your code.... I think though since I don't really need the speed at all for my application, and since I already have it implemented in code I will use Phils' permutation method.· With the few Checks I have added in place for a 0 or 9 it only uses 20 longs of program space.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Ken Peterson · 2009-02-24 01:38

pub set_random_bits(size, num) | large, temp
  result~
  large := (num > (size>>1))
  if large
    num := size-num
  while(num)
    temp := result | (|<(cnt? // size))
    if temp <> result
      result := temp
      num--
  if large
    result ^= |<size - 1

Not very deterministic, but the code isn't very long.

What it does is set less than half the bits. If your number of bits to be set is more than half the size, it sets the number of bits that should be zero and then inverts the result. This way you always have a >=50/50 chance of the random bit not having already been set.

For execution speed, the worst case scenario will be when the number of bits to be set is equal to half the total number of bits.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
·"I have always wished that my computer would be as easy to use as my telephone.· My wish has come true.· I no longer know how to use my telephone."

- Bjarne Stroustrup

Post Edited (Ken Peterson) : 2/24/2009 2:09:23 AM GMT

virtuPIC · 2009-02-24 09:30

Okay. Since this thread doesn't come to an end what about this one:

code deleted for two reasons:

It was wrong. Could have caused problems if used.
It was wrong. So embarassingly wrong! Shame on me!

We could also replace the operations 'x // c' by 'x ** (2^32 ) / c' to accelerate. Well, 'x // 8' can even be done be 'x & 0x3'...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

Post Edited (virtuPIC) : 2/25/2009 9:43:12 AM GMT

virtuPIC · 2009-02-24 14:13

Oops! Good that nobody else has talked about probabilities. My last recent program does not produce all patterns at the same probability! However, if you replace the PRNG-call with a counter you can use it as a generator for the table in my other program, too...

Maybe I think a little about the program with mixed probs and fix them. Yeah, I know. Nobody will use it anyway. But it's demanding. And it's fun.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

Tracy Allen · 2009-02-24 18:34

App note 52 from Xilinx has a table with taps for LFSRs from 3 to 168 bits long, vetted for period length and presumably other statistical properties. Nevertheless, single iterations of LFSRs are not great for bytes etc, due to the steady march of bits in one direction. That will be irrelevant in Beau's application, I think, and with the additional permutations or lookups.

But that brings me to my math question. The Spin operator ? is, according to the manual, an LFSR that can be used forward ?X or in reverse X? Neat! Retrace steps. But how does an LFSR do that? The manual states.
The Propeller chip’s Random output is reversible; in fact, specifically it is a 32-bit
maximum-length, four-tap LFSR (Linear Feedback Shift Register) with taps in both the LSB
(Least Significant Bit, rightmost bit) and the MSB (Most Significant Bit, leftmost bit)
allowing for bi-directional operation.

However, it is not as simple as shifting right with the same set of taps. For example, taps=$802000003 is a four tap mask with taps in both the lsb and msb, however, it does not take long to come up with a counterexample, where the left shift is not reversible with a right shift using the same taps. Short of iterating the forward map 2^32-2 times, is there a trick to make it reversible? Looking shallowly on line, it looks like there exists a complementary set of taps, that mathematically can generate the reverse sequence. But the circuit to do it is not trivial, example here. Hmmm...to echo the Joker, how does he do that?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Phil Pilgrim (PhiPi) · 2009-02-24 19:29

Tracy,

The key element is that the bit that gets shifted out is involved in the XOR process. That way, the XOR product that gets shifted into the other end can be used to reconstruct this bit from the other taps. In this case, the taps for the reverse case are just the same taps as for the forward case, rotated by one position in the direction of the original shift. (You don't really have to have both the MSB and LSB set in the original mask — just the one corresponding to the bit that gets shifted out.) For example, if your original mask is %11010000_00000001, and you're shifting right, the new mask for shifting left will be %11101000_00000000. This is enough to reconstruct the bit that got shifted out in the forward direction and to shift it back into the other end.

-Phil

Fred Hawkins · 2009-02-25 03:01

Tracy, the attraction of lfsr is that it will give every number of a given set of integers in a pseudorandom order without duplication before starting over. So an array of nine bit numbers, randomly arranged, could simulate a lfsr.

It occurs to me now that you could just keep a set of constants, one for each bit. Just add (or not) them to build your new instance.

binary:
0_0000_0001
0_0000_0010
...
1_0000_0000

Arrange these randomly, maybe following the 4 bit lfsr's order which has nice properties.

then you need a set of eight starting instances of one set bit through 8 set bits.

To get an new instance of any of these, run a nine step loop that shifts off a bit from the old instance, and if it's set, add the nth binary to your new instance. If you keep track of the number of adds, you can even drop out of the loop when you have set the appropriate number of bits.

My guess is that it's random enough. You could reshuffle the binary array every now and then if you're worried about that.

Post Edited (Fred Hawkins) : 2/25/2009 3:09:29 AM GMT

Tracy Allen · 2009-02-25 08:26

Thanks Phil. I was way over-complicating! I see what you mean about the key. It helps to think about it as one step in each direction, and how to solve for the unknown bit. Let me see if I've got it...
Say for these taps for the 32 bit lfsr
$8020_0003 for shift left
with the new lsb from
x0 := x31 ^ x21 ^ x1 ^ x0
with x31 being lost after the shift, but it can be recomputed from the new x0 along with the now shifted x1, x2 and x22.
The taps for shift right would be
$0040_0007
with new msb from
x31 := x22 ^ x2 ^ x1 ^ x0

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

virtuPIC · 2009-02-25 10:00

Regarding bidirectional LFSR, if I remember correctly an n bit LFSR implements a polynomial multiplication with the tap sequence interpreted as a polynomial modulo xⁿ in GF(2). Each single step is such a modulo-multiplication. If you want to step back you have to divide by the tap sequence polynomial modulo xⁿ. You won't loose information since the multiplication in GF(2) mod xⁿ is a group operation and the tap sequence polynomial is primitive if you have maximum period taps. Yes, that's computer algebra. It's weird. It's complicated. I looked around on the net but couldn't find any comprehensive, complete explanation.

If you look at en.wikipedia.org/wiki/LFSR you will find two possible implementations in hardware (Fibonacci and Galois) giving different sequences. Maybe we should try to rewire them that each clock to the SR gives backward change? Or simply look it up in the code of the SPIN interpreter?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

virtuPIC · 2009-02-25 10:04

Well, my last posting was a little theoretical. But here I am again for the practical part. My last implementation was so embarrassing wong that I deleted the code in shame. But I have a new idea:

' alternative version of fourofnine.spin
' (C) 2009 virtuPIC@gmail.com

' differences:
' + k_of_9 instead of 4_of_9
' + less memory consumption
' - much slower

' Initializes
PUB start
  ' Seed PRNG
  rnd = cnt | 1

' return value with k randomly selected bits out of the 9 LSBs
PUB fourofnine(k) | idx, sel, pat
  pat := 0
  ' Initialize list of bit positions
  ' Could be accelerated by assigning longs instead of words
  repeat idx from 0 to 8
    pos[noparse][[/noparse]idx] := |< idx
  repeat idx from 0 to k - 1
    sel := ?rnd // 9 - idx
    pat |= |< pos[noparse][[/noparse]sel]
    pos[noparse][[/noparse]sel] := pos[noparse][[/noparse]9 - idx]

VAR
  word pos[noparse][[/noparse]9]
  long rnd

Again, the Propeller Tools swallows it, but I haven't run it so far.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Airspace V - international hangar flying!
www.airspace-v.com/ggadgets for tools & toys

Pseudo Random Bit Pattern generation ideas

Comments