diff options
| -rw-r--r-- | charf.c | 54 |
1 files changed, 40 insertions, 14 deletions
@@ -83,31 +83,57 @@ void compute_maximalfunction(VALUETYPE* f, VALUETYPE* Mf, int D){ VALUETYPE* Sf[N]; VALUETYPE* Af[N]; for(int i=0; i<D; i++){ - Sf[i] = malloc(D*sizeof(VALUETYPE)); - Af[i] = malloc(D*sizeof(VALUETYPE)); + Sf[i] = malloc((2*D+1)*sizeof(VALUETYPE)); + Af[i] = malloc((2*D+1)*sizeof(VALUETYPE)); } for(int i=0; i<D; i++) { - Sf[i][i] = f[i]; - Af[i][i] = f[i]; + Sf[i][1] = f[i]; + Af[i][1] = f[i]; } - - for(int n=1; n<D; n++){ + + for(int l=2; l < 2*D; l++){ /*Recursively compute all integrals and averages over intervals of increasing length*/ for(int i=0; i<D; i++){ - Sf[i][(i+n)%D] = sum(Sf[i][(i+n-1)%D], f[(i+n)%D]); - Af[i][(i+n)%D] = ratio(Sf[i][(i+n)%D],int_to_valuetype(n+1)); + Sf[i][l] = sum(Sf[i][l-1], f[(i+l-1)%D]); + Af[i][l] = ratio(Sf[i][l],int_to_valuetype(l)); } } - - /*Compute maximal function by picking the largest average*/ + + Af[0][2*D] = Af[0][D]; + + int Pbest[N]; + int Lbest[N]; for(int i=0; i<D; i++){ - Mf[i] = Af[i][i]; - for(int j=1; j<=D; j++){ - Mf[i] = maximum(Af[i][(i+j)%D], Mf[i]); - Mf[i] = maximum(Af[(i-j+D)%D][i], Mf[i]); + Pbest[i]=0; + Lbest[i]=2*D; + } + + for(int l=2*D-1; l>0; l--) { + for(int i=0; i<D; i++){ + VALUETYPE A = Af[i][l]; + int n=i; + while(n<i+l && n<i+D){ + if(is_greater_certainly(Af[Pbest[n%D]][Lbest[n%D]],Af[i][l])) n += (Pbest[n%D]-n-D)%D + Lbest[n%D]; + else{ + A = maximum(A,Af[Pbest[n%D]][Lbest[n%D]]); + int k = n+1; + while((Pbest[k%D] == Pbest[n%D]) && (Lbest[k%D] == Lbest[n%D]) && k<i+l && k<i+D){ + Pbest[k%D] = i; + Lbest[k%D] = l; + k++; + } + Pbest[n%D] = i; + Lbest[n%D] = l; + n=k; + } + } + Af[i][l] = A; } } + + /*Compute maximal function by picking the largest average*/ + for(int i=0; i<D; i++) Mf[i] = Af[Pbest[i]][Lbest[i]]; /*Print computed functions and averages*/ /* |