4

我有两个无符号长整数 X 和 Y，其中 X < Y，但两者都可能非常大。我想计算 X / Y 小数点后的第一个数字。例如，如果 X 是 11，Y 是 14，那么 11 / 14 是 .785……，所以结果应该是 7。

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

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

4

6 回答 6

4

我不愿意通过浮点转换来保证准确的结果，除非尾数有足够的位来准确表示所有整数值。例如，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,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...
于 2009-08-16T23:08:13.103 回答
3

如果我有理由相信它足够精确以计算正确的结果，则转换为 double 将起作用。

如果您只需要第一个数字，那么 double 肯定足够精确。

编辑： wrang-wrang 在评论中的反例证明我错了。

于 2009-08-16T22:54:30.813 回答
1

转换为 Double 将放弃 64 位中除数和施主的 12 位精度。大多数情况下，它会给您正确的答案，但它偶尔会出现舍入错误，除非它使用 80 位浮点格式存储.

编辑：除非我太困而看不到错误，否则我认为 wrang-wrang 的答案会起作用。我早上上班，开车6小时到客户现场。乌格。夜晚。

编辑：最后一件事。x86 使用 80 位内部表示。如果你想扔几个 asm 指令，我认为有一些操作码可以将 int64 转换为 float80。这将是一个比纯 C 实现更优雅且肯定更快的解决方案，尽管它不是可移植的。

于 2009-08-17T00:52:24.437 回答
0

X % Y 给出余数 R

然后，您可以从 R 和 Y 计算答案的小数部分

R / Y

要获得第一个数字，请使用整数除法：

(long)((long)10*R/Y)

这应该将数字四舍五入并去掉任何额外的小数。

编辑：

为了匹配您的问题（对于那些想要挑剔的人）它

Y % X = R

和

R / X
于 2009-08-17T01:43:40.970 回答
0

怎么样

x / ((y + 9) / 10)

y + 9 用于将分母中的商 y/10 向上取整，因此整体结果向下取整。

对于大 x 和 y，它应该几乎总是正确的，但它并不完美，它为您的示例 11 / 14 产生 5。

问题是您由于分裂而丢失了信息。由于乘以十已经溢出，除非使用更大的数字数据类型，否则您无法解决这个问题。

于 2009-08-17T11:28:43.707 回答
-1

如果您准备接受范围限制，您可以用整数算术完成所有操作：-

(X * 10) / Y

在您的示例中：

(11 * 10) / 14

=> 110 / 14

=> 7

限制是您将 X 的最大值减少了 10 倍。

于 2009-08-17T03:19:38.943 回答