事情要从这段代码说起:

1
2
3
4
5
// gcc test.c -o test -fwrapv
int64_t multimod_fast(int64_t a, int64_t b, int64_t m) {
int64_t t = (a * b - (int64_t)((double)a * b / m) * m) % m;
return t < 0 ? t + m : t;
}

昨天晚上,有人给我发了这段据说可以替代快速乘的代码,让我解释这段代码的正确性。这段代码可以把时间复杂度从降到。显然,我们都知道int64_tdouble之间的强制转换会丢失精度,因此我对这段代码的正确性产生了怀疑。

阅读全文 »
0%