Approximating randoms

E1bddb31000e459fb3ee5593fe067486
0
paul0n0n 101 Aug 25, 2009 at 17:53

How would that be done?
first off this is just a hobby exercise. but say you have an infinite series of random numbers i.e. “0.42014928858192.. etcetera”.

Here is an example of my first shot at doing such a thing.

were n = 1 and d = 1 , and a = the random number
iterating {
n/d = c
if c < a then n = n + 1
if c > a then d = d + 1
}
this approximates the number perfectly, but is very slow.

I output n and d to a file every iteration, then plot them, to which i find a very nice little pattern, that seems to have a very particular angle. I get the angle by averaging n and d which seems to work out pretty well up until the point n and d stop, then the angle goes off course.

Now I remember hearing that 6 or 7 digits of pi was enough to calculate the circumference of the known universe to within the accuracy of an atom (don’t quote me on this). so then if i have an angle that is accurate to say 20 decimals then how does the angle go off course so quickly. And is there any way to correct it?

6 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Aug 25, 2009 at 18:18

So, you want to find a rational number approximation for a given positive real number?

I’m not sure what you mean by saying that “the angle goes off course”. Clearly the n vs. d curve should converge to a slope n/d equal to the number being approximated. Can you post an image of the graph to help explain?
@paul0n0n

Now I remember hearing that 6 or 7 digits of pi was enough to calculate the circumference of the known universe to within the accuracy of an atom

Actually, no…an atom is about 10\^-11 meters across, while the observable universe is about 10\^27 meters across. So you’d need something like 38 digits of pi to calculate the circumference that accurately. :) However, when doing single-precision arithmetic on a computer, only about 6 or 7 decimal digits can be stored; with double-precision, 15 or 16 digits. To work with longer numbers you need a special arbitrary-precision arithmetic library.

E1bddb31000e459fb3ee5593fe067486
0
paul0n0n 101 Aug 25, 2009 at 21:08

@Reedbeta

So, you want to find a rational number approximation for a given positive real number?

well kind of…It’s more to find an irrational number. or numbers that just don’t exist yet. Not saying that it can be done, I’m just trying it out.
@Reedbeta

Can you post an image of the graph to help explain?

http://c3.ac-images.myspacecdn.com/images02/43/l_f987e0e9b6e84375ad7f5c299df57efa.jpg
The dotted line in the picture is the plotting of a and b, were a is the x-axis and b is the y-axis.

I came up with a way to approximate the random number faster then adding 1 to either a or b, by multiplying both a and b by 10 if the product of a/b has a closer approximation then it had before. The plot doesn’t multiply by 10 but instead adds 10 to x and y so that they don’t go over there bit limit. the same angle is achieved.

The random number I used is: 0.811319243339041120212239080712172745200117254351360228364246460925262842220
and after about five minutes I ended up with:
a=95502539202421521611352142300221720
b=117712651322522732822462253411322830

Which is accurate to 35 decimals: 0.81131924333904112021223908071217274
@Reedbeta

I’m not sure what you mean by saying that “the angle goes off course”. Clearly the n vs. d curve should converge to a slope n/d equal to the number being approximated.

When trying to use the angle to predict the rest of the random number though it will be accurate up to a and b, and cannot be used to even get a couple extra decimals, which i could then use to make a and b more accurate, recalculate the angle to a higher precision and repeat the steps to have a way to predict the rest of the random sequence. i have a few idea’s why the angle cannot achieve even one extra decimal but nothing that is well defined.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Aug 25, 2009 at 21:19

Wait, so you’re trying to predict the rest of the number by looking only at the first n digits? I don’t think that’s going to work very well as there are infinitely many rationals that give the same first n digits. As a trivial example if you had the first three digits 0.811, one possible rational approximation would be 811/1000, but this would predict 0 for all following digits. The only way I can see this working is if you know how the RNG works internally, you may be able to deduce part of its internal state from the beginning of the sequence, which would then let you predict the rest of the sequence. I don’t know much about the subject but you could do some reading about cryptography if you’re interested.

E1bddb31000e459fb3ee5593fe067486
0
paul0n0n 101 Aug 25, 2009 at 21:31

That is what the Angle is for. if say, just for arguments sake, the angle = sin(30), you could then use that number with a and b to achieve a little bit farther approximation to the number. well at least that is what my idea was, I mean it does a really good job of it, but it’s never overly right.

but obviously it would be best if this idea never could work.
@Reedbeta

The only way I can see this working is if you know how the RNG works internally, you may be able to deduce part of its internal state from the beginning of the sequence, which would then let you predict the rest of the sequence.

There is no internal working for the random number above, it wasn’t generated by a computer at least.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Aug 25, 2009 at 21:41

The angle is just the arctangent of the number you’re trying to predict. If the number you’re trying to predict is a random sequence, the arctangent is another random sequence. I don’t think it’s any easier to predict the arctangent than the original random sequence.

Put another way, you don’t get more information by converting it from rational format to an angle. For instance if you know the first three digits are 0.811, then the slope is between 0.811 and 0.812, and so the angle is between atan(0.811) and atan(0.812). You still have a range of possible angles based on what you know, but no way to predict which angle within that range is the right one.

E1bddb31000e459fb3ee5593fe067486
0
paul0n0n 101 Aug 26, 2009 at 00:32

That was perfect. Thank you, don’t need to waist my time on it.