如何知道分数中的重复小数？

Question

我已经知道一个分数是重复小数.这是功能.

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

你知道更好的方法吗？还是一个算法？

Answer 1

一个非常简单的算法是:实现长除法.记录您所做的每个中级部门.一旦你看到一个与你之前完成的部门相同的部门,就会有重复的部分.

示例: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.看起来对我来说!剩下的就是实现细节,或者找到更好的算法!

Answer 2

如果你有一个(正)减少的分数numerator / denominator,当且仅当denominator没有素数因子而不是2或5 时,分数的十进制展开终止.如果它有任何其他素因子,则十进制展开将是周期性的.但是,分母可以被2和5中的至少一个整除,并且它不会产生略微不同的行为.我们有三种情况:

1. denominator = 2^a * 5^b,则十进制扩展终止max {a, b}小数点后的数字.
2. denominator = 2^a * 5^b * m其中m > 1不能被2或5整除,那么小数展开的小数部分由两部分组成,长度的前期max {a, b}和周期,其长度由m分子决定并独立于分子.
3. denominator > 1 不能被2或5整除,那么十进制扩展纯粹是周期性的,这意味着周期在小数点之后立即开始.

案件的处理1.和2.有一个共同的部分,让c = max {a, b},然后

numerator / denominator = (numerator * 2^(c-a) * 5^(c-b)) / (10^c * m)

其中,m = 1对于情况1.注意的因素之一2^(c-a),并5^(c-b)与我们乘分子为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包含总和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所解释的长除法.)

所以仍然需要找到这个时期的长度.我们可以恢复上面的推理并发现如果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

是一种快速计算方法.如果周期太长或者没有大整数类型可用,那么有效地计算数字会更加混乱,而且我不记得究竟是怎么做到的.