c++ 不使用bigint如何比较这个大产品

ss2ws0br  于 2023-02-26  发布在  其他
关注(0)|答案(1)|浏览(94)
long long a,b,c,d,e,f,g,h;
bool is_greater = a*b*c*d > e*f*g*h;

我试着将类型转换为long double,然后使用除法(例如,lhs上的一个变量除以rhs上的另一个变量),但是由于精度错误,我得到了不正确的输出。
我的另一个想法是先尝试高位数,然后是低位数,类似于这样

int M=1e9;
p1 = a/M;
q1 = b/M;
r1 = c/M;
s1 = d/M;

u1 = e/M;
t1 = f/M;
v1 = g/M;
w1 = h/M;

if (p1*q1*r1*s1 > u1*t1*v1*w1) return true;
if (p1*q1*r1*s1 < u1*t1*v1*w1) return false;
//if equal try lower digits:
p2 = a%M;
q2 = b%M;
r2 = c%M;
s2 = d%M;

u2 = e%M;
t2 = f%M;
v2 = g%M;
w2 = h%M;
return (p2*q2*r2*s1 > u2*t2*v2*w1);

正如@n-m所说的,这就是bigint,但我之所以要逆向工程,是因为我有另外一条信息,结果是256位,但我有信息99.99%的时间差在最后128位,最有可能在最后64位,我想用这个信息使我的代码更快(在摊销的基础上),但不会受到精度误差的影响。所以我在两边都做了一些权衡。

eqzww0vc

eqzww0vc1#

如果

a * b * c * > e * f * g * h [1]

a/e * b/f * c/g * d/h > 1 [2]

假设全部为正。如果 e、f、g、h 中的某些为负:

  • 如果它们中奇数个是负翻转,
  • 如果偶数为负,则不改变符号

结论是:如果[2]为真,则[1]也为真(再次注意符号)
伪码:

int p = 0;
for (x in [efgh])
    if (x < 0)
        p += 1;

if (pow(-1, p) < 0)
    flip_the_sign;

相关问题