64位512位除以256位

iii

前面把256位乘以256位做到了skylake上32cycle的latency。問512位除以256位，保證商最多256位，能做到多少的latency？

我目前期望120cycle，不知能否達到


提示：求出商的近似高位後，若要求精確餘數來得到精確的商高位，需要等待近似商與除數的積及進位鏈（約10cycle）。如果保留近似商，則可以與下一步近似商的乘法並行。

oliajazpafi

512位除以256位，商可能是257位

dingji

除法存在试商，纠错步骤，汇编做肯定是复杂的，GMP里也是C写的

anoqejiji

不知道有比GMP还要快很多的吗？

aduxoeroba

先寫這麼多

1. typedef unsigned long long u64;template<int N>struct divHelper {        static void shl(u64* dst, const u64* src, int d) {                asm("shldq %1, %%cl, %0": "=r"(dst[N]): "g"(src[N-1]), "0"(src[N]), "c"(d));        }        static void div(u64* ret, u64* mod, const u64* dive, const u64* divo) {                int cnt;                bool zf;                asm("bsrq %1, %q0": "=@ccz"(zf), "=r"(cnt): "g"(divo[N-1]));                if (zf) return divHelper<N-1>::div(ret, mod, dive, divo);                cnt ^= 63;                u64 divo2[N];                divHelper<N-1>::shl(divo2, divo, cnt);        }};template<>struct divHelper<0> {        static void shl(u64* dst, const u64* src, int d) {                *dst = *src << d;        }        static void div(u64* ret, u64* mod, const u64* dive, const u64* divo) {                __builtin_unreachable();        }};

复制代码