Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Pseudo-random number generator, set complete?
2011-11-28 01:00
Style

Registered: Jun 2004
Posts: 498
Pseudo-random number generator, set complete?

Hi all

Im looking for an algorithm that will generate random-looking numbers from 1 - 1000, but will only ever select any one number once. Obviously this is for the 64 screen :)

I seem to recall set complete pseudo-random algorithms at uni but cant recall much more. Any advice?

thanks
2011-11-28 01:48
chatGPZ

Registered: Dec 2001
Posts: 11386
my usual approach to this kind of problem is the "card shuffle" algo, ie use a regular prng and shuffle a sorted set with it. i remember "set complete" prng though, but if i recall correctly they always had a fixed size (usually 2^n) and size of the set, which is not always useful.
2011-11-28 02:03
Style

Registered: Jun 2004
Posts: 498
A 2^10 set complete prng would be cool :)

shuffling a list of 1000 16 bit numbers = ~2k = expensive......

What I might do is come up with a shuffled list of say 100 8 bit numbers, and then reuse them 10 times. It would look bad if the number was divisible by 40, but maybe 100 would look ok.....

2011-11-28 02:25
chatGPZ

Registered: Dec 2001
Posts: 11386
just looked at some old source of mine, where i used this one to clear a bitmap.... not sure how much it is what you want, but it seemed to work for me:
getrandom:

         lda random+1
         sta temp1
         lda random
         asl a
         rol temp1
         asl a
         rol temp1
         clc
         adc random
         pha
         lda temp1
         adc random+1
         sta random+1
         pla
         adc #$11
         sta random
         lda random+1
         adc #$36
         sta random+1

         rts

temp1:   .byte $5a
random:  .byte %10011101,%01011011
2011-11-28 03:24
Style

Registered: Jun 2004
Posts: 498
cool groep, thanks for that, Ill see what it does when I get home :)
2011-11-28 04:44
King Durin
Account closed

Registered: Oct 2007
Posts: 85
You could always calculate 100 cells and then on each iteration EOR the cell so that the pattern appears more random on the screen. You could also shift your starting point randomly so you aren't always starting at $FF which would enhance the randomness of the display.
2011-11-28 05:05
JackAsser

Registered: Jun 2002
Posts: 2014
Or use any of the 8-bit pseudorandom algorithms on Codebase. They produce a series of 0-255 in a shuffled manner, where each value is covered exactly once. Then use 4 seeds at the same time to cover 0-1023 and use that to randomize your screen, promptly ignoring the 24 byte overflow.
2011-11-28 08:26
ready.

Registered: Feb 2003
Posts: 441
I happened to have the same problem when fading pseudo-randomly the last pic in the demo Aurora 100%. This code produces pseudo random sequences from 0 to $f, but it actually has a 0-$ff range, then you can clip it by changing max_no. It is nice since it does not require any table and is very compact in memory, ok the below version is adapted so you can see the output on the screen. Press space to generate more sequences.
You can easily adapt it in order to generate sequences from any number to any number.

Furthermore it tells you when the set is complete.


	*=$0801
	.byte $0c,$08,$0a,$00,$9e
	.byte 0+$30,2+$30,3+$30,0+$30,4+$30 ;start address

*=$0900
	;clear screen
	jsr $e544
	;prepare zero page vector for screen output
	lda #<$0400
	sta zp
	lda #>$0400
	sta zp+1
	;start CIA2 counter to be used as rnd number generator (counts down from $ffff continously)
	lda #$ff
	sta $dd04
	sta $dd05
	lda #%00010001
	sta $dd0e
	;y is the char x-position pointer on the screen
	ldy #0
	
m_001
	lda no ;no is the tune number 0-255 you want to load
	clc
	adc increment
	sta no
	bcc m_002
	;when no > 255 pass = pass +1
	inc passes
	lda passes
	cmp increment
	bne m_002
		;when passes = increment the random sequence has been completed (all number from 0 to 255 has been pulled out)
		lda zp
		clc
		adc #40 ;add one row to display
		sta zp
		lda zp+1
		adc #0
		sta zp+1
		lda #0
		sta passes
m_006
		lda $dd05 ;loads new random number
		ora #1 ;random number must be an odd number
		sta increment
		sta no
		ldy #0 ;reset char x-position pointer on screen
		inc rows
		lda rows
		cmp #20 ;when row = 20 then wait for spacebar
		beq m_exit		
		
m_002
	lda no
	cmp #max_no ;max number of sequence, can be any from 0 to 255
	bcc m_000
	jmp m_001
m_000
	tax
	lda number_tbl,x ;generate char to be displayed
	sta (zp),y	 ;put char on screen
	iny
	jmp m_001
	
	
m_exit
	;wait for spacebar and generate more sequences
	lda #0
	sta rows
	lda $dc01
m_008
	cmp $dc01
	beq m_008
	jmp $0900
	rts
;variables
number_tbl .byte $30,$31,$32,$33,$34,$35,$36,$37,$38,$39,$01,$02,$03,$04,$05,$06
zp = $2
rows .byte 0
passes .byte 0
no .byte 1
increment .byte 13
max_no = $10
2011-11-28 22:38
Krill

Registered: Apr 2002
Posts: 2980
I think that a regular LFSR algorithm with 10 bits should be alright. If you trip on something between 1000 and 1024, simply call the routine another time. Pretty unlikely to need more than 2 attempts to get your next unique number within shuffle range..
2011-11-28 23:48
Digger

Registered: Mar 2005
Posts: 437
This thread reminds me of a basic program I wrote back in '96 – Randomizer™ and released today.

It only does up to 256 values but I thought it would be nice to unleash it ;) Enjoy.
2011-11-29 00:20
Krill

Registered: Apr 2002
Posts: 2980
Oh, and i just see groepaz's solution plus ANDing with $03ff and retry until y <= 1000 would be pretty similar to what i meant.. :)
2011-11-29 01:41
Style

Registered: Jun 2004
Posts: 498
Thanks for mentioning LFSR krill. Id never come across them before, but that's exactly what I need. And yep, that looks like what Groep's routine is doing - of course, Ill have to write my own, otherwise Ill have to credit Groep :)
2011-11-29 01:45
chatGPZ

Registered: Dec 2001
Posts: 11386
hihi... this routine isnt mine either... or well, the algo isnt :)
2011-11-29 02:07
Style

Registered: Jun 2004
Posts: 498
pfffft...... dirty ripper

:)
2011-12-15 07:00
ChristopherJam

Registered: Aug 2004
Posts: 1409
or, could use the old linear congruential. Here's x=(x*261+117)%1024:

genRand
; perform rand'=(rand*261+117)%1024
	lda rand
	asl
	rol t4hi   ; don't need to init t4hi, as only using bottom two bits
	asl
	rol t4hi
	clc
	adc rand
	sta rand
	lda t4hi
	adc rand+1   ;a::rand' is now rand*5
	clc
	adc rand     ;(a::rand')%1024 is now (rand*261)%1024
	sta rand+1

	clc
	lda rand
	adc#117
	sta rand
	lda rand+1
	adc#0
	and#3
	sta rand+1
	rts

rand
	lda#0
t4hi
	brk

(cf http://en.wikipedia.org/wiki/Linear_congruential_generator . The 117's an arbitrary odd number, and the multiplier must be one more than a multiple of four )
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Acidchild/Padua
Linus/MSL
Chesser/Blazon
AMB/Level 64
Guests online: 104
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.6)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 Dawnfall V1.1  (9.5)
7 Rainbow Connection  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Libertongo  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Triad  (9.3)
5 Censor Design  (9.3)
Top Fullscreen Graphicians
1 Joe  (9.7)
2 Sulevi  (9.6)
3 The Sarge  (9.6)
4 Veto  (9.6)
5 Facet  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.073 sec.