This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.
Messages - Xeda112358
Pages: 1 ... 42 43 [44] 45 46 ... 317
646
« on: December 18, 2013, 06:52:37 pm »
For anything with more than 4 vertices, it completely fills the regions. As to the talk of Sierpinski's Triangle generation, there are many, many ways of doing that. LunarFire mentioned one, and I have previously made some in assembly that are extremely fast. I also like to play with warped versions (such as the one mapping it to a circle). Attached is a screenshot of an animated one that I made that has it warped interestingly.
To answer some questions about what the resulting images mean, the first two screenshots produced Sierpinski's Triangles with decent definition because the pattern of the PRNG was fairly chaotic. If it had been too patterned (like cycling through 0,1,2,0,1,2,0,1,2,...) it would not have made a Sierpinski's Triangle.
For the ones dealing with a square, the first one was a similar pattern that had a very simple and short cycle, so it bounced back and forth between the same order of vertices. If it had jumped halfway each time to random vertices, it would have filled in the whole area (like the last one). The middle one was pretty chaotic, but the fact that it did not generate the appropriate image is due to it having a cycle (albeit a fairly long one).
647
« on: December 18, 2013, 02:49:12 pm »
Quad1 is an example of a PRNG that does not behave chaotically. It is the 2-byte LFSR, compared to the other two. The empty space in Quad2 shows that there is a bias for certain runs of numbers. The empty space in Quad1 shows there is basically only the same pattern over and over.
648
« on: December 18, 2013, 02:47:05 pm »
I have to go to work, but I would be interested to see the iRandom routine tested. This is just a tool for testing pseudo-random number generators.
649
« on: December 18, 2013, 02:37:11 pm »
The Chaos Game is not a 'game' in the standard sense. Instead, it is a mathematical 'game' like Conway's Game of Life or Langton's Ant. There are so many cool, neat things about the Chaos Game, and many uses for it, but that would take a good semester or two just to describe and employ it. Instead, I will describe the basics and the way I am using it at the moment: - Start with a polygon, like a triangle or a square, or something more inventive
- Start at some point, maybe on the perimeter-- it doesn't really matter (well, some deeper investigation will say otherwise, but... )
- Now select a vertex randomly and move halfway to that vertex. Repeat this step many times.
On the surface, it makes neat things happen if you use a triangle-- it actually does not fill it in. There are certain points that can never be reached inside the triangle and in fact, it will make a Sierpinski's Triangle. However, squares and such will be filled in. USES: One of the really cool effects of this deals with the very important part of the iterative step. The key word is "random." If you use an algorithm that cycles, this game will show that with strong biases for certain points. Any common runs or cycles will do this. For example, if you use a square and an RNG that returns the sequence {2,3} more frequently than other pairings with 2, the space between points 2 and 3 will be darker than any other points. Since we cannot produce real "random" numbers, we can test pseudo-random number generators to see if they produce the correct result or where biases might be. A very chaotic PRNG that has a very long period will yield good results. A PRNG that has a shorter period or common runs will produce a less amazing result. Since I have been working on PRNGs, I have been using some simple implementations of the Chaos Game. Below is a code that allows you to add in your own 'Random' routine to test as well as the choice of using a square or triangle. In z80 assembly, we often mask out bits to generate integers in a smaller range like [0,1,2,3] or [0,1,2,3,4,5,6,7] (powers of 2, minus 1 make easy masks). While this is fast and simple, the Chaos Game will tell you if this is actually destroying the chaotic behavior of your RNG. If this is the case, you might have better results using a range that isn't a power of 2. However, this can be more time consuming. It's your pick .nolist #define TASM #define bcall(xxxx) rst 28h \ .dw xxxx #define equ .equ .list shape=4 rand=2 update=1
.org 9D93h .db $BB,$6D bcall(4BD0h) ;_GrBufClr bcall(486Ah) ;_GrBufCpy bcall(4570h) ;_RunIndicOff di ld a,$FD out (1),a ld hl,0 ChaosGame_SierpinskisGasket: in a,(4) ;test ON press and 8 ret z in a,(1) ;test Clear press and 64 ret z ld (coords),hl call Plot ld hl,(coords) srl h srl l push hl #IF update==256 ld a,(count) inc a ld (count),a jr nz,$+5 bcall(486Ah) ;_GrBufCpy #ENDIF call Random #IF shape==3 call L_mod_3 pop hl jr z,ChaosGame_SierpinskisGasket dec a ld a,32 jr nz,$+7 add a,l ld l,a jp ChaosGame_SierpinskisGasket add a,h ld h,a jp ChaosGame_SierpinskisGasket #ENDIF #IF shape==4 and 3 pop hl jr z,ChaosGame_SierpinskisGasket rrca ld b,a ld a,32 jr nc,$+6 add a,l ld l,a ld a,32 rrc b jp nc,ChaosGame_SierpinskisGasket add a,h ld h,a jp ChaosGame_SierpinskisGasket #ENDIF #IF rand==0 ; From CaDan, by Iambian and Geekboy Random: LFSR: ld hl,lfsrseed1 ld a,(hl) rrca ld (hl),a jp nc,+_ xor %00111000 ld (hl),a _: ld l,a ret #ENDIF #IF rand==1 ; From CaDan, by Iambian and Geekboy Random: LFSR2Byte: ld hl,(lfsrseed2) ld a,L rlca xor h rlca ; rlca ; xor h ; rlca xor h rlca adc hl,hl ld (lfsrseed2),hl ld a,h ;for combatability ret #ENDIF #IF rand==2 ; From Zeda's library Random: Rand8: ;Output: L is a pseudo-random number, DE=509, B=0, C=seed1 ;Destroys:A ;Size: 141 bytes ;Speed: fastest: 672, slowest: 796 ;Notes: ; Requires 2 seeds of 1 byte each, seed1 and seed2 ;Method ; We iterates 2 Linear Congruential Generators. 'x' is seed1, 'y' is seed2 ; (33x+17) mod 251 -> x ; (13y+83) mod 241 -> y ; Next, we output the lower 8 bits of x*y mod 509 ; This all gives a period of 60491 (251*241) which should be overkill for games and such ld hl,(seed1) ld h,0 ;multiply by 13 ld b,h ld c,l add hl,hl add hl,bc add hl,hl add hl,hl add hl,bc ;add 83 ld c,83 add hl,bc ;mod_241 ld c,15 ld a,h add a,a add a,a add a,a add a,a sub h add a,l ;139 jr nc,$+6 add a,c jr nc,$+3 add a,c add a,c jr c,$+3 sub c ;store back to seed1 ld (seed1),a ;seed2 ld hl,(seed2) ld h,b ;multiply by 33 ld b,h ld c,l add hl,hl add hl,hl add hl,hl add hl,hl add hl,hl add hl,bc ;add 17 ld c,17 add hl,bc ;--- ;make BC=seed1 ld c,a ;--- ;mod_251 ld a,h add a,a add a,a add a,h add a,l jr nc,$+8 add a,5 jr nc,$+4 add a,5 cp 251 jr c,$+4 add a,5 ;store seed2 ld (seed2),a
ld h,a ld l,b ;H_Times_C sla h \ jr nc,$+3 \ ld l,c add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc add hl,hl \ jr nc,$+3 \ add hl,bc HL_mod_509: ;HL_mod_509 -> HL ld a,h ld d,b srl a rl d add a,h sub d jr nc,$+3 inc d add a,l jr nc,$+4 inc d ccf ld e,a ld hl,509 ex de,hl sbc hl,de jr c,$+6 add hl,de sbc hl,de ret nc add hl,de ret #ENDIF #IF shape==3 L_mod_3: ;Outputs: ; A is the remainder ; destroys L,BC ; z flag if divisible by 3, else nz
ld bc,0306h ld a,l res 4,l rlca rlca rlca rlca and 15 add a,l and 31 ld l,a sra l sra l and b add a,l sub c \ jr nc,$+3 \ add a,c sub b \ ret nc \ add a,b ret ;at most 123 cycles, at least 114, 30 bytes #ENDIF #IF rand==3 ; From Zeda's library Random: Rand24: ;Inputs: seed1,seed2 ;Outputs: ; HLA is the pseudo-random number ; seed1,seed2 incremented accordingly ;Destroys: BC,DE ;Notes: ; seed1*243+83 mod 65519 -> seed1 ; seed2*251+43 mod 65521 -> seed2 ; Output seed1*seed2 ld hl,(seed1) xor a ld b,h \ ld c,l ld de,83 add hl,hl \ rla ;2 add hl,bc \ adc a,d ;3 add hl,hl \ rla ;6 add hl,bc \ adc a,d ;7 add hl,hl \ rla ;14 add hl,bc \ adc a,d ;15 add hl,hl \ rla ;30 add hl,hl \ rla ;60 add hl,hl \ rla ;120 add hl,bc \ adc a,d ;121 add hl,hl \ rla ;242 add hl,bc \ adc a,d ;243 add hl,de \ adc a,d ;243x+83 ;now AHL mod 65519 ; Essentially, we can at least subtract A*65519=A(65536-17), so add A*17 to HL ex de,hl ld l,a ld b,h ld c,l add hl,hl add hl,hl add hl,hl add hl,hl add hl,bc add hl,de ld c,17 jr nc,$+3 add hl,bc add hl,bc jr c,$+4 sbc hl,bc ld (seed1),hl ;seed1 done, now we need to do seed2 ld hl,(seed2) ; seed1*243+83 mod 65519 -> seed1 ; seed2*251+43 mod 65521 -> seed2 ; Output seed1*seed2 xor a ld b,h \ ld c,l ld de,43 add hl,hl \ rla ;2 add hl,bc \ adc a,d ;3 add hl,hl \ rla ;6 add hl,bc \ adc a,d ;7 add hl,hl \ rla ;14 add hl,bc \ adc a,d ;15 add hl,hl \ rla ;30 add hl,bc \ adc a,d ;31 add hl,hl \ rla ;62 add hl,hl \ rla ;124 add hl,bc \ adc a,d ;125 add hl,hl \ rla ;250 add hl,bc \ adc a,d ;251 add hl,de \ adc a,d ;251x+83 ;now AHL mod 65521 ; Essentially, we can at least subtract A*65521=A(65536-15), so add A*15 to HL ex de,hl ld l,a ld b,h ld c,l add hl,hl add hl,hl add hl,hl add hl,hl sbc hl,bc add hl,de ld c,15 jr nc,$+3 add hl,bc add hl,bc jr c,$+4 sbc hl,bc ld (seed2),hl ;now seed1 and seed 2 are computed ld bc,(seed1) ex de,hl call BC_Times_DE ex de,hl ld l,b ld h,0 ld b,h ld c,l add hl,hl add hl,hl add hl,bc add hl,hl add hl,hl add hl,bc add hl,hl add hl,bc ld c,d ld d,e ld e,a ld a,c sbc hl,bc sbc a,b ret nc ld c,43 add hl,bc ret BC_Times_DE: ;BHLA is the result ld a,b or a ld hl,0 ld b,h ;1 add a,a jr nc,$+4 ld h,d ld l,e ;2 add hl,hl rla jr nc,$+4 add hl,de adc a,b ;227+10b-7p add hl,hl rla jr nc,$+4 add hl,de adc a,b
add hl,hl rla jr nc,$+4 add hl,de adc a,b
add hl,hl rla jr nc,$+4 add hl,de adc a,b
add hl,hl rla jr nc,$+4 add hl,de adc a,b
add hl,hl rla jr nc,$+4 add hl,de adc a,b
add hl,hl rla jr nc,$+4 add hl,de adc a,b
;=== ;AHL is the result of B*DE*256 push hl ld h,b ld l,b ld b,a ld a,c ld c,h ;1 add a,a jr nc,$+4 ld h,d ld l,e ;2 add hl,hl rla jr nc,$+4 add hl,de adc a,c ;227+10b-7p add hl,hl rla jr nc,$+4 add hl,de adc a,c
add hl,hl rla jr nc,$+4 add hl,de adc a,c
add hl,hl rla jr nc,$+4 add hl,de adc a,c
add hl,hl rla jr nc,$+4 add hl,de adc a,c
add hl,hl rla jr nc,$+4 add hl,de adc a,c
add hl,hl rla jr nc,$+4 add hl,de adc a,c
pop de ;Now BDE*256+AHL ld c,a ld a,l ld l,h ld h,c add hl,de ret nc inc b ;BHLA is the 32-bit result ret #ENDIF #IF rand==4 Random: ;from ionRandom ld hl,(seed1) ld a,r ld d,a ld e,(hl) add hl,de add a,l xor h ld (seed1),hl ld hl,0 ld e,a ld d,h add hl,de djnz $-1 ld l,h ret #ENDIF #IF rand==5 Random: ld hl,(seed1) xor a ld b,h \ ld c,l ld de,83 add hl,hl \ rla ;2 add hl,bc \ adc a,d ;3 add hl,hl \ rla ;6 add hl,bc \ adc a,d ;7 add hl,hl \ rla ;14 add hl,bc \ adc a,d ;15 add hl,hl \ rla ;30 add hl,hl \ rla ;60 add hl,hl \ rla ;120 add hl,bc \ adc a,d ;121 add hl,hl \ rla ;242 add hl,bc \ adc a,d ;243 add hl,de \ adc a,d ;243x+83 ;now AHL mod 65519 ; Essentially, we can at least subtract A*65519=A(65536-17), so add A*17 to HL ex de,hl ld l,a ld b,h ld c,l add hl,hl add hl,hl add hl,hl add hl,hl add hl,bc add hl,de ld c,17 jr nc,$+3 add hl,bc add hl,bc jr c,$+4 sbc hl,bc ld (seed1),hl ret #ENDIF #IF rand==6 Random: ld hl,(seed2) ; seed2*251+43 mod 65521 -> seed2 xor a ld b,h \ ld c,l ld de,43 add hl,hl \ rla ;2 add hl,bc \ adc a,d ;3 add hl,hl \ rla ;6 add hl,bc \ adc a,d ;7 add hl,hl \ rla ;14 add hl,bc \ adc a,d ;15 add hl,hl \ rla ;30 add hl,bc \ adc a,d ;31 add hl,hl \ rla ;62 add hl,hl \ rla ;124 add hl,bc \ adc a,d ;125 add hl,hl \ rla ;250 add hl,bc \ adc a,d ;251 add hl,de \ adc a,d ;251x+83 ;now AHL mod 65521 ; Essentially, we can at least subtract A*65521=A(65536-15), so add A*15 to HL ex de,hl ld l,a ld b,h ld c,l add hl,hl add hl,hl add hl,hl add hl,hl sbc hl,bc add hl,de ld c,15 jr nc,$+3 add hl,bc add hl,bc jr c,$+4 sbc hl,bc ld (seed2),hl ret #ENDIF Plot: ;need to plot the pixel at HL ld a,l cp 64 \ ret nc #IF update==1 add a,80h out (16),a #ENDIF ld a,h cp 96 \ ret nc ld c,l ld h,0 ld b,h add hl,hl add hl,bc add hl,hl add hl,hl ld b,a rrca \ rrca \ rrca and 0Fh #IF update==1 add a,20h out (16),a add a,20h #ELSE or 40h #ENDIF ld c,a ld a,b ld b,93h add hl,bc and 7 ld b,a inc b ld a,1 rrca djnz $-1 or (hl) ld (hl),a #IF update==1 out (17),a #ENDIF
ret
coords: .db 0,0 count: .db 0 lfsrseed2: lfsrseed1: seed1: .dw 256 seed2: .dw 0
As notes: - Press [ON] or [CLEAR] to exit
- Set shape as 3 or 4 based on the mode you want to compile.
- Set rand accordingly. There are 7 included (0,1,2,3,4,5,6). See below.
- Set update to 256 to update every 256 iterations using the OS routine. This is not recommended. Use 1. It is faster and you see every pixel plotted.
There are 7 included PRNGs and 2 shapes. The shapes are 3 for a triangle, 4 for a square. The PRNGS are: 0 for a 1-byte Linear Feedback Shift Register (LFSR) that I was testing. It is a very fast code and pretty chaotic, but using shape=4 shows that it is actually strongly biased for simple masking. Using shape=3 yields excellent results with some minor bias. (credit goes to Iambian and Geekboy for this) 1 for a 2-byte LFSR, also from Iambian and Geekboy 2 for a much heavier/slower 8-bit PRNG I wrote. It works well for shape=3 and shows some fairly weak bias in shape=4, so it is decent for chaotic behavior 3 for an even larger, slower routine (about half the speed of the previous) but it yields a 24-bit pseudo-random number and passes both test very well. This routine is on par with the OS rand routine, but many times faster (probably hundreds or thousands times faster). 4 is the ION routine 5 and 6 are the LCGs used in (3) You can add your own routines named Random as well, but they should return the result in L. EDIT: Updated the code, added a download with a readme.
650
« on: December 16, 2013, 02:54:10 pm »
I took another approach and now the worst case is 156 t-states:
HL_mod_10: ;Input: HL ;Output: HL_mod_10->A ;156 t-states worst case ;141 t-states best case srl h \ ld a,l \ rra \ add a,h \ adc a,0 ld h,a \ res 4,h rlca \ rlca \ rlca \ rlca and 15 \ add a,h \ and 31 rr l \ rra sub 40 \ jr nc,$+4 \ add a,40 sub 20 \ jr nc,$+4 \ add a,20 sub 10 \ ret nc \ add a,10 \ ret
The approach here basically is to perform mod 5 on the upper 15 bits of HL, then rotate the lower bit of the input back in. This is from the observation that 10=5*2, so no matter what, the lower 1 bit is going to be the same in the input and output. So then I could do (x mod 10) = ((x mod 10)-(x mod 2)) mod 10 + (x mod 2) = (floor(x/2) mod 5)*2 + (x mod 2)
However, from earlier observations, mod 2n+1 and mod 2n-1 are pretty easy in binary. For mod 5 you can add each 2k-bit chunk together where k>1 and perform mod 5 on that. In my code, I add the upper 7 bit of the input to there lower 8 bits, if there is overflow, just add 1 to the 8-bit result. Then I add the upper and lower nibble of that producing at most a 5-bit result. At that point, I rotate back in the low bit, making at most a 6-bit value that can be checked against 10*2{0,1,2}.
651
« on: December 15, 2013, 01:44:11 pm »
I was trying to make an HL_mod_10 routine today employing some of the trickery I used with my Rand24 routine (24-bit pseudo-random number generator). I wanted to make it as fast as I could, so I was wondering if anybody wanted to have a fun game of optimise-the-short-assembly-routine.
My approach was to break HL into two parts as H*256+L. Mod 10, that is equivalent to: (H*260-H*4+L) mod 10=(L-H*4) mod 10
H and L are 8-bit values, so H*4 has the potential of being a 10 bit number. If I call this X*256+Y where X is the upper 2 bits of H*4: (L-H*4) mod 10 = (L-X*256-Y) mod 10 (L-X*256-Y) mod 10 =(L-(X*260-X*4)-Y) mod 10 (L-(X*260-X*4)-Y) mod 10=(L-Y+X*4) mod 10
Now that is an 8-bit subtraction with L and Y. If there is 8-bit 'overflow' with the subtraction, then I need to adjust it by adding a constant. Then, X*4 is at most a 4 bit number to add to that. Once that is all done, you can perform mod 10 stuff on an 8-bit number. I came up with this code:
HL_mod_10 ;Input: HL ;Output: (HL_mod_10 -> A) ;197.75 avg cycles ld a,l ld l,h ld h,0 add hl,hl add hl,hl sub l \ jr nc,$+8 \ add a,4 \ jr nc,$+4 \ add a,6 sla h \ sla h add a,h \ jr nc,$+8 \ sub 4 \ jr nc,$+4 \ sub 6 sub 160 \ jr nc,$+4 \ add a,160 sub 80 \ jr nc,$+4 \ add a,80 sub 40 \ jr nc,$+4 \ add a,40 sub 20 \ jr nc,$+4 \ add a,20 sub 10 \ ret nc \ add a,10 \ ret
It averages a smidge under 197.75 t-states.
EDIT: If anybody wants to modify this for other languages, here is a supplemental explanation: This is the equivalent of HL mod 10: (L-Y+X*4) mod 10
If the input bits of HL are abcdefghijklmnop2, then: L=ijklmnop2 Y=cdefgh002 X=000000ab2
So to put it into an 8-bit value to operate on: ijklmnop2-cdefgh002+0000ab002
If this is >256 (it will be at most 267), then add 6 and keep the lower 8 bits. If this is <0 (it will be at the lowest -255) then take the lower 8-bits (signed, two's complement form), add 4. If that overflows to be >256, then add another 6, keeping only the lower 8 bits. So for example, if ijklmnop2-cdefgh002+0000ab002=-3 → FD+04→10116→01+06→07.
Now perform mod 10 on the 8-bit result. You can apply more tricks to this if you like. abcdefgh2=128a+0bcdefgh2, so if a=1, you can do 0bcdefgh2-2, for example. Or: 0000ab002+00cdefgh2 Or: 0000abc02+000defgh2
652
« on: December 12, 2013, 08:47:08 pm »
I thought I should pop in and say that I found this to be one of the neater ideas. It was lightweight, simple and fun, so good job!
653
« on: December 12, 2013, 07:31:05 pm »
Wooh, excellent job for Merth, now I need to check out the others!
654
« on: December 12, 2013, 06:53:56 pm »
It is most definitely 1, and that is a cool feature of how the Reals work. Think of it this way: Try to find a number between .9999... and 1. You can't and that is why they are equal! I had to take a proof-writing course with a pretty neat professor and he once asked me something like this for homework: Let f(x) be the function that returns the value of the first digit after the decimal point in base 10. Is this a function? (Meaning that f(x)=f(x)) On initial inspection, I thought it was indeed a function and I wrote the proof for it. That was until I realised the morning it was due that .999... =1 and f(.99...) returns 9 and f(1) returns 0, yet the inputs are identical! Crazy shtuff, that
655
« on: December 10, 2013, 08:47:30 am »
LDS is Latter Day Saints, as I am aware of it. This should be a pretty neat experience Will, I hope you enjoy it! I find that I am more motivated after being away from calcs/computers/internet for a while, so maybe you will come back with crazy fantastic motivation and make a Toy Wars 2
656
« on: December 08, 2013, 10:00:27 am »
Checking out Wikipedia's article, the comparison shows that you can't really get much better than that with quaternions. I've been looking into them, too, but also, I don't see why you would only get 10FPS if you were getting so much more with rotation matrices.
657
« on: December 05, 2013, 06:29:21 pm »
Cool! I'll be doing the Putnam for a good chunk of Saturday and finals start next week, so there is a pretty good chance I won't be able to commit time to this. It sounds fun already, though!
658
« on: December 05, 2013, 11:21:13 am »
This also works for the TI-89t, but you could also play with Dialog boxes, too, if you wanted to make it fancier. I don't know what P is since it isn't used in calculations, so I thought it was just an option:
Dialog Title "Title" Request "balance",b,0 Request "rate",r Request "compounds",n Request "time",t DropDown "Option:",{"1","2"},p EndDlog
However, as a warning, B,R,N, and T are strings, so you will need to use expr() on them to convert them to numbers to perform calculations.
You can also make your program into a function if that is easier, but that doesn't prompt for inputs. Still, you could do:
func1(b,r,n,t) Func Local b,r,n,t Return b*(.01r/n)/((1+.01r/n)^(n*t)-1) EndFunc
Then on the homescreen, you could use it just like a regular function.
659
« on: December 05, 2013, 10:26:06 am »
It is likely due to spaces in the filepath name. Also, it seems that ClrHome is down, so I am thinking Deep Thought is too busy
660
« on: December 04, 2013, 03:30:03 pm »
I know you said you wanted an offline solution, but maybe talk to Deep Thought about ORG. It gives an option to output the hex.
Pages: 1 ... 42 43 [44] 45 46 ... 317
|