This probably belongs in a Math conference, but joining Math put me in
a conference with items about religion and philosophy. So, here goes:

    Most of us know about repeating decimal fractions, which come about
because there is no way to express with a finite number of decimal places even
most rational numbers. We can generally break down the fractional portion of
a rational number into the non-repeating and the repeating portions.

    For instance, 1/2 is 0.5, which has a single digit in the non-repeating
part, while 1/3 is 0.3333333, whose repeating protion can be considered to
be a single digit (written 0.3 with a bar drawn over the 3) since this is all
that's necessary to convey how to generate all the other digits in the
infinite string of 3s. 1/7 is 0.142857(bar), a _six_ digit string repeated
ad nausium, while 1/9 and 1/11 have repeating parts of only one and two digits
respectively. 1/30, or 0.0333333... by my definition has both its
non-repeating and it repeating strings equal to a single digit in length.

    Now for my inquiry: I need a good means of determining the lengths of the
nonrepeating and the repeating parts of a decimal fraction, given fairly large
numbers in the numerator and especially the denominator. For instance, how
many digits will be required to write the exact decimal representation of
672355/1205647, and how many of these digits will have the bar drawn over
them?

    As it is for a potential programming project, I'd like a method or rule
that can be applied in base 2, 16, or 256 as well as base 10.

21 responses total.

I believe they gave us a way of doing this when I was in Calculus, but I don't
remember what it was.  I'll go and see if I've still got the notes.

The maximum length of the repeating digit string is one less than the 
denominator.  If you're dealing with arbitrary large denominators,
this is a pretty wasteful way to store numbers in a computer. 

Re #2:
    That is the maximum length. But I need the *actual* length to see if
the denominator is suitable for a special purpose. I need to be assured
of a large repeating string.

    This is not for the storage of large, or high precision numbers in and
of itself. What I intend to use this for is to generate random-looking sets
of numbers which have a fairly large period; and this looks like a promising
method *if* I can filter out repeating digit strings of insufficient length.

Okay.  There's a number of special cases, fruitful mines, etc., but i don't
know of any general way to determine the length of the repeat string that's
meaningfully faster than calculate-it-and-count-the-the-length.

The length is determined by the the divisibility of a string of ones by
the denominator; the smallest such string determines the repeat length.
For instance, 1/7 repeats in 6 digits because the smallest string of 1's
which is divisible by 7 is 111111 ( = 7 * 15873).

I don't think there's an easy way of calculating the repeating length
aside from doing prime factorizations of the various strings.

Why not use one of the many simple pseudo-random number generating
schemes whose repeat lengths have been evaluated? 

The ones I've seen require pre-calculation of a couple of terms in the series
before results can be used. At any rate they turned out to be unsuitable for
this particular purpose.

Actually, this generator need not have *that* large a period in number of
terms generated from a seed. However, the first terms of sequences generated
from different seeds have to appear random and have a large "period" across
initial seed values.

The purpose is to store a "universe" of several billion locations, each of
which may be empty or else contain various objects, without having to actually
allocate a few hundred gigs of space, by storing it in the form of a
mathematical procedure. Thus I actually *want* deterministic, predictable
behavior. A seed number X,Y must produce the same set of numbers every time
it's used. However, the "period" of the sequences across the X,Y range must
be larger than the size of the grid, or else (as I've found experimentally)
the map looks crappy.

The divide into a string of 1's plan looks implimentable, if a bit of a
kludge. Can it work in other bases?

You figure out what the prime factorization of a string of 1's is in
the other bases and you go from there.

Pseudo-random number generators have the properties you seek in #7.

Actually it's a string of 9's. 1's is not correct, because 1 mod 3 == 1, 11
mod 3 == 2, and 111 mod 3 == 0, indicating that 1/3 repeats in three digits
when in fact it repeats in *one* digit. The string of 9's rule checks out for
the few examples that I've tried.

Rane's right; a pseudo-random number generator, properly applied, should do
exactly what you need.  If you seed it with the same number each time, the
results are repeatable; that's why it's called "pseudo-random."

r
Okay, I'm getting acceptable results from my tests, and I'll accept that I
might get acceptable results from "a pseudo-random number generator, properly
applied" run the same way. However, both are about an order of magnitude or
two too slow.

What I'm doing now is generating the first 65535 terms of the "series" whether
I need them or not, and storing them in an array, for each separate X-value
being plotted. For each Y location I take as my "random" result the
(Y+32767)th term/digit (Y ranges from -32767 to +32767) of the array.

What I need instead is a way, either with the repeating decimal *or* with a
standard random number series, to calculate the nth term *without* having to
canculate the other n-1 terms. Or else a way to sufficiently scramble seeds
so that the first term in the series bears no *apparent* relationship to the
raw seed value supplied.

A pseudo-random number generator usually requires an operation on only two
of them to generate the next, and perhaps a short list from which to
choose those two. Two successive generated values would be the (almost)
independent X and Y values. So, at most, four additions might be necessary
to generate the pair. (I haven't run the generator I am thinking of
for some time and would have to look up the details and the resulting
repeat interval. What repeat interval do you need (more than), and how
many significant figures do you need, again?

The grid is 65535 by 65535 or less, so I guess a period of 2^32 should
suffice if you count the entire map. For each row, by itself, a period
of 2^16 for that row's sequence may be sufficient, provided that that sequence
is unique among 2^16 other rows.

Could you expand a little bit on the objectives. I understand that you
want to choose locations in that large grid. Will different entities
be allocated to grid points? How many of the 65535^2 grid points do
you want to choose in the generation of (xx,y)?

This is a 2-D star map for a computer game. I want it to have "BILLions and
BILLions of stars" without actually having to allocate entire multi-gigabyte
hard drives to store the data. A grid point may be empty (usual case) or else
contain a collection of objects (star(s), planets, moons, etc.) which are also
to be generated based on the grid location co-ordinates. I find that between
2 and 4 stars per 256 grid points seems to have the best appearance.

And you want to just choose the 256 grid points randomly, and something
else will populate them? 

Something like that. More like 4 billion grid points, perhaps a bit less for
slack, with between a one-hundered-twenty-eighth and a sixty-fourth of them
populated and the rest empty.

Here is a way to generate pairs of random numbers with the desired
property. The random number generator I will describe uses only
addition. Let

    X(n)  =  (X(n-p) + X(n-k)) mod m, n > k

    where m = 1000000000000 *octal*

For example, of p = 24 and k = 55, the period of X(n) is greater
than 2^55. 

The two random numbers are the first and last 6 digits in X(n).

For example, 777777 777777 corresponds to the decimal pair [65535, 65535].

It is necessary to first produce the seed consisting of k=55 (say) 12
digit octal numbers, which can be done with any random number generator. 
From then on, the generation is very fast and of course repeatable. 

Is this useful?

Possibly.

I'm having promising results with a random number generator that I got out
of a manual for my TI58C, which goes

        x[n+1] = (a x[n] + c) mod m

where x[0] is the seed, a = 24298, c = 99991, and m = 199017.

I've modified the form to

        x[n] = (a^n x[0] + c (a^(n-1) + a^(n-2) + ... + A^2 + A + 1)) % m

and I'm pre-generating all the a^i terms and sum c a^i terms and putting
them effectively into two 65534 * 24 bit integer arrays. Then when displaying
a portion of the map, I generate the "random" number by using the X location
on the map as x[0] and the Y location as n, and compute the n'th term by

        r = (a_power[n] * X + ca_sum[n]) % modulus.

The results were further improved by reversing the bit-order of X before
feeding it to this get_loc_rand function.

Of course, this necessitates generating all 65534 sets of terms and storing
them for the duration of the program, which sucks up a large portion of the
lower 640K. It's better, I suppose, than the memory requirements for 4 billion
grid points - or even that fraction of them that are populated.

Your addition-only (plus mod) method would save a multiply, and along with
it some time; but it seems it would still require pre-generating and storing
a similar amount of data. (I could be wrong, I haven't looked at it closely
yet.)

No, you just store the initial 55 seeds. Then each iteration generates
a new, pseudo-random, location. Of course, you need 12 digit octal
processing. If you want to work with just 6 figures, you need to generate
two PRNs in a row. 

Response not possible - You must register and login before posting.

- Backtalk version 1.3.30 - Copyright 1996-2006, Jan Wolter and Steve Weiss