| Author |
Message |
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
 Posted: 14 Jun 2007 11:00:53 pm Post subject: |
|
|
Groene07 wrote: hmmm. I guess all I understand is psuedorandom (Kind of) what I got to thinking was There is no such thing as a random number PERIOD!!!! My basis is that lets say you were going to pick a number out of a hat....You are technically confined to the numbers in a hat and technically there was nothing random about that number because you deliberatly put your hand on to of THAT number. Same goes for if you spin a wheel of numbers its just not random. If someone knows of a true random number generator, or a way to come to a completly random number tell me, but I just don't think it's possible.
Yah!!! teh hundreth posterz!!!!   :biggrin: :
[post="108228"]<{POST_SNAPBACK}>[/post]
You may be wondering what's "as far as I'm concerned" doing here - it's because probability depends on the amount of information a person has, and therefore varies from person to person. If you threw a coin and asked me about the probabilities, I'd say it's 1/2 for heads and 1/2 for tails. That's not true for you - you already saw it come up, say, heads, and so for you the probability that it's tails is 0. But it's 1/2 and 1/2 for me since I have no information. |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 21 Jun 2007 07:05:35 am Post subject: |
|
|
(N.B. I'm formally on a break, but I have a spot of a reprieve, so I'm taking the opportunity...)
As an additional bit of info, normally-distributed random numbers can also be generated by what is called the Box-Muller Transformation. I think the reason why the calculator gives results different from invNorm(rand) is that it uses this method, it being cheaper in terms of operations needed.
If one wants random numbers with distribution function p(x), the method for generating them is to apply the inverse of the corresponding CDF to rand.
thornahawk |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 21 Jun 2007 10:29:46 am Post subject: |
|
|
thornahawk wrote: (N.B. I'm formally on a break, but I have a spot of a reprieve, so I'm taking the opportunity...)
As an additional bit of info, normally-distributed random numbers can also be generated by what is called the Box-Muller Transformation. I think the reason why the calculator gives results different from invNorm(rand) is that it uses this method, it being cheaper in terms of operations needed.
1. It only generates one random number, and not two, when it calculates randNorm(. We know this because the code 0->rand:randNorm(0,1:rand has the same output as 0->rand:rand:rand.
2. The result is exactly opposite of invNorm(rand, which would be very surprising from a completely unrelated method.
Quote: If one wants random numbers with distribution function p(x), the method for generating them is to apply the inverse of the corresponding CDF to rand.
thornahawk
[post="109027"]<{POST_SNAPBACK}>[/post] Unfortunately, the normal CDF is the only one which the calculator can find an inverse for. You could use the solve( command for some of the rest, but I've found it does not work at all for tcdf(, and haven't tried it for any of the others. You could invert geometcdf( quite easily by hand, however, to get the formula int(1+ln(1-rand)/ln(1-p or just int(1+ln(rand)/ln(1-p; I'm not sure about the others.
By the way, I've noticed you looked at some of the statistics pages I wrote for TIBD. How were they? I know I'm not a statistics expert (far from it, I've only taken one real statistics course, and that was this year). Also, this was my first attempt at LaTeX.
Last edited by Guest on 30 Aug 2010 08:17:08 pm; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 22 Jun 2007 04:51:40 am Post subject: |
|
|
The idea with Box-Muller is that you output one and save the other one for later, then generate two normal deviates again when the reserve one gets used. On the other hand, I do not have my calc handy, so all I have said before remains conjectural.
Quote: ...You could use the solve( command for some of the rest, but I've found it does not work at all for tcdf(, and haven't tried it for any of the others. You could invert geometcdf( quite easily by hand, however, to get the formula int(1+ln(1-rand)/ln(1-p or just int(1+ln(rand)/ln(1-p; I'm not sure about the others.
That is true; TI neglected to provide inverses for the other distributions. With the case of tcdf(, though, I have encountered somewhere that one can use the output of invNorm( as a starting point for solve( for inverting tcdf( ; I do not have my references handy at the moment to verify this, however. :(
Quote: ...I've noticed you looked at some of the statistics pages I wrote for TIBD. How were they? I know I'm not a statistics expert (far from it, I've only taken one real statistics course, and that was this year). Also, this was my first attempt at LaTeX.
I've PM'd you. ;)
(* back to *real* work *)
thornahawk |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 22 Jun 2007 09:05:23 am Post subject: |
|
|
thornahawk wrote: That is true; TI neglected to provide inverses for the other distributions. With the case of tcdf(, though, I have encountered somewhere that one can use the output of invNorm( as a starting point for solve( for inverting tcdf( ; I do not have my references handy at the moment to verify this, however. 
[post="109132"]<{POST_SNAPBACK}>[/post]
Anyway, the running time for p=.975 and df=5 is about 15 run indicator bars, which is 23 seconds on my 83+. Using fMin( to solve the same equation gave a slightly-inaccurate answer (accurate to 8 or 10 decimal places) within 12 run indicator bars, and since fMin( actually has a tolerance parameter, you could get a lower-accuracy answer faster.
Last edited by Guest on 22 Jun 2007 09:08:29 am; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 24 Jun 2007 07:03:39 am Post subject: |
|
|
For those who wish to delve deeper into techniques for "complicated" random numbers:
Non-Uniform Random Variate Generation
(and while you're at it, his rant's worth reading, too.  )
thornahawk |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 29 Aug 2007 11:27:12 pm Post subject: |
|
|
wow, excellent work, I don't know how I missed this.
Very helpful information  |
|
| Back to top |
|
|
DarkerLine
ceci n'est pas une |
Super Elite (Last Title)
Joined: 04 Nov 2003
Posts: 8328
|
| Posted: 09 Sep 2007 03:38:12 pm Post subject: |
|
|
Should anyone be curious, I added the details for randM( as well - I initially forgot about that one because it was in a different menu.
Last edited by Guest on 30 Aug 2010 08:18:37 pm; edited 1 time in total |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 22 Oct 2007 04:28:12 am Post subject: |
|
|
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
Last edited by Guest on 22 Oct 2007 04:30:00 am; edited 1 time in total |
|
| Back to top |
|
|
Cryzz
Newbie
Joined: 16 Oct 2007
Posts: 29
|
| Posted: 24 Oct 2007 04:43:48 pm Post subject: |
|
|
Sorry to necropost but this really hurts my eye:
[quote name='"darkerline"']randInt(A,B
- when A<B, A+int((B-A+1)rand
- when A>B, B+int((A-B+1)rand
[/quote]Simply A+(B-A)rand will do the trick (eventually enclosed with int()!
Edit: ah you want the bounds inclusive? then what Luby said is correct but it doesn't matter what the high or the low bounds are
Last edited by Guest on 24 Oct 2007 04:44:14 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: 24 Oct 2007 05:17:08 pm Post subject: |
|
|
The other problem with an optimization like yours is that it changes an addition into a subtraction when A>B. This still gives a right answer in the sense that it's uniformly distributed in the right range, but it wouldn't have agreed with randInt( even if the latter didn't use inclusive bounds. When using randInt(, a small output of rand means that the result is close to min(A,B), and I want to reflect that behavior; in your optimization, a small output of rand means that the result is close to A, even if A>B.
Last edited by Guest on 24 Oct 2007 05:17:19 pm; edited 1 time in total |
|
| Back to top |
|
|
Cryzz
Newbie
Joined: 16 Oct 2007
Posts: 29
|
| Posted: 24 Oct 2007 06:08:49 pm Post subject: |
|
|
| Ah ok, if you see it that way... |
|
| Back to top |
|
|
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 |
|
|
|
TI-Basic => TI-BASIC
