我有一个可行的算法,可以确定分数是否无限循环,并确定哪些数字是重复的:
std::vector<integer_type> rd, dg;
integer_type d ( m_numer ), r;
do {
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() ) );
注意:
rd
包含余数数字dg
包含十进制结果数字_remquo
整除第一个和第二个操作数,并将余数存储在第三个参数中,忽略模板参数base
可以视为十进制值10
m_numer
是一个分数的分子m_denom
是一个分数的分母
问题:
我想要摆脱至少std::find ( rd.rbegin() + 1, rd.rend(), r ) != rd.rend() )
,也就是说,我想要检测是否之前出现过一次余数,并且最好(为了同时摆脱rd
向量),返回自右向左的最后一位重复数字到第一个重复数字的距离。
问题是,我想要分析具有巨大的重复数字序列的数字,例如1083448249/12172166
,并且要在合理的时间内完成(不需要花费时间去反向搜索余数向量)。
有人有什么想法吗?
13/30
=> 0.4(3) - Heiko Schäfer1/N
的情况。对于这种情况,请参阅此链接:http://mathforum.org/library/drmath/view/51549.html(可推广到任何基数)。 - freakish