# Rounding errors for expressions with floor/ceil funcitons

In parallel computations I frequently use the following distribution of data to processors: having a sequence of $n$ elements $x_1,\ldots,x_n$ and $P$ processors $p_1,\ldots,p_P$, processor $p_k$ handles the elements $x_{\mathit{first}(k)},\ldots,x_{\mathit{last}(k)}$, where

$$\mathit{first}(k)=\left\lceil (k-1)\frac{n}{P}+\frac{1}{2} \right\rceil, \quad \mathit{last}(k)=\left\lceil k\frac{n}{P}-\frac{1}{2} \right\rceil.$$

This provide a balanced distribution such that each processor handles the same amortized number of elements. The element $x_i$ is then located in a local array of processor $p_{\mathit{proc}(i)}$ at position $\mathit{pos}(i)$, where

$$\mathit{proc}(i)=\left\lfloor \left(i-\frac{1}{2}\right) \frac{P}{n} \right\rfloor + 1, \quad \mathit{pos}(i)=i-\mathit{first}(\mathit{proc}(i)).$$

My problem is that I am not sure whether the values of $\mathit{proc}$ and $\mathit{pos}$ functions calculated by floor/ceil functions within a computer program and thus containing rounding errors may not differ from their actual values? And also, I wonder how to provide an analysis of this problem. Is there any mathematical approach for such kind of analyses/proves?

• This depends on $n$. If it's too large you might want to use a different assignent algorithm. – AlexR Feb 1 '15 at 13:52
• I can imagine $n$ going up to $10^{13}$ nowadays, $10^{16}$ in the near future. Which different assignment algorithm would you suggest? – Daniel Langr Feb 1 '15 at 13:58
• That's definately going to become an issue then. You should use an integer-based assignment algorithm. Let me write something up. – AlexR Feb 1 '15 at 13:58
• You might consider using big integers instead of floating point in your computation. For example, in C there is a "bignum" library, and Python has built-in support for big integers. – awkward Feb 1 '15 at 14:42

Basically what you are trying to do is separate $(x_n)$ into chunks of size $n/P$ (your assignment seems faulty as-is actually, the chunks will have length $P/n \to 0$ as $n\to\infty$. I suggest doing a high-precision computation of $$l := \lfloor n/P \rfloor$$ using a non floating-point algorithm of your choice and doing the same for $$r := n\ \mathrm{mod}\ P$$ Now you have two integers with $n = P\cdot l + r$ so the load can be determined by

globalIdx = 0;
for (i = 0; i < P; i++)
l[i] = i < r ? l : l + 1;
pStart[i] = globalIdx;
pEnd[i] = globalIdx + l[i] - 1;
globalIdx += l[i];
end


If $P$ also grows, we can run the algorithm in parallel on each processor in $\mathcal O(1)$. Only $l$ and $r$ need to be precomputed (feasible in $\mathcal O(\log n)$):

l[i] = i < r ? l : l + 1; // Determine my load
pStart[i] = i * l;
if (i > r) pStart[i] += i - r;
pEnd[i] = pStart[i] + l[i] - 1;

• My fault, I swapped the parts of the fractions in $\mathit{first}$ and $\mathit{last}$ when rewriting from my papers. Edited a while ago to become correct. – Daniel Langr Feb 1 '15 at 14:34
• I suggest long-division to get $l$ and $r$ simultaneously btw. – AlexR Feb 1 '15 at 14:40
• True, nice solution. But I am more concerned about calculation of processor number and the local position for $i$th element, in $\mathcal{O}(1)$ at best. – Daniel Langr Feb 1 '15 at 14:40
• @DanielLangr My algorithm can be parallelised to get $\mathcal O(1)$ as well, I'll line out how. – AlexR Feb 1 '15 at 14:41