8
votes
Accepted
Batch rounding with preservation of a sum
There are many rounding methods that round an integer to the nearest integer, all of which are the same except on the half-integers. The sum of integers returned will be close to the sum of the ...
- 39.1k
5
votes
Batch rounding with preservation of a sum
Yves's answer will give you exactly the answer you are looking for.
An alternative is to use stochastic rounding which will give you the rounded sum in expectation, and may have nicer properties for ...
- 51
4
votes
Accepted
Are IEEE floating point numbers intervals or point values?
That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings. (Thanks for one ...
- 31.6k
4
votes
Accepted
Rounding logarithm to next integer — Potential function
The analysis there is slightly wrong, though the conclusions are correct. Here is the correct calculation:
$i$ is not a power of 2. In that case $\lfloor \log_2 i \rfloor = \lfloor \log_2 (i-1) \...
- 279k
4
votes
Why can't we round results of linear programming to get integer programming?
Here is a 2d region where rounding the optimal continuous solution (top right) will always give an invalid integer solution:
Here is a 2d region where rounding the optimal continuous solution (green ...
- 151
3
votes
Integrality gap and LP-rounding
For first question: No, it doesn't make sense. If there is no ratio between OPT(ILP) and OPT(LP-relax) (i.e. integrality gap is 1) which is very rarely to happen (only happen with problem that is in $...
- 299
2
votes
Accepted
1/2 Approximation to MAX-DICUT by rounding a linear program
The constraints force $z_{ij} = \min(x_i,1-x_j)$. Therefore you have to show that
$$
\left(\frac{1}{4} + \frac{x_i}{2}\right) \left(\frac{1}{4} + \frac{1-x_j}{2}\right) \geq \frac{1}{2} \min(x_i,1-x_j)...
- 279k
1
vote
Accepted
Floating-point rounding - bit patterns of values that are halfway between two possible results
Let us express any given binary number without a floating point in the following form
$$\underbrace{XX\cdots X}_{i\text{ digits}}~Y~\underbrace{ZZ\cdots Z}_{j\text{ digits}}{}_2=x\times2^{j+1} + Y\...
- 39.1k
1
vote
Accepted
How to rewrite a function such that integer division is applied before multiplication
The +999 will make the result go up by 1 except when xy is exactly 0 mod 1000.
It's easy to calculate xy mod 1000 without overflow, as (x mod 1000)*(y mod 1000). So we have two cases:
xy = 0 mod 1000:...
- 26
1
vote
Accepted
Converting Decimal Numbers between 0 and 1 to Binary
You are not doing arithmetic on arbitrary infinitely precise numbers. You are doing arithmetic on the subset of number representable in your computer's native floating point format. Moreover, the ...
- 12.1k
1
vote
Rounding of $2-10^{20}$ in IEEE double precision
Determine the binary exponent of $10^{20}$. From that determine the value of the lowest bit of the mantissa of $10^{20}$. Then ask yourself: How large does a number x have to be at least so that round ...
- 31.6k
1
vote
Increased rounding relative error when subtracting
On the other hand, $x−y$ has increased relative error.
The correct conclusion should be $x-y$ may have increased relative error. In other words, $x-y$ may have decreased relative error.
Let us ...
- 39.1k
1
vote
Shortest decimal expansion within binary interval
Decimal numbers with k digits to the right of the decimal point are $10^{-k}$ apart. So if you choose k large enough that $10^{-k} < 2·2^n$, then there is a decimal number with k decimals inside ...
- 31.6k
Only top scored, non community-wiki answers of a minimum length are eligible