c - 如何计算大数之间除法的第一个小数位？

Question

我有两个无符号长整型 X 和 Y，其中 X < Y，但两者都可能非常大。我想计算 X/Y 小数点后的第一位数字。例如，如果 X 为 11，Y 为 14，则 11/14 为 .785...，因此结果应为 7。

(X * 10)/Y 会起作用，除非它在 ​​X * 10 溢出时产生错误的结果。如果我有理由相信它足够精确以计算出正确的结果，则转换为 double 会起作用。

这是在 C 中。感谢您的帮助!

Answer 1

我不愿意通过浮点转换来保证准确的结果，除非尾数有足够的位来准确表示所有整数值。例如，tonsider y=9223372036854775807 和 x = (y div 10) - 1 = 922337203685477579。其中“div”是整数除法。 x/y 是 0.09999999999999999981568563067746...，但使用 double 会让你 >= 0.1。这是 double 的有效数字只有 52 位精度的结果(而 y 需要 61 位，x 大约需要 58 位)

您可以使用 80 位或 128 位 FP 精度，在这种情况下您会得到正确的答案，因为尾数将 >=64 位(ULL 是 64 位，对吗？)因此您可以无损地表示数字.

我会从一个近似值(使用整数或 FP 算法)开始，然后尝试乘法以查看答案应该少 1 还是多 1。关键的见解是，只要知道两个数量之间的差异小于最大无符号整数的一半，您仍然可以比较两个可能溢出的整数。例如，这种比较技术是必要的。 TCP序列号溢出。

如果您想使用仅 整数运算，则可以使用以下函数“fdd(x,y)”。我包含了一个 main() 来显示一些结果:

#include <iostream>
using namespace std;

typedef unsigned char ull; // change char to any integral type e.g. long long

const ull maxull=(ull)-1;
const ull halfull = maxull/2;
typedef unsigned long long asint;

// x = X mod (maxull+1), y= Y mod (maxull+1).  we only know x and y
// if we assume |X-Y|<halfull, then we return X<Y:
inline bool less_mod_near(ull x, ull y) {

    return (x<=halfull == y<=halfull) ? x<y : y>x;
}

// assuming x<y, return first decimal digit of 10x/y (return is in [0..9])
inline int fdd(ull x, ull y) { 
// assert(x<y);
 if (x<=maxull/10) return (10*x)/y; 
  // for speed, and to ensure that y>10 to avoid division by 0 later
 ull r=y/10;
 if (r*10==y) return x/r;
 ull ub=x/(r+1); // ub >= 10x div y (without overflow)
 ull x10=x*10; // allow overflow
 cout<<"ub="<<(asint)ub<<" x10="<<(asint)x10<<" r="<<(asint)r<<" ";
 return less_mod_near(x10,ub) ? ub-1 : ub; 
  // we already handled the 10 evenly divides y case
}

int pdd(ull x, ull y,ull mustbe)
{
    ull d=fdd(x,y);
    cout << (asint)x << '/' << (asint)y << " = ." << (asint)d << "...";
    if (d!=mustbe) cout << " (should be "<<(asint)mustbe<<")";
    cout<<endl;
//    assert(a==d);
}

int main() {
    pdd(0,1,0);
    pdd(1,2,5);
    pdd(11,101,1);
    pdd(10,101,0);
    pdd(49,69,7);
    pdd(50,69,7);
    pdd(48,69,6);
    pdd(160,200,8);
    pdd(161,200,8);
    pdd(159,200,7);
    pdd(254,255,9);
}

输出:

0/1 = .0...
1/2 = .5...
11/101 = .1...
10/101 = .0...
ub=7 x10=234 r=6 49/69 = .7...
ub=7 x10=244 r=6 50/69 = .7...
ub=6 x10=224 r=6 48/69 = .6...
160/200 = .8...
161/200 = .8...
159/200 = .7...
ub=9 x10=236 r=25 254/255 = .9...