舍入整数例程 [英] rounding integers routine
问题描述
在教程中有一些东西阻碍我使用整数算术。准确地说，整数除法。
There is something that baffles me with integer arithmetic in tutorials. To be precise, integer division.
看似优选的方法是将除数转换为浮点数，然后将浮点四舍五入为最接近的整数，然后将其转换回整数：
The seemingly preferred method is by casting the divisor into a float, then rounding the float to the nearest whole number, then cast that back into integer:
#include <cmath>
int round_divide_by_float_casting(int a, int b){
return (int) std::roundf( a / (float) b);
}
然而，这似乎用你的右手抓住你的左耳。我使用的是：
Yet this seems like scratching your left ear with your right hand. What I use is:
int round_divide (int a, int b){
return a / b + a % b * 2 / b;
}
这没有突破，但事实上它不是标准的，我缺少什么？
尽管我的测试（尽管有限），我找不到任何情况下，这两种方法给我不同的结果。有人遇到某种情况，其中int-> float-> int casting产生更准确的结果？
It's no breakthrough, but the fact that it is not standard makes me wonder if I am missing anything? Despite my (albeit limited) testing, I couldn't find any scenario where the two methods give me different results. Did someone run into some sort of scenario where the int->float->int casting produced more accurate results?
推荐答案
如果定义函数应该返回什么，她会将其描述为 f（a，b） code>返回真正除数环中 a 除以 b 除法运算结果的最接近的整数
Arithmetic solution
If one defined what your functions should return, she would describe it as something close as "f(a, b) returns the closest integer of the result of the division of a by b in the real divisor ring."
因此，问题可以概括为，我们可以只使用整数除法来定义这个最接近的整数。我认为我们可以。
Thus, the question can be summarized as, can we define this closest integer using only integer division. I think we can.
有两个候选作为最接近的整数： a / b 和（a / b）+ 1 （1）。选择很容易，如果 a％b 更接近 0 ，因为它是 b ，则 a / b 是我们的结果。如果没有，（a / b）+ 1 是。
There is exactly two candidates as the closest integer: a / b and (a / b) + 1(1). The selection is easy, if a % b is closer to 0 as it is to b, then a / b is our result. If not, (a / b) + 1 is.
和良好的实践：
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 by b / w / cpp / numeric / math / divrel =nofollow> std :: div（） ：
While this definition satisfies out needs, one could optimize it by not computing two times the division of a by b with the use of 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;
}
我们之前做过的问题的分析确保了我们良好定义的行为我们的实现。
The analysis of the problem we did earlier assures us of the well defined behaviour of our implementation.
（1）只有最后一件事要检查： a b 是否定的？这是留给读者;）
(1)There is just one last thing to check: how does it behaves when a or b is negative? This is left to reader ;).
#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";
}
}
输出：
Outputs:
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
两个算术解决方案的性能不可区分（当您缩放工作台尺寸时，它们的基准收敛）。
The two arithmetic solutions' performances are not distinguishable (their benchmark converges when you scale the bench size up).
这篇关于舍入整数例程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
