Questions tagged [rounding]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
38 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 ...
2
votes
1answer
22 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
1answer
152 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
0answers
19 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}}{...
3
votes
1answer
117 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
0answers
64 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
1answer
48 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.
1
vote
0answers
45 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}\...
1
vote
2answers
66 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 ...
4
votes
0answers
51 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 ...
1
vote
1answer
61 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 ...
2
votes
1answer
286 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 ...
1
vote
1answer
157 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$,...
5
votes
3answers
5k 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 ...
0
votes
2answers
377 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.
2
votes
0answers
61 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? ...
1
vote
1answer
145 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 ...
3
votes
1answer
19k 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} =...
0
votes
1answer
699 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 ...
13
votes
1answer
461 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 ...