【分享+求测试】只使用O(n^2)次k位运算求nk位除法
在k大于n的时候用#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long uint;
int cnt=0;
uint random() {
static uint base = 62418510241;
base *= 1455241609451;
return base += 514141541;
}
uint div_with_8_bit(uint a, uint b) {
int d;
uint r=0, t;
cnt = 0;
while (a>=b) {
t = (a<<__builtin_clzll(a)>>(8*sizeof(uint)-15)) / (((b)<<__builtin_clzll(b)>>(8*sizeof(uint)-8))+1);
d = __builtin_clzll(b) - __builtin_clzll(a) - 7;
if (d<0) t>>=-d; else t<<=d;
if (!t) return r+1;
r += t;
a -= t*b;
cnt++;
}
return r;
}
int main() {
uint a, b,d1, d2;
int i;
int sumcnt=0;
for (i=0; i<10000000; i++) {
a=random(), b=random()>>48;
if (b==0) continue;
d1 = div_with_8_bit(a, b);
d2 = a/b;
sumcnt += cnt;
if (d1 == d2) continue;
printf ("%20llu%20llu ", a, b);
printf ("%20llu%20llu", div_with_8_bit(a, b), a/b);
printf ("%11u\n", cnt);
}
printf ("Average %f\n", sumcnt/1e7);
return 0;
}
页:
[1]