Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.sys.apple2.programmer > #6314 > unrolled thread

Linear Feedback Shift Register

Back to article view | Back to comp.sys.apple2.programmer

Contents

  Linear Feedback Shift Register Duhast <duhast@123gmail.com> - 2024-09-04 21:39 -0400
    Re: Linear Feedback Shift Register kegs@provalid.com (Kent Dickey) - 2024-09-05 20:13 +0000
      Re: Linear Feedback Shift Register Duhast <duhast@123gmail.com> - 2024-09-10 22:54 -0400
        Re: Linear Feedback Shift Register kegs@provalid.com (Kent Dickey) - 2024-09-12 03:58 +0000
          Re: Linear Feedback Shift Register Duhast <duhast@123gmail.com> - 2024-09-12 19:06 -0400
            Re: Linear Feedback Shift Register D Finnigan <dog_cow@macgui.com> - 2024-09-13 00:49 +0000
    Re: Linear Feedback Shift Register John Ames <commodorejohn@gmail.com> - 2025-01-16 09:36 -0800
      Re: Linear Feedback Shift Register Peter Ferrie <peter.ferrie@gmail.com> - 2025-01-21 15:46 +0000

#6314 — Linear Feedback Shift Register

I'm trying to generate pseudo random numbers 1-255(yes zero is a special 
case).  Following Graphic Gems, and code I found at codebase64 I came up 
with this:

          ORG   $300

          LDY   #$00

XOR      LSR   RAND
          LDA   RAND
          BCC   SKIP
          EOR   #$B8
SKIP     STA   RAND
          STA   $2000,Y
          INY
          BEQ   DONE
          JMP   XOR

DONE     RTS

RAND     DB    $01

I then put the values in text file:

  10 D$ =  CHR$ (4)
  20  PRINT D$;"OPEN RAND"
  30  PRINT D$;"WRITE RAND"
  40  FOR I = 0 TO 255
  50  PRINT  PEEK (8196 + I)
  60  NEXT
  70  PRINT D$;"CLOSE"

Pasted them into a spreadsheet and sorted.  It doesn't work.  There are 
missing numbers, duplicate numbers.  What am I doing wrong?  Is there a 
better method?

[toc] | [next] | [standalone]

#6315

In article <vbb26i$1tf0$1@dont-email.me>, Duhast  <duhast@123gmail.com> wrote:
>I'm trying to generate pseudo random numbers 1-255(yes zero is a special 
>case).  Following Graphic Gems, and code I found at codebase64 I came up 
>with this:
>
>          ORG   $300
>
>          LDY   #$00
>
>XOR      LSR   RAND
>          LDA   RAND
>          BCC   SKIP
>          EOR   #$B8
>SKIP     STA   RAND
>          STA   $2000,Y
>          INY
>          BEQ   DONE
>          JMP   XOR
>
>DONE     RTS
>
>RAND     DB    $01
>
>I then put the values in text file:
>
>  10 D$ =  CHR$ (4)
>  20  PRINT D$;"OPEN RAND"
>  30  PRINT D$;"WRITE RAND"
>  40  FOR I = 0 TO 255
>  50  PRINT  PEEK (8196 + I)
>  60  NEXT
>  70  PRINT D$;"CLOSE"
>
>Pasted them into a spreadsheet and sorted.  It doesn't work.  There are 
>missing numbers, duplicate numbers.  What am I doing wrong?  Is there a 
>better method?

You should use PEEK(8192+I).  That may be the only problem.

And you can optimize the routine a bit:

LOOP	LDA RAND
	LSR
	BCC SKIP
	EOR #$B8
SKIP	STA RAND
	STA $2000,Y
	INY
	BNE LOOP
	RTS

You don't have to save RAND in a memory location at all, just remove the
LDA RAND and STA RAND.  It's important for LFSR to start at a non-0 number
(if you start it with 0, it stays at 0), so I'd initialize RAND to 1 before
the loop.

	LDA #1
	STA RAND

You can see it works with a more elaborate code which counts the occurrence
of each byte at output:

	LDY #0
	LDA #0
CLR	STA $4000,Y
	INY
	BNE CLR
	LDA #1
LOOP	LSR
	BCC SKIP
	EOR #$b8
SKIP	TAX
	INC $4000,X
	INY
	BNE LOOP
	RTS

Where $4000-40ff will have $01 in every position except $4000, and $40B8 will
have $02 (something had to occur twice since $00 is not an output).

Kent

[toc] | [prev] | [next] | [standalone]

#6318

On 9/5/2024 4:13 PM, Kent Dickey wrote:

> You should use PEEK(8192+I).  That may be the only problem.
> 

Ok, it was a brain fart of 4096 vs 8192, and that was corrected, but I 
still get bad numbers.

I was running Applewin, and it gives me one set of numbers, with missing 
ones and duplicates.  I ran it under GSplus, and it gave me different 
numbers, but no missing and one duplicate(but I think I know 
why(executing loop an extra round)), I then ran it on real //gs hardware 
and it matches the GSplus output.

Shouldn't it always generate the same sequence with the same seed?  Does 
the EOR function not work right on a 6502 vs 65816, or is Applewin not 
right?

[toc] | [prev] | [next] | [standalone]

#6319

In article <vbr0q9$3ddnt$1@dont-email.me>, Duhast  <duhast@123gmail.com> wrote:
>On 9/5/2024 4:13 PM, Kent Dickey wrote:
>
>> You should use PEEK(8192+I).  That may be the only problem.
>> 
>
>Ok, it was a brain fart of 4096 vs 8192, and that was corrected, but I 
>still get bad numbers.
>
>I was running Applewin, and it gives me one set of numbers, with missing 
>ones and duplicates.  I ran it under GSplus, and it gave me different 
>numbers, but no missing and one duplicate(but I think I know 
>why(executing loop an extra round)), I then ran it on real //gs hardware 
>and it matches the GSplus output.
>
>Shouldn't it always generate the same sequence with the same seed?  Does 
>the EOR function not work right on a 6502 vs 65816, or is Applewin not 
>right?

Your original code didn't initialize RAND to anything.  So it may vary
between systems.  My modified code initialized it to 1.

Kent

[toc] | [prev] | [next] | [standalone]

#6320

On 9/11/2024 11:58 PM, Kent Dickey wrote:

> Your original code didn't initialize RAND to anything.  So it may vary
> between systems.  My modified code initialized it to 1.
> 
> Kent

In my original code, I DB'd RAND as $01.  I'm not great at assembly, but 
is that not initializing it?

[toc] | [prev] | [next] | [standalone]

#6321

Duhast wrote:
> On 9/11/2024 11:58 PM, Kent Dickey wrote:
> 
>> Your original code didn't initialize RAND to anything.  So it may vary
>> between systems.  My modified code initialized it to 1.
>> 
>> Kent
> 
> In my original code, I DB'd RAND as $01.  I'm not great at assembly, but 
> is that not initializing it?
>

If your assembler takes DB to mean "define a byte within the assembled
object code," then yes. Use the Monitor to check your program after you load
it into RAM, but before you execute it, to verify it is $01.

-- 
]DF$
The New Apple II User's Guide:
https://macgui.com/newa2guide/

[toc] | [prev] | [next] | [standalone]

#6322

On Wed, 4 Sep 2024 21:39:53 -0400
Duhast <duhast@123gmail.com> wrote:

> Pasted them into a spreadsheet and sorted.  It doesn't work.  There
> are missing numbers, duplicate numbers.  What am I doing wrong?  Is
> there a better method?

Punching the assembler snippet into a simulator, it runs as expected,
generating a pseudo-random number sequence that doesn't repeat the seed
until the 255th byte - so, allowing for the 8192-vs.8196 issue that's
already been covered, the problem must be somewhere else.

(Interesting notion to pre-generate a table of values and cycle through
them; it wouldn't be practical for a larger LFSR size, but for a basic
8-bit one it's certainly a nice way to get fast random numbers!)

[toc] | [prev] | [next] | [standalone]

#6323

In Total Replay, we have the luxury of dealing with the 256 element by 
just hard-coding the final store, rather than going up one level of range, 
but otherwise LFSR is a great idea.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.sys.apple2.programmer

csiph-web