Questions tagged [rounding]
The rounding tag has no usage guidance.
23
questions
1
vote
2
answers
112
views
Sampling from bins with ratio preservation
I have sequence of integers $a_1, a_2, .., a_n$,
let $S_a = \sum_{i=1}^{N}{a_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a_i$ into another integer $b_i$ with 2 requirements:
$...
- 287
1
vote
1
answer
29
views
Floating-point rounding - bit patterns of values that are halfway between two possible results
I am working through the book Computer Systems: A Programmer's Perspective.
The authors explain that round-to-even rounding can be applied for values that are halfway between two possible results. For ...
- 113
2
votes
3
answers
1k
views
Batch rounding with preservation of a sum
I have a sequence of floating point numbers. I want to map each of them to one of their closest integers. There is one rule:
Sum of integers must be as close to the sum of original numbers as possible ...
- 287
1
vote
1
answer
47
views
How to rewrite a function such that integer division is applied before multiplication
Given the following function
$$
f(x,y) = (x \cdot y + 999)\; \text{div} \; 1000
$$
where $x \in \{0, 1, 2, \dots, 2^{63}-1\}$, $y \in \{1, 2, 3, \dots, 500\}$, and the div operator is defined to round ...
- 165
2
votes
1
answer
398
views
1/2 Approximation to MAX-DICUT by rounding a linear program
Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ ...
1
vote
1
answer
961
views
Converting Decimal Numbers between 0 and 1 to Binary
I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater ...
2
votes
0
answers
30
views
Integrality gap in Online Problems and adaptation to competitive ratio
As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution.
Now this gap ($IG:=\frac{OPT_{frac}}{...
- 161
3
votes
1
answer
193
views
Integrality gap and LP-rounding
I have a doubt about integrality gap.
If I know that there is no integrality gap for a given problem, i.e.:
$$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$
...
0
votes
0
answers
72
views
Doubt on integrality gap and LP relaxation
I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
1
vote
1
answer
66
views
Rounding of $2-10^{20}$ in IEEE double precision
How do we get the rounding of $2-10^{20}$ in IEEE double precision? The textbook says it is $-10^{20}$, but I do not know why. I think my textbook only explains the rule for rounding mantissa.
- 111
1
vote
0
answers
48
views
An LP with two covering constraints - how to round
I came across an LP with two covering problems, and I wonder how to
find a good approximation. For the relevant part of the LP: We have
a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\...
- 267
1
vote
2
answers
81
views
Increased rounding relative error when subtracting
I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says:
If x and y are real numbers of the same sign,
their sum x + y has an absolute error that adds the two ...
- 111
4
votes
0
answers
56
views
Compile-time error control vs. interval arithmetic?
I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out ...
- 241
1
vote
1
answer
69
views
Shortest decimal expansion within binary interval
Consider an interval $[x-2^n,x+2^n]$ defined by a binary float $x$ and a power of two $2^n$ typically much smaller than $x$. I would like to know whether an efficient algorithm exists to determine the ...
- 190
3
votes
1
answer
396
views
Are IEEE floating point numbers intervals or point values?
The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision ...
- 190
1
vote
1
answer
161
views
Rounding logarithm to next integer — Potential function
The problem is IV-3 of this pdf: potential function.
Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log_2i}\rfloor+1} + 1$
The solution states that if $i$ is not an exact power of $2$,...
7
votes
3
answers
7k
views
Why can't we round results of linear programming to get integer programming?
If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
If linear programming suggests we can afford only $3.7$ workers, then ...
- 289
0
votes
2
answers
427
views
Why are transcendental functions of large numbers inaccurate on computers?
For instance, why is it hard to accurately compute sin(1e99)? I suspect it has something to do with rounding error.
- 9
2
votes
0
answers
68
views
Normalised Floating Point System
I have a floating point number system and I have a number for which I need to calculate the exact relative error after rounding. The number is clearly an overflow. Does anyone know what I should do?
...
- 121
1
vote
1
answer
166
views
floating point rounding (1/x)*x
I'm trying to figure out what the smallest positive integer x such that the floating point expression round(round(1/x)*x) is not equal to 1 in single precision.
I have that the answer is 41, but when ...
- 11
3
votes
1
answer
21k
views
Normalizing the mantissa in floating point representation
How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format
1 - Sign bit
7 - Exponent in Excess-64 form
8 - Mantissa
$(0.148)_{10} =...
- 503
0
votes
1
answer
829
views
In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes
In a 32-bit floating number with normalized mantissa and excess-64 exponent base 16, the number $16^{-65}$ denotes
Floating point overflow.
Negative floating point overflow.
All 0's in the exponent ...
- 79
13
votes
1
answer
522
views
Floating point rounding
Can an IEEE-754 floating point number < 1 (i.e. generated with a random number generator which generates a number >= 0.0 and < 1.0) ever be multiplied by some integer (in floating point form) to ...
- 313