SHARE
TWEET

Untitled

a guest Jul 11th, 2016 18 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <math.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define TEST_N 1000
  6. #define START_AT 0.0
  7. #define RUNS 3000000
  8.  
  9. #define PREC 10000
  10. #define SZ 1009
  11. #define false 0
  12. #define true 1
  13. #define bool int
  14.  
  15. double M;
  16. double cache[PREC+1][SZ];
  17. void reset(double r){
  18.     static bool done=false;
  19.     if(!done){
  20.         done=true;
  21.         for(int i=0;i<=PREC;i++){
  22.             for(int j=0;j<SZ;j++){
  23.                 cache[i][j]=-1;
  24.             }
  25.         }
  26.     }
  27.     M=r;
  28. }
  29.  
  30. double R(double m, int n){
  31.     int mint=(int)(m*PREC);
  32.     if(n==1){
  33.         return 1-m;
  34.     }
  35.     else if(cache[mint][n]>=0){
  36.         return cache[mint][n];
  37.     }
  38.     else{
  39.         double sum=0;
  40.         int cnt=0;
  41.         for(int i=0;i<=PREC;i++){
  42.             double v=(i+0.00001)/PREC;
  43.             if( v<m ){ cnt++; }
  44.             else{
  45.                 if(pow(v, n-1)>R(v, n-1)){
  46.                     sum+=pow(v,n-1);
  47.                 }
  48.                 else{
  49.                     sum+=R(v, n-1);
  50.                 }
  51.             }
  52.         }
  53.         sum+=cnt*R(m, n-1);
  54.         return cache[mint][n]=sum/(PREC+1);
  55.     }
  56. }
  57.  
  58. int guess_max(double v, int ntotal, int count){
  59.     int N=ntotal-count+1; // Numbers left.
  60.     int res;
  61.     if(v<M){
  62.         res=0;
  63.     }
  64.     else if(N==1){
  65.         res=1; // We fail anyway...
  66.     }
  67.     else{
  68.         res = pow(v, N-1) > R(v, N-1);
  69.     }
  70.     if(v>M){ M=v; }
  71.     return res;
  72. }
  73.  
  74. void print(int n){
  75.     for(int nn=1;nn<=n;nn++){
  76.         printf("For N=%d: total - %lf%%, other:\nM%% ", nn, R(START_AT, nn)*100);
  77.         for(int i=0;i<100;i+=2){
  78.             printf("%2d ",i);
  79.         }
  80.         printf("\nR%% ");
  81.         for(int i=0;i<100;i+=2){
  82.             printf("%2d ",(int)(99.9999*R(i/100.0, nn)));
  83.         }
  84.         printf("\n");
  85.     }
  86.     printf("R(START, N)=%lf%%\n", 100*R(START_AT, n));
  87. }
  88.  
  89. int main(){
  90.     reset(START_AT);
  91.     int cnt=0;
  92.     int N=TEST_N;
  93.     print(N);
  94.     int runs=RUNS;
  95.     for(int i=0;i<runs;i++){
  96.         reset(START_AT);
  97.         srand(i);
  98.         double real_max = START_AT;
  99.         double your_max = -1;
  100.         int done = 0;
  101.      
  102.         for(int count=1; count<=N; count++) {
  103.             double x=rand()/(double)RAND_MAX;
  104.             if (!done && (done = guess_max(x, N, count))) {
  105.                 your_max = x;
  106.             }
  107.             if (real_max < x) {
  108.                 real_max = x;
  109.             }
  110.         }
  111.         if(your_max >= real_max-1e-12) {
  112.             cnt++;
  113.         }
  114.     }
  115.     printf("Empirical accuracy for N=%d: %lf%%\n", N, cnt/(double)runs*100);
  116. }
RAW Paste Data
Want to get better at C?
Learn to code C in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top