问个关于高精度除法的问题

Question

本帖最后由 MygodStudio 于 2012-02-24 19:57:58 编辑

Answer 1

.NET自带的除法不能满足需求吗？

Answer 2

    private static string DivideWithValidDigits(BigInteger d1, BigInteger d2, int n)
    {
        var log10 = Math.Floor(Math.Log10((double)(d1 / d2)));
        var result = new StringBuilder(n);
        var zeros = 0;
        while (result.Length - zeros <= n)
        {
            var mod = d1 % d2;
            if (result.Length - zeros >= n)
            {
                if ((d1 - mod) / d2 > 4)
                {
                    var j = result.Length - 1;
                    while (j >= 0)
                        if (result[j] == '9')
                        {
                            result[j] = '0';
                            j--;
                        }
                        else
                        {
                            result[j]++;
                            break;
                        }
                    if (j < 0)
                    {
                        result.Insert(0, '1');
                        log10++;
                    }
                }
                break;
            }
            if (mod != 0)
            {
                result.Append((d1 - mod) / d2);
                while (zeros < result.Length && result[zeros] == '0') zeros++;
                d1 = mod * 10;
            }
            else
            {
                result.Append(d1 / d2);
                while (zeros < result.Length && result[zeros] == '0') zeros++;
                break;
            }
        }
        var pos = (log10 < 0 ? 0 : Convert.ToInt32(log10)) + 1;
        if (pos < result.Length) result.Insert(pos, '.');
        return result.ToString();
    }
}
写了一个，大家看看能不能改进……

Answer 3

3楼的那个我也想到了，但是BigInteger所指定的数可能很大，因此应该用哈希表，暂时还没做，而且有时可能会反而变慢。（需求精度较低时）

Answer 4

var log10 = Math.Floor(Math.Log10((double)(d1 / d2)));
我感觉你这里强制类型转换可能会出错，会导致数据溢出。而且两个BigInteger相除，返回的结果还是BitInteger，就算强制转换也应该转化为Int32啊，怎么都不会是double类型。

Answer 5

已更正并修改：private static string DivideWithValidDigits(BigInteger d1, BigInteger d2, int n)
{
    var log10 = Math.Floor(BigInteger.Log10(d1 / d2));
    var result = new StringBuilder(n);
    var zeros = 0;
    while (result.Length - zeros <= n)
    {
        var mod = d1 % d2;
        if (result.Length - zeros >= n)
        {
            if ((d1 - mod) / d2 > 4)
            {
                var j = result.Length - 1;
                while (j >= 0)
                    if (result[j] == '9')
                    {
                        result[j] = '0';
                        j--;
                    }
                    else
                    {
                        result[j]++;
                        break;
                    }
                if (j < 0)
                {
                    result.Insert(0, '1');
                    log10++;
                }
            }
            break;
        }
        if (mod != 0)
        {
            result.Append((d1 - mod) / d2);
            while (zeros < result.Length && result[zeros] == '0') zeros++;
            d1 = mod * 10;
        }
        else
        {
            result.Append(d1 / d2);
            //while (zeros < result.Length && result[zeros] == '0') zeros++;    // zeros will be no more used
            break;
        }
    }
    var pos = (log10 < 0 ? 0 : Convert.ToInt32(log10)) + 1;
    if (pos < result.Length) result.Insert(pos, '.');
    return result.ToString();
}

Answer 6

突然想起来log10(a/b)=log10(a)-log10(b)，改进下：private static string DivideWithValidDigits(BigInteger molecular, BigInteger denominator, int validDigits)
{
    var log10 = Math.Floor(BigInteger.Log10(molecular) - BigInteger.Log10(denominator));
    var result = new StringBuilder(validDigits);
    var zeros = 0;
    while (result.Length - zeros < validDigits) // process digits
    {
        var mod = molecular % denominator;
        if (mod != 0)
        {
            result.Append((molecular - mod) / denominator);
            while (zeros < result.Length && result[zeros] == '0') zeros++;
            molecular = mod * 10;
        }
        else
        {
            result.Append(molecular / denominator);
            break;
        }
    }
    if (result.Length - zeros >= validDigits)   // process rounding
    {
        if ((molecular - molecular % denominator) / denominator >= 5)
        {
            var j = result.Length - 1;
            while (j >= 0)
                if (result[j] == '9')
                {
                    result[j] = '0';
                    j--;
                }
                else
                {
                    result[j]++;
                    break;
                }
            if (j < 0)
            {
                result.Insert(0, '1');
                log10++;
            }
        }
    }
    var pos = (log10 < 0 ? 0 : Convert.ToInt32(log10)) + 1;
    if (pos < result.Length) result.Insert(pos, '.');
    return result.ToString();
}