computationally efficient linear index to index pair mapping Consider two index sets $S = \{0, 1, 2, 3, 4, ..., N - 1\}$ and $Q = \{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\}$. Let $R = \{(a, b)\space |\space a, b \in S, a \ge b\} = \{(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2), \dots\}$. There will be $\frac{N(N + 1)}{2}$ elements in $R$. Is there a one-to-one function $f : Q \to R$ that is computationally efficient?

One application is to map the linear memory index to row and column of a triangular matrix. Another application is to map thread numbers to work items in parallel programs where the work deals with pairs of items (triangular domain problems).
For a given $m \in Q$, we need to find the biggest $n \in R$, such that $\frac{n(n+1)}{2} \leq m$. Hence, the first element will be $n$ and the second elemnet is $\lfloor m - \frac{n(n+1)}{2} \rfloor$. Now, the question is how can we compute $n$ efficiently? Fortunately, it can be computed by testing some constant numbers and the specified pair will be $(n, \lfloor m - \frac{n(n+1)}{2} \rfloor)$ for a given number $m \in Q$.