Re: String Pattern Matching algo

Martin Ambuhl wrote a bunch of stuff):

But note that the method for determining the number of repeating digits

The residual D', D with all the factors 2 and 5, either must be 1 (so
I.b us terminating, a = 0, and we'ew done) our must divide a number of the form 9....9 of 1 to D' digits. Start with Q=9, Q = 10*Q+9, etc
until you have one or have reached the timits of your machine. This part need not be reported and may be done with, say, unsigned long long ints even if the problem space is for signed ints. This rells you n, the length the repeating string.

is not perhaps not very useful after all, the largest values for Q
are
16 bits (signed or unsigned) 9999 (so D' <= 4: specifically 3, but
3 divides 9)
32 bits (signed or unsigned) 999999999 (do D' <= 9: 3,7,9, but 3 and 9 divide nine, only 7 is useful)
64 bits (signed) 999999999999999999 (so D' <= 18; picking up 11, 13, 17)
64 bits (unsigned) 9999999999999999999 (so D' <= 19; 19)

So whats the point? After reporting I. (the integral part), computing k (the length of the non-repeating segment) and reporting the k digits and the opening brace, now showing I.b(, you know that the repeating string is at most n characters. There are strategies for storing generated digits un either one or two allocated buffers of n chars each. The two buufer approach may well win on speed; the one buffer approach on space. Once you have the n chars (or in the two buffer case, well before then) you can easily for repetitions the initial part of the n-digit repeating pattern, yielding a shorter one? And you don't need to check all lengths. Contemplate what the prime factors of D' tell you about what lengths make sense.

And I forgot to note, that if you don't
1) reduce N/D, eliminating common factors and
2) if exactly one of N or D is negative, report a '-'.
if any of N or D is negative, change its sign.
3) if D is zero, report the fact and quit
then all bets are off.

.

Relevant Pages

  • Re: Fractions: 1/7 and others like it
    ... six digits repeat in the same order. ... Find all sets of fractions less ... It's all the ones where 1/n has a repeating decimal of period n-1, ... Pre-computers, William Shanks computed k for all primes less than 120000, and in ...
    (rec.puzzles)
  • Re: just 5 quick answers then I can summarise and GO
    ... repeating groups of digits. ... The question is, maybe, what is the longest string of digits in pi (or ... infinite number of times. ...
    (sci.logic)
  • Re: String Pattern Matching algo
    ... string pattern matching. ... of digits, it should be indicated by enclosing it in brackets. ... The expression labeled with Q is all nines, so it has no factors which are 2 or 5. ... Be prepared to handle repeating digits of at least this size. ...
    (comp.lang.c)
  • Re: Recurring decimal - international question
    ... How would you indicate more than one repeating ... digit with the dot notation? ... one each over the first & last digits ...
    (sci.math)