| Author |
Message |
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
 Posted: 09 Dec 2007 01:34:46 pm Post subject: |
|
|
thornahawk wrote: Attached to this post is the paper by P. L'Ecuyer on the algorithm used by TI calculators to generate pseudorandom numbers, as published in the Communications of the ACM.
There is a Pascal implementation of the specific "combined linear congruential generator" used in TI calculators in the paper, but what I have yet to figure out is how to seed it so that it acts like rand in the calculators after being stored to by a seed.
thornahawk
[post="114738"]<{POST_SNAPBACK}>[/post]
I believe I've got it. Here's how the generator works explicitly:
The calculator stores two integer seeds which we'll call s1 and s2.
When the OS requests a random number, the following calculations are done:
s1 = 40 014 s1 mod 2 147 483 563
s2 = 40 692 s2 mod 2 147 483 399
Z = (s1-s2) / 2 147 483 563
If Z <= 0, Z = Z+1.
Z is returned as the random number.
So far this is exactly as recommended in the aforementioned paper; the constants used are the ones suggested for 32-bit computers because they don't fit in 16 bits, but that didn't matter for TI since they use floating-point numbers throughout.
When an integer N is stored to rand, s1 is set to 40 014 N, and s2 is set to N (note, however, that calculations will be done on these two seeds before they're used to generate a random number). The exception is when 0 is stored to rand, in which case s1 is set to 12 345 and s2 is set to 67 890. For non-integer N, as has been previously said, the calculator takes the integer part; also, only the first nine digits of the number are taken if it's too big.
As mentioned in the paper, the period of this generator is approximately 2.30584x1018.
Last edited by Guest on 31 Oct 2009 07:24:06 pm; edited 1 time in total |
|
| Back to top |
|
|
alexrudd
pm me if you read this
Bandwidth Hog
Joined: 06 Oct 2004
Posts: 2335
|
| Posted: 09 Dec 2007 04:48:48 pm Post subject: |
|
|
| I have an idea where this could apply. |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 09 Dec 2007 05:05:50 pm Post subject: |
|
|
Hm. I was "slightly" incorrect in that topic when I said there were 1e14 seed values - there are 1e9 because the calculator ignores most digits. So a 5x5 sprite, not a 6x7 sprite, is the limit. It would probably be possible to calculate those, but using a computer, not a calculator.
Edit: here's an implementation of the RNG in Java.
Last edited by Guest on 09 Dec 2007 06:24:26 pm; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 09 Dec 2007 07:18:59 pm Post subject: |
|
|
*applause* :D
DarkerLine, would you mind telling us how you figured out the seeding scheme used?
This particular one got me laughing and shaking my head:
Quote: when 0 is stored to rand, in which case s1 is set to 12 345 and s2 is set to 67 890
thornahawk |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 09 Dec 2007 07:26:26 pm Post subject: |
|
|
Getting back to the idea of a "magic compression" algorithm, if we were to try and equate every possible sprite of a certain dimension with a specific seed, there would have to be zero duplicates emanating from those seed values. Why? The best we can hope for in terms of minimizing the number of digits in the seed values is that all sprites are represented by 0 through 2^(height×width of the images)-1, in some order. This falls back to simply using those numbers 0–n and then converting them to binary. It should go without saying that the probability of random numbers being optimally interchangeable with regular decimal numbers is nil.
I've even tried extrapolating this to text, as seen here:
Last edited by Guest on 09 Dec 2007 07:34:22 pm; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 09 Dec 2007 09:26:07 pm Post subject: |
|
|
thornahawk wrote: *applause* :D
DarkerLine, would you mind telling us how you figured out the seeding scheme used?
This particular one got me laughing and shaking my head:
Quote: when 0 is stored to rand, in which case s1 is set to 12 345 and s2 is set to 67 890
thornahawk
[post="117024"]<{POST_SNAPBACK}>[/post]
And using 12345 and 67890 is not terrible, in that both numbers are co-prime with their respective moduli. If they weren't, that might have reduced the period (e.g. it would be a quadrillion rather than a quintillion, and would take slightly less than a million years to go through on a calculator, which would be terrible).
Here's a cute little result: if you seed rand with 196164532 then get a random number from rand, it will return 1. Sweet!
Last edited by Guest on 14 Dec 2007 01:58:10 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 23 Jan 2008 05:04:01 pm Post subject: |
|
|
I said earlier that a one-to-one correspondence between seeds and images is unlikely, but there is a way to allow for each seed to be useful in multiple situations.
An introductory example: 1,0,1,0,1,1,0,0,1,1,1,1,1,0,0,1
This can be put in a form of RLE where the first bit is designated as being either "on" or "off," with subsequent numbers counting the lengths of alternating "groups" of ones and zeros—1,1,1,1,1,2,2,5,2,1. This is all very basic – it's even easy enough to predict the effectiveness of this method by counting the number of groups in the starting list, which can be done with 1+sum(not(not([font="times new roman"]∆List(L1.
The challenge here is how to go about reducing the number of groups without losing information. Uncompressed, the list has 9 groups. XORing it with a different list can make that number smaller, but the means of storing the key list has to be compact enough to still make the difference. A well-chosen seed will do this. (And better yet, the seed would still be able to apply to other cases!)
With the above example and a "key" of 1: 1→rand:L1 xor int(2rand(dim(L1
1+sum(not(not([font="times new roman"]∆List(Ans returns 10 (groups), so this would add on to the number of elements in the abbreviated list; it'd be better to use a different key here and save the one in use for when it can be found useful. Moving on to using 2 as the key, we get a list of just 6 groups. We'll end up having to add in that key as part of the encoding, but with 3 groups shaved off, we've benefited from this process in the long run.
But keep in mind that better keys may exist – 7 is the best single-digit key in this circumstance, but a key of 42 will produce better results. Theoretically, the best key lists would equal L1 or not(L1, but with the abundance of other profitable seed values lying around, this is probably (in the truest sense of the word) a much more realistic hunt among all other random number searches.
Just something to think about, and perhaps use as a basis for writing a program or two.
Last edited by Guest on 30 Aug 2010 08:15:11 pm; edited 1 time in total |
|
| Back to top |
|
|
luby
I want to go back to Philmont!!
Calc Guru
Joined: 23 Apr 2006
Posts: 1477
|
| Posted: 23 Jan 2008 05:52:41 pm Post subject: |
|
|
| On a related note, I added to Darkerline's code and made it so you can find whatever rand you want. All you do is run Finder. It will ask you for a double and number of places. The double is the rand you are looking for and number of places is to how many decimal places you want accuracy. |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 23 Jan 2008 08:51:15 pm Post subject: |
|
|
Note to stranger: your question has been moved (you can find it here) because it had nothing to do with this topic.
As for the compression method - I don't think this can be better, on average, than just encoding the sequence of ones and zeros in binary.
Last edited by Guest on 23 Jan 2008 09:57:51 pm; edited 1 time in total |
|
| Back to top |
|
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
| Posted: 24 Jan 2008 01:12:09 am Post subject: |
|
|
Then I'll propose a modified RLE where the run each step cannot exceed 9, and zeros are inserted to prevent interruption by the intermediate changes in color. That is, if every element "A" of length 10 or greater is substituted by augment(9-18fPart(seq(X,X,1,int(A/9),.5)),{0,9fPart(A/9, then the numbers in the list are restricted to single digits, but the list itself would logically produce the exact same image. The list can then be exchanged for a string without commas.
Converting this picture  (including borders) into binary, we get a number that, in base ten, has 309 digits.
The string RLE...
[font=courier new]19090906909090329011219072711612903279021190125573901241905382\
33223252822171325272323252526242212231526255222162529341625292\
34714272323241213252344142113241323222411142354211114262411133\
22427292324282822433828221225172922123416290122133225290221243\
124290211272123283128112427222631252756222621848290909039090906
...has 311 digits... ugh.
Alas, my hope of countering the last few digits becomes diminished as the whitespace in the image is too spacious; thanks to the messy distribution of random numbers, it now seems unreasonable to believe that the key(s) which would improve upon this image will feasibly be found. All the work has gone against my argument more than it has helped it. Oh, well.  Besides, the image can be represented in 256 hexadecimal digits anyway – it appears that random numbers in general just will never come out on top.
[EDIT]
Well, I guess something like an asterisk in place of each nine-comma-zero and a new conditional statement in the decoder would help quite a bit, at least in the midst of horizontal black lines everywhere.
Last edited by Guest on 05 Jul 2010 08:21:58 am; edited 1 time in total |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 30 Jul 2009 09:59:08 am Post subject: |
|
|
Here is another random number algorithm: the one used on the TI-89 series for randNorm() (the TI-83 algorithm doesn't work there since the calculator wouldn't know how to compute invNorm().
Code:
:randNorm(x,d)
:Func
:Local u,v,s
:Loop
: 2*rand()-1→u
: 2*rand()-1→v
: u*u+v*v→s
: If 0<s and s<1
: Return x+d*v*√(-2*ln(s)/s)
:EndLoop
:EndFunc
Last edited by Guest on 05 Jul 2010 08:19:52 am; edited 1 time in total |
|
| Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009
Posts: 555
|
| Posted: 30 Jul 2009 10:47:00 am Post subject: |
|
|
That's pretty cool! (So is the whole topic!)
My necropost:
DarkerLine wrote: Here's a cute little result: if you seed rand with 196164532 then get a random number from rand, it will return 1. Sweet!
This is only true to an extent, because the calculator rounds when it shows this on the homescreen.
From TIBD: http://tibasicdev.wikidot.com/rand
Quote: Note: Due to specifics of the random number generating algorithm, the smallest number possible to generate is slightly greater than 0. The largest number possible is actually 1, but since returning a result of 1 would mess up the output of randBin( and randNorm(, the actual value returned in such cases is 1-1.11e-12 (which is displayed as 1, and is "equal" to 1 for the purposes of the = command). To see 1, store 196164532 to rand and then run the random number generator.
You can check this with a method I saw used by Darkerline.
Do this from the homescreen:
1. 196164532->rand
2. rand->A
3. Go to the Solver ([Math] [0])
4. For the equation put the letter A
5. Press down
6. Now you can see all the decimals the calc can hold
1-1.11e-12=.99999999999889
It's pseudo-one |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 30 Jul 2009 11:51:56 am Post subject: |
|
|
...you are aware that you are replying to me by quoting a paragraph written by me, and suggesting a method you saw used by me, right?
Last edited by Guest on 30 Jul 2009 11:52:22 am; edited 1 time in total |
|
| Back to top |
|
|
ztrumpet
Active Member
Joined: 06 May 2009
Posts: 555
|
| Posted: 30 Jul 2009 11:54:27 am Post subject: |
|
|
Yes, using stuff I read on your blog, quoting stuff from the site you're master admin of...
Last edited by Guest on 30 Jul 2009 12:28:39 pm; edited 1 time in total |
|
| Back to top |
|
|
|
TI-Basic => TI-BASIC
