r - Bin Fu 的算法实现没有给出正确的结果

Question

我正在尝试实现 Bin Fu's approximate sum algorithm用真实的语言更好地了解它的工作原理。

In a nutshell ，这是一个计算 $\hat{s}(x)$ 的算法，$(1+\epsilon)$ 对 $s(x)=\sum_{i=1}^n x_i$ 的近似值(例如，这意味着 $\hat{s}(x)$ 满足: $\hat{s}(x)/(1+\epsilon)\leq s(x)\leq (1+\epsilon)\hat{ s}(x)$[1]).

但是，我一定是做错了什么，因为运行我的实现并没有给出正确的结果，例如我得到的 $\hat{s}(x)$ 不满足 [1]。

我怀疑在下面的实现中，我存在得太早了，但我看不出是什么导致了这种情况。

ApproxRegion<-function(x,b,delta,n){
    if(n<=1 || x[n]<b)          return(NULL)
    if(x[n-1]<b)                return(c(n,n))
    if(x[1]>=b)             return(c(1,n))
    m<-2
    while(n-m**2>0 && x[n-m**2+1]>=b)   m<-m**2
    r<-m
    while(m>=(1+delta)){
        m<-sqrt(m)  
        if(n-floor(m*r)>=0 && x[n-floor(m*r)+1]>=b) r=m*r   
    }
    return(c(n-floor(m*r)+1,n))
}       
ApproxSum<-function(x,n,epsilon){
    if(x[n]==0)         return(0)
    delta=3*epsilon/4
    rp<-n
    i<-0
    s<-0
    b<-x[n]/(1+delta)
    while(b>=delta*x[n]/(3*n)){
        R<-ApproxRegion(x,b,delta,rp)
        if(is.null(R))      break   
        rp<-R[1]-1;
        b<-x[rp]/(1+delta)
        si<-(R[2]-R[1]+1)*b
        s<-s+si
        i<-i+1
    }
    return(list(s=s,i=i))
}

但是，当我运行它的时候

n<-100;
set.seed(123)
x<-sort(rexp(n));
eps<-1/10
y0<-ApproxSum(x=x,n=n,epsilon=eps);
y0$s*(1+eps)
sum(x)

我知道 y0$s*(1+eps) 小于 sum(x)

Answer 1

看起来您在两个地方丢失了 i 与 i+1 的轨迹，第二个 while 循环在 ApproxRegion 中，而循环在 ApproxSum 中。这看起来适用于您的示例:

ApproxRegion<-function(x,b,delta,n){
    if(n<=1 || x[n]<b)          return(NULL)
    if(x[n-1]<b)                return(c(n,n))
    if(x[1]>=b)             return(c(1,n))
    m<-2
    while(n-m**2>0 && x[n-m**2+1]>=b)   m<-m**2
    r<-m
    while(m>=(1+delta)){
        m<-sqrt(m)
        if(n-floor(m*r)>=0 && x[n-floor(m*r)+1]>=b) r=m*r
    }
    return(c(n-floor(r)+1,n))
}
ApproxSum<-function(x,n,epsilon){
    if(x[n]==0)         return(0)
    delta=3*epsilon/4
    rp<-n
    i<-0
    s<-0
    b<-x[n]/(1+delta)
    while(b>=delta*x[n]/(3*n)){
        R<-ApproxRegion(x,b,delta,rp)
        if(is.null(R))      break
        si<-(R[2]-R[1]+1)*b
        s<-s+si
        i<-i+1
        rp<-R[1]-1;
        b<-x[rp]/(1+delta)
    }
    return(list(s=s,i=i))
}

n<-100;
set.seed(123)
x<-sort(rexp(n));
eps<-0.001
y0<-ApproxSum(x=x,n=n,epsilon=eps);


> y0$s*(1+eps)
[1] 104.5955

> sum(x)
[1] 104.5719

> y0$s/(1+eps)
[1] 104.3866