如何知道小数中的重复小数？
我已经知道一个分数是什么时候重复小数。 这是功能。
public bool IsRepeatingDecimal
{
get
{
if (Numerator % Denominator == 0)
return false;
var primes = MathAlgorithms.Primes(Denominator);
foreach (int n in primes)
{
if (n != 2 && n != 5)
return true;
}
return false;
}
}
现在，我试图获得重复的数字。 我正在检查这个网站：http://en.wikipedia.org/wiki/Repeating_decimal
public decimal RepeatingDecimal()
{
if (!IsRepeatingDecimal) throw new InvalidOperationException("The fraction is not producing repeating decimals");
int digitsToTake;
switch (Denominator)
{
case 3:
case 9: digitsToTake = 1; break;
case 11: digitsToTake = 2; break;
case 13: digitsToTake = 6; break;
default: digitsToTake = Denominator - 1; break;
}
return MathExtensions.TruncateAt((decimal)Numerator / Denominator, digitsToTake);
}
但我真的意识到，有些数字有一个十进制小数有限，后来是无限的。 例如：1/28
你知道更好的方法来做到这一点吗？ 还是算法？
一个非常简单的算法是：实现长期分工。 记录你所做的每一个中间部门。 只要你看到一个与你之前完成的部门相同的部门，你就有重复的事情。
例如：7/13。
1. 13 goes into 7 0 times with remainder 7; bring down a 0.
2. 13 goes into 70 5 times with remainder 5; bring down a 0.
3. 13 goes into 50 3 times with remainder 11; bring down a 0.
4. 13 goes into 110 8 times with remainder 6; bring down a 0.
5. 13 goes into 60 4 times with remainder 8; bring down a 0.
6. 13 goes into 80 6 times with remainder 2; bring down a 0.
7. 13 goes into 20 1 time with remainder 7; bring down a 0.
8. We have already seen 13/70 on line 2; so lines 2-7 have the repeating part
该算法给我们538461作为重复部分。 我的计算器说7/13是0.538461538。 看起来很对我！ 剩下的只是实现细节，或者找到更好的算法！
如果分数numerator / denominator分数（正数）减小，则当且仅当denominator没有2或5以外的素数因子时，分数的小数点扩充才会终止。如果有任何其他素数因子，则小数点扩展将是周期性的。 但是，分母可以被2和5中的至少一个整除并且不会引起略微不同的行为的情况。 我们有三种情况：
denominator = 2^a * 5^b ，则小数点后的小数点扩展终止max {a, b}位数。 denominator = 2^a * 5^b * m其中m > 1不能被2或5整除，则小数展开的小数部分由两部分组成，即长度为max {a, b}的前期和该期限的长度由m决定，与分子无关。 denominator > 1不能被2或5整除，那么十进制扩展就是纯粹的周期性的，这意味着该周期在小数点后立即开始。 案例1和2的处理有一个共同的部分，那么令c = max {a, b}
numerator / denominator = (numerator * 2^(c-a) * 5^(c-b)) / (10^c * m)
其中对于情况1， m = 1 1。注意，我们乘以分子的因子2^(ca)和5^(cb)是1.然后，通过扩展
(numerator * 2^(c-a) * 5^(c-b)) / m
并将小数点c位移到左边。 在第一种情况下（ m = 1 ）该部分是微不足道的。
案例2和3的处理也有一个共同部分，即一部分的计算
n / m
其中n和m没有共同的素因子（并且m > 1 ）。 我们可以写出n = q*m + r其中0 <= r < m （除数为余数， r = n % m ），q是分数的整数部分，而不是感兴趣的。
由于分数被假设为减少，因此我们有r > 0 ，所以我们想要找到分数r / m的扩大，其中0 < r < m并且m不能被2或5整除。如上所述，这样的扩张是纯粹的周期性的，所以寻找期限意味着找到完整的扩张。
让我们开始寻找启发式的时期。 所以设k是（最短）期的长度， p = d_1d1_2...d_k期。 所以
r / m = 0.d_1d_2...d_kd_1d_2...d_kd_1...
= (d_1d_2...d_k)/(10^k) + (d_1d_2...d_k)/(10^(2k)) + (d_1d_2...d_k)/(10^(3k)) + ...
= p/(10^k) * (1 + 1/(10^k) + 1/(10^(2k)) + 1/(10^(3k)) + ...)
最后一项是几何级数， 1 + q + q^2 + q^3 + ...其中|q| < 1 |q| < 1具有1/(1-q) 。 在我们的例子中， 0 < q = 1/(10^k) < 1 ，因此和为1 / (1 - 1/(10^k)) = 10^k / (10^k-1) 。 因此我们已经看到了
r / m = p / (10^k-1)
由于r和m没有共同的因素，这意味着有一个s有10^k - 1 = s*m和p = s*r 。 如果我们知道k ，周期的长度，我们可以简单地找到这一时期通过计算数字
p = ((10^k - 1)/m) * r
并填充前导零直到我们有k数字。 （注意：只有当k足够小或大整数类型可用时才是简单的。要计算具有标准固定宽度整数类型的17/983的周期，请使用@ Patrick87解释的long division。）
所以它仍然是找到时间的长短。 我们可以恢复上面的推理，并发现如果m除10^u - 1 ，那么我们可以写
r / m = t/(10^u - 1) = t/(10^u) + t/(10^(2u)) + t/(10^(3u)) + ...
= 0.t_1t_2...t_ut_1t_2...t_ut_1...
r/m的长度为u 。 所以最短时间的长度就是最小的正数u ，使得m除以10^u - 1 ，或者换句话说，最小的正数u使得10^u % m == 1 。
我们可以在O（m）时间内找到它
u = 0;
a = 1;
do {
++u;
a = (10*a) % m;
while(a != 1);
现在，找到那段时间的长度并不比寻找长周期的数字和周期长度更有效，而对于足够小的m ，这是最有效的方法。
int[] long_division(int numerator, int denominator) {
if (numerator < 1 || numerator >= denominator) throw new IllegalArgumentException("Bad call");
// now we know 0 < numerator < denominator
if (denominator % 2 == 0 || denominator % 5 == 0) throw new IllegalArgumentException("Bad denominator");
// now we know we get a purely periodic expansion
int[] digits = new int[denominator];
int k = 0, n = numerator;
do {
n *= 10;
digits[k++] = n / denominator;
n = n % denominator;
}while(n != numerator);
int[] period = new int[k];
for(n = 0; n < k; ++n) {
period[n] = digits[n];
}
return period;
}
只要10*(denominator - 1)不会溢出，那么int就可以是32位或64位整数。
但对于大分母来说，效率低下，通过考虑分母的主要因式分解，人们可以更快地找到周期长度和周期。 关于期限长度，
m = p^k ， r/m的周期长度是(p-1) * p^(k-1)的除数。 a和b互质并且m = a * b ，则r/m的周期长度是1/a和1/b的周期长度的最小公倍数。 总之， r/m的周期长度是λ(m)的除数，其中λ是卡迈克尔函数。
因此，要找到的周期长度r/m ，找到的质因数分解m和用于所有素功率因数p^k ，找到的周期1/(p^k) -等同地，10模的乘法顺序p^k ，这已知是(p-1) * p^(k-1)的除数。 由于这些数字并没有太多的因数，所以很快就完成了。 然后找到所有这些的最小公倍数。
对于期间本身（数字），如果有大整数类型可用且期限不太长，则使用公式
p = (10^k - 1)/m * r
是计算它的一种快速方法。 如果这段时间太长或者没有大整数类型，那么有效地计算数字就会变得更加混乱，而且我不记得它是如何完成的。
一种方法是重复你长时间分手的方式，并在每个阶段记下剩下的部分。 当剩余的部分重复时，剩下的过程也必须重复。 例如1.0 / 7的数字是0.1剩余3然后0.14剩余2然后0.142剩余6然后0.1428剩余4然后0.14285剩余5然后0.142857剩余1这是再次开始它的1和因此你得到0.1428571剩余3并且它重复再从那里。
链接地址: http://www.djcxy.com/p/68577.html