64位512位除以256位

l4m2

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

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


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

无心人

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

无心人

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

nyy

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

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

l4m2

先寫這麼多

1. typedef unsigned long long u64;
   
2. 
   
3. template<int N>
   
4. struct divHelper {
   
5.         static void shl(u64* dst, const u64* src, int d) {
   
6.                 asm("shldq %1, %%cl, %0": "=r"(dst[N]): "g"(src[N-1]), "0"(src[N]), "c"(d));
   
7.         }
   
8.         static void div(u64* ret, u64* mod, const u64* dive, const u64* divo) {
   
9.                 int cnt;
   
10.                 bool zf;
    
11.                 asm("bsrq %1, %q0": "=@ccz"(zf), "=r"(cnt): "g"(divo[N-1]));
    
12.                 if (zf) return divHelper<N-1>::div(ret, mod, dive, divo);
    
13.                 cnt ^= 63;
    
14.                 u64 divo2[N];
    
15.                 divHelper<N-1>::shl(divo2, divo, cnt);
    
16.         }
    
17. };
    
18. 
    
19. template<>
    
20. struct divHelper<0> {
    
21.         static void shl(u64* dst, const u64* src, int d) {
    
22.                 *dst = *src << d;
    
23.         }
    
24.         static void div(u64* ret, u64* mod, const u64* dive, const u64* divo) {
    
25.                 __builtin_unreachable();
    
26.         }
    
27. };
    

复制代码