四舍五入常规

Question

在教程中,有些东西让我感到困惑.准确地说,整数除法.

看似首选的方法是将除数转换为浮点数,然后将浮点数舍入为最接近的整数,然后将其转换为整数:

#include <cmath>
int round_divide_by_float_casting(int a, int b){
    return  (int) std::roundf( a / (float) b); 
}

然而,这似乎是用右手刮伤你的左耳.我用的是:

int round_divide (int a, int b){
    return a / b + a % b * 2 / b;
}

这不是突破,但它不标准的事实让我想知道我是否遗漏了什么？尽管我(尽管有限)测试,我找不到任何两种方法给我不同结果的情况.是否有人遇到某种情况,其中int-> float-> int cast产生了更准确的结果？

Answer 1

算术解

如果一个定义你的函数应返回什么，她将之形容为一个接近的“f(a, b)回报分工的结果最接近的整数a通过b在真实因子环。”

因此，问题可以概括为：我们能否仅使用整数除法来定义这个最接近的整数。我认为我们可以。

恰好有两个候选者作为最接近的整数：a / b和(a / b) + 1(1)。选择很容易，如果a % b是更接近0，因为它是b，那a / b是我们的结果。如果不是，(a / b) + 1是。

然后可以编写类似的东西，忽略优化和良好实践：

int divide(int a, int b)
{
    const int quot = a / b;
    const int rem = a % b;
    int result;

    if (rem < b - rem) {
        result = quot;
    } else {
        result = quot + 1;
    }
    return result;
}

虽然这个定义满足了需求，人们可以通过不计算划分两次的优化它a通过b配合使用std::div()：

int divide(int a, int b)
{
    const std::div_t dv = std::div(a, b);
    int result = dv.quot;

    if (dv.rem >= b - dv.rem) {
        ++result;
    }
    return result;
}

我们之前对问题的分析向我们保证了我们实现的明确定义的行为。

(1) 最后一件事要检查：当a或b为负时，它的行为如何？这留给读者;)。

基准

#include <iostream>
#include <iomanip>
#include <string>

// solutions
#include <cmath>
#include <cstdlib>

// benchmak
#include <limits>
#include <random>
#include <chrono>
#include <algorithm>
#include <functional>

//
// Solutions
//
namespace
{
    int round_divide_by_float_casting(int a, int b) {
        return  (int)roundf(a / (float)b);
    }

    int round_divide_by_modulo(int a, int b) {
        return a / b + a % b * 2 / b;
    }

    int divide_by_quotient_comparison(int a, int b)
    {
        const std::div_t dv = std::div(a, b);
        int result = dv.quot;

        if (dv.rem >= b - dv.rem)
        {
            ++result;
        }
        return result;
    }
}

//
// benchmark
//
class Randomizer
{
    std::mt19937 _rng_engine;
    std::uniform_int_distribution<int> _distri;

public:
    Randomizer() : _rng_engine(std::time(0)), _distri(std::numeric_limits<int>::min(), std::numeric_limits<int>::max())
    {
    }

    template<class ForwardIt>
    void operator()(ForwardIt begin, ForwardIt end)
    {
        std::generate(begin, end, std::bind(_distri, _rng_engine));
    }
};

class Clock
{
    std::chrono::time_point<std::chrono::steady_clock> _start;

public:
    static inline std::chrono::time_point<std::chrono::steady_clock> now() { return std::chrono::steady_clock::now(); }

    Clock() : _start(now())
    {
    }

    template<class DurationUnit>
    std::size_t end()
    {
        return std::chrono::duration_cast<DurationUnit>(now() - _start).count();
    }
};

//
// Entry point
//
int main()
{
    Randomizer randomizer;
    std::array<int, 1000> dividends; // SCALE THIS UP (1'000'000 would be great)
    std::array<int, dividends.size()> divisors;
    std::array<int, dividends.size()> results;
    randomizer(std::begin(dividends), std::end(dividends));
    randomizer(std::begin(divisors), std::end(divisors));

    {
        Clock clock;
        auto dividend = std::begin(dividends);
        auto divisor = std::begin(divisors);
        auto result = std::begin(results);
        for ( ; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
        {
            *result = round_divide_by_float_casting(*dividend, *divisor);
        }
        const float unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<float>(results.size());
        std::cout << std::setw(40) << "round_divide_by_float_casting(): " << std::setprecision(3) << unit_time << " ns\n";
    }
    {
        Clock clock;
        auto dividend = std::begin(dividends);
        auto divisor = std::begin(divisors);
        auto result = std::begin(results);
        for ( ; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
        {
            *result = round_divide_by_modulo(*dividend, *divisor);
        }
        const float unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<float>(results.size());
        std::cout << std::setw(40) << "round_divide_by_modulo(): " << std::setprecision(3) << unit_time << " ns\n";
    }
    {
        Clock clock;
        auto dividend = std::begin(dividends);
        auto divisor = std::begin(divisors);
        auto result = std::begin(results);
        for ( ; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result)
        {
            *result = divide_by_quotient_comparison(*dividend, *divisor);
        }
        const float unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<float>(results.size());
        std::cout << std::setw(40) << "divide_by_quotient_comparison(): " << std::setprecision(3) << unit_time << " ns\n";
    }
}

输出：

g++ -std=c++11 -O2 -Wall -Wextra -Werror main.cpp && ./a.out
       round_divide_by_float_casting(): 54.7 ns
              round_divide_by_modulo(): 24 ns
       divide_by_quotient_comparison(): 25.5 ns

Demo

两种算术解决方案的性能无法区分（当您扩大工作台尺寸时，它们的基准会收敛）。

Answer 2

首选标准溶液。使用 cstdlib 中声明的 std::div 系列函数。

请参阅： http: //en.cppreference.com/w/cpp/numeric/math/div

在某些架构（例如微控制器）上先转换为 float，然后转换为 int 可能效率非常低。