r - 傅斌的算法实现没有给出正确的结果

我正在尝试实现Bin Fu'sapproximate sum algorithm
用一种真实的语言去更好地感受它是如何工作的。
In a nutshell，这是一个计算$ \ {s}（x）$的算法，$（1＋ε）$近似值为$ s（x）＝SUMY{{i＝1 } ^ n xi 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)

最佳答案

看起来你在两个地方失去了i对i+1的跟踪，ApproxRegion中的第二个while循环和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