【分享+求测试】只使用O(n^2)次k位运算求nk位除法

l4m2

在k大于n的时候用

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. typedef unsigned long long uint;
   
4. int cnt=0;
   
5. uint random() {
   
6.     static uint base = 62418510241;
   
7.     base *= 1455241609451;
   
8.     return base += 514141541;
   
9. }
   
10. uint div_with_8_bit(uint a, uint b) {
    
11.     int d;
    
12.     uint r=0, t;
    
13.     cnt = 0;
    
14.     while (a>=b) {
    
15.         t = (a<<__builtin_clzll(a)>>(8*sizeof(uint)-15)) / (((b)<<__builtin_clzll(b)>>(8*sizeof(uint)-8))+1);
    
16.         d = __builtin_clzll(b) - __builtin_clzll(a) - 7;
    
17.         if (d<0) t>>=-d; else t<<=d;
    
18.         if (!t) return r+1;
    
19.         r += t;
    
20.         a -= t*b;
    
21.         cnt++;
    
22.     }
    
23.     return r;
    
24. }
    
25. int main() {
    
26.     uint a, b,d1, d2;
    
27.     int i;
    
28.     int sumcnt=0;
    
29.     for (i=0; i<10000000; i++) {
    
30.         a=random(), b=random()>>48;
    
31.         if (b==0) continue;
    
32.         d1 = div_with_8_bit(a, b);
    
33.         d2 = a/b;
    
34.         sumcnt += cnt;
    
35.         if (d1 == d2) continue;
    
36.         printf ("%20llu%20llu ", a, b);
    
37.         printf ("%20llu%20llu", div_with_8_bit(a, b), a/b);
    
38.         printf ("%11u\n", cnt);
    
39.     }
    
40.     printf ("Average %f\n", sumcnt/1e7);
    
41.     return 0;
    
42. }
    

复制代码