Simulation of irrational numbers
40 次查看（过去 30 天）
I am trying to generate two random numbers and such that their ratio is an irrational number. I understand that all numbers stored on a computer are rational, so one cannot have a truly irrational number in a simulation/experiment. So, is there any way of simulating the situation where the ratio of the two numbers has a very long repeat period?
John D'Errico 2019-6-1
编辑：John D'Errico 2019-6-1
Perhaps now I am starting to understand what your question comes down to.
The ratio of x1 and x2, if they are doubles, will never have a period longer than 16 digits, because that fraction, as a double precision number, only has roughly 16 significant digits. There simply are not more than 16 digits to which you can attribute any meaning in a double. Worse, as I point out in my initial comment to your question, ALL double precisionn numbers are rational, and non-repeating decimals.
If they are fully general integers, then the ratio of two integers can in theory have as long a period to repeat as you wish. You will just need to pick two numbers (mainly you need to pick the divisor) such that it has a long period. But that is not something that is easily controlled. In general, the numerator of a rational fraction does not contribute to the period of the decimal form, although it may reduce the period. The numerator (n) of a fraction n/d cannot increase the period beyond that of 1/d, however, it may yield a shorter period.
For example, the number 1/7 has an infinitely repeating period of length 6. However, the number 7/7 is an integer, so it has only repeating zeros after the decimal point. Or, the number 1/21 is a repeating decimal with period 6 (the "047619" repeats) but 7/21 repeats with period 1, since it reduces to 1/3.
So, what controls the period of a fraction? A quick link that suggests the solution is:
The problem is that you don't get a truly simple formula to use. But in general, consider the fraction 1/d. If you want the longest potential period, then you need to consider prime numbers for d. Why? Because the period is a function of the totient function of d. Euler's Totient function (I offer a totient calculator in my vpi toolbox. But the totient is easy to compute as long as you know the prime factorization of your number.)
It is usually written using the name phi. phi(d) is the number of integers m less than d, such that gcd(d,m)==1. Clearly the totient of a prime number is 1 less than the number itself. We can see how it works, by some examples:
The length of the repeating portion of a rational fraction n/d will be a factor of phi(d). So we can see that the MAXIMUM length of the period of a repeating fraction is d-1, since the largest possible value for the totient function of a number is 1 less than that number.
Consider 1/7. It has a period of 6. And phi(7)=6. And 6 is a factor of 6. So it works.
How about 1/13? It also has a period of 6. And phi(13)=12. 6 is clearly a factor of 12.
So not all prime numbers have maximum length periods, because the requirement is merely that the period length be a FACTOR of totient(d). And it is not that easy to predict the period length either. Here is a good one, for a moderately small denominator.
Of ourse, phi(61) is 60, since 61 is a prime. And 1/61 has a repeating period of 60, with this repeating fragment:
Is there an easy way to identify that fact? The trick can be to use a powermod utility. Lets see, the factors of 60 are given by my aliquotparts function:
1 2 3 4 5 6 10 12 15 20 30
The period (p) of 1/61 is then the SMALLEST power of 10, such that mod(10^p,61) == 1. So now, we test each power of 10.
p = aliquotparts(60)
1 2 3 4 5 6 10 12 15 20 30
for p_i = p
And of course, we have:
So the smallest power of 10 such that (10^p_i-1) is divisible by 61 is in fact 60. Therefore the period of 1/61 has repeating part of length 60. In fact, we don't need to actually test 60 there, because it is provably true. That is, Fermat's theorem (sometimes called Fermat's Little Theorem)
tells us that for ANY prime p, if p does not dive a, then this relation always holds fpr prime p, and integer a > 1:
mod(a^(p-1) , p) == 1
So as long as p is not 2 or 5, then we know that
powermod(10,p-1,p) == 1
must hold true. The conclusion is that any prime that is not 2 or 5 will have a perion of at most p-1, when the fraction is represented in decimal digits.
So, do you want a fraction with a HUGE repeating period? Pick a large prime denominator. Then run a quick test.
d = nextprime(1e8)
p = aliquotparts(totient(d))
1 2 491 982 101833 203666 50000003
for p_i = p
If any of those intermediate results had been 1, then the period would be less than the maximum possible. For example, I claimed before that the period of 1/13 is 6? We can predict that would be true by this simple computation:
And that is the smallest power of 10 that leaves a residue of 1 modulo 13, among the divisors of 12.
Anyway, the period of fractions of the form n/100000007 have period length 100000006. That is, just over 100 million decimal digits before it starts to repeat. Here are the first 200 digits of that number:
Why does the above test work? Not hard to prove, actually. It is actually more interesting to prove that for prime divisor d, the maximum value of the period is d-1. For this, a quick look at a theorem that goes back as far as Fermat will suffice.
One of the very pretty things (at least to me) is that this question, about something as prosaic as decimal fractions, actually uses some interesting results from number theory to solve.
What use this is to you? Your problem, not mine. ;-)