SHARE
TWEET

Brute force counting of mean ops per Fenwick tree update

a guest Jun 26th, 2015 213 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. int bf_ops_for_number(int x, int n) {
  7.     if (x > n) {
  8.         return 0;
  9.     } else {
  10.         return 1 + bf_ops_for_number(x + (x & -x), n);
  11.     }
  12. }
  13.  
  14. int main(int argc, char *argv[]) {
  15.         double worst = 0;
  16.         for(int n=1; n<65536; n++) {
  17.                 double sum = 0;
  18.                 double result;
  19.                 for(int j=1; j<=n; j++) {
  20.                         sum+=bf_ops_for_number(j, n);
  21.                 }
  22.                 result = sum/n;
  23.                 if (result > worst) {
  24.                     worst = result;
  25.                     printf("NEW WORST: %f for n=%d\n", result, n);
  26.                 }
  27.         }
  28. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top