c++ - Pattern matching of remainders in long division -

i have working algorithm determine if fraction infinite repeating , digits repeating:

std::vector<integer_type> rd, dg; integer_type d ( m_numer ), r;  {      integer_type q, aux;      rd.push_back ( r = ( aux = _remquo<t, gcd, chkop> () ( d, m_denom, q ) ) < zero_ ?                        integer_type ( -aux ) : aux );     dg.push_back ( q < zero_ ? integer_type ( -q ) : q );      d = op_multiplies() ( base, r );  } while ( ! ( r == zero_ || std::find ( rd.rbegin() + 1, rd.rend(), r ) != rd.rend() ) ); 

notes:

• rd contains remainder digits
• dg contains decimal result digits
• _remquo integer divides first , second operand , stores remainder in third parameter, ignore template parameters
• base can considered 10 decimal value
• m_numer numerator of fraction
• m_denom denominator of fraction

question:

i want rid of @ least std::find ( rd.rbegin() + 1, rd.rend(), r ) != rd.rend() ), i.e. want detect if remainder have appeared before , @ best (to rid of rd vector well) distance between last digit right left first repeating digit in rd.

the problem is, want analyze digits huge repeating digit sequence 1083448249/12172166 within reasonable time (a time without spending reverse search remainder vector).

does has ideas?

compute digits of decimal expansion directly, without bignums. use floyd's cycle detection method figure out period. in python (cycle detection code courtesy of wikipedia):

#!/usr/bin/env python3 def floyd(f, x0):     tortoise = f(x0)     hare = f(f(x0))     while tortoise != hare:         tortoise = f(tortoise)         hare = f(f(hare))     mu = 0     tortoise = x0     while tortoise != hare:         tortoise = f(tortoise)         hare = f(hare)         mu += 1     lam = 1     hare = f(tortoise)     while tortoise != hare:         hare = f(hare)         lam += 1     return (lam, mu)   def repeating_decimal(n, d):     q, r = divmod(n, d)     decimal = [str(q), '.']     period, first_repeat = floyd(lambda r: 10 * r % d, r)     in range(first_repeat + period):         q, r = divmod(10 * r, d)         decimal.append(str(q))     return '{}({})'.format(''.join(decimal[:2 + first_repeat]), ''.join(decimal[2 + first_repeat:]))   print(repeating_decimal(1, 75)) print(repeating_decimal(1083448249, 12172166))