论坛 › 编程擂台 › 64位512位除以256位

l4m2 发表于 2023-5-18 14:41:38

64位512位除以256位

本帖最后由 l4m2 于 2023-5-18 17:05 编辑

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

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


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

无心人 发表于 2023-5-22 16:06:54

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

无心人 发表于 2023-5-22 16:07:47

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

nyy 发表于 2023-5-22 16:53:19

无心人 发表于 2023-5-22 16:07
除法存在试商，纠错步骤，汇编做肯定是复杂的，GMP里也是C写的

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

l4m2 发表于 2023-5-24 23:04:32

先寫這麼多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): "g"(src), "0"(src), "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));
                if (zf) return divHelper<N-1>::div(ret, mod, dive, divo);
                cnt ^= 63;
                u64 divo2;
                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();
        }
};

查看完整版本: 64位512位除以256位