Re: String Pattern Matching algo
- From: Martin Ambuhl <mambuhl@xxxxxxxxxxxxx>
- Date: Sun, 30 Apr 2006 00:42:50 GMT
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.
.
- References:
- String Pattern Matching algo
- From: 116Rohan@xxxxxxxxx
- Re: String Pattern Matching algo
- From: Martin Ambuhl
- String Pattern Matching algo
- Prev by Date: Re: String Pattern Matching algo
- Next by Date: Re: Trying to read hardware memory from pointer?
- Previous by thread: Re: String Pattern Matching algo
- Next by thread: Re: String Pattern Matching algo
- Index(es):
Relevant Pages
|
Loading