Reduction、scan 与数值正确性

#include <cstddef>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <vector>
#include <utility>
long long reduce(std::vector<long long> values) {
    if(values.empty()) return 0;
    while(values.size()>1) {
        std::vector<long long> next;next.reserve(values.size()/2+values.size()%2);
        for(std::size_t i=0;i<values.size();i+=2)
            next.push_back(values[i]+(i+1<values.size()?values[i+1]:0));
        values=std::move(next);
    }
    return values[0];
}
int main() {
    for(std::size_t n=0;n<100;++n) {
        std::vector<long long> v(n);for(std::size_t i=0;i<n;++i) v[i]=static_cast<long long>(i%11)-5;
        if(reduce(v)!=std::accumulate(v.begin(),v.end(),0LL)) throw std::runtime_error("oracle");
    }
    const std::vector<long long> input{3,1,4,1,5};std::vector<long long> scan(input.size());
    std::partial_sum(input.begin(),input.end(),scan.begin());
    if(reduce(input)!=14 || scan!=std::vector<long long>{3,4,8,9,14}) throw std::runtime_error("scan");
    std::cout<<"sum="<<reduce(input)<<" scan=";
    for(std::size_t i=0;i<scan.size();++i) std::cout<<(i?",":"")<<scan[i];std::cout<<'\n';
}

#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits>
#include <stdexcept>
bool close(double value,double reference,double atol=1e-12,double rtol=1e-9) {
    if(!std::isfinite(value)||!std::isfinite(reference)||!std::isfinite(atol)||!std::isfinite(rtol)||atol<0||rtol<0) return false;
    const double difference=std::abs(value-reference);
    const double tolerance=atol+rtol*std::abs(reference);
    if(std::isfinite(difference)) return difference<=tolerance;
    if(std::isfinite(tolerance)) return false;
    // Both overflowed: compare the same quantities in bounded units.
    // Do not rely on long double having extra range on this platform.
    const double scale=std::max(std::abs(value),std::abs(reference));
    return std::abs(value/scale-reference/scale)
        <= atol/scale+rtol*(std::abs(reference)/scale);
}
int main() {
    const double large=1e16,negative=-1e16,small=1;
    const double serial=(large+negative)+small,regrouped=large+(negative+small);
    const double nan=std::numeric_limits<double>::quiet_NaN(),inf=std::numeric_limits<double>::infinity();
    if(serial!=1 || regrouped!=0 || close(nan,1) || close(1,nan) || close(inf,inf)
       || !close(1+1e-10,1) || !close(1e-13,0) || close(1,0) || close(1,1,-1))
        throw std::runtime_error("numeric contract");
    const double maximum=std::numeric_limits<double>::max();
    if(close(maximum,-maximum/2,0,2.5) || !close(maximum,-maximum/2,0,3)
       || close(maximum,-maximum,0,1.5) || !close(maximum,-maximum,0,2)
       || close(maximum,-maximum,maximum,0) || !close(maximum,-maximum,maximum,1)
       || !close(maximum,maximum/2,0,2) || !close(maximum,maximum,0,0))
        throw std::runtime_error("finite extreme tolerance");
    std::cout<<"serial="<<serial<<" regrouped="<<regrouped<<" nonfinite_rejected=1\n";
}