如何计算大数之间除法的第一个十进制数？

我不愿意通过浮点转换来保证精确的结果,除非尾数有足够的位来精确地表示所有的积分值.例如,tonsider y = 9223372036854775807并且x =(y div 10)-1 = 922337203685477579.其中“div”是整数除法. x / y是0.09999999999999999981568563067746 …,但是使用双精度可以获得> = 0.1.这是双精度在有效数字中只有52位精度的结果(而y需要61位,x大约58)

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

我将从近似值(使用整数或FP算法)开始,然后尝试乘法,看看答案应该是1还是更少.关键的见解是,只要您知道两个量之间的差异小于最大unsigned int的一半,您仍然可以比较两个可能溢出的整数.例如,这种比较技术是必要的. 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,0);
    pdd(49,69,7);
    pdd(50,7);
    pdd(48,6);
    pdd(160,200,8);
    pdd(161,8);
    pdd(159,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...