# Transform from linear index of a packed triangular matrix to dense indices

Given indices $i,j$ s.t. $0\leq i \leq j <n$, the function $f(i,j)=i+j(j+1)/2$ maps 2d indices to linear indices in column major order. What is the fastest way to invert this function? My first inclination is binary search on a list of the first $n$ triangle numbers but is there a faster (perhaps $O(1)$, other than a lookup table with quadratic storage complexity) solution?

Given the linear index $f$, you can invert

$f(i,j) = i+\frac{j(j+1)}{2}$

by first calculating the $j$-index via

$j = \left\lfloor \frac{-1+\sqrt{1+8f}}{2} \right\rfloor$

where $\lfloor \cdot \rfloor$ is the floor function. Then obviously $i$ follows trivially as

$i = f-\frac{j(j+1)}{2}$

The formula for $j$ is based on solving the quadratic equation

$\hat{j}^2+\hat{j}-2f=0$

where $\hat{j}$ is the real counterpart to the integer $j=\lfloor \hat{j} \rfloor$. The choice of branch cut is obvious.

Note that if $f$ is a triangle number, $\hat{j}$ is an integer.

• This was definitely what I was looking for, thank you. But with the square root, I wonder if the binary search isn't more efficient for most practical $n$. Or if it's more worthwhile to find a way to avoid the inversion altogether. – deasmhumnha Jun 2 '18 at 17:03
• @DezmondGoff I'm far from an expert on things like this, but I doubt that you could write a binary search algorithm that's faster practically than the sqrt implementation on modern processors. Maybe though. Sure, depending on your implementation, instead of a loop like (in C/C++) for (int f=0;f<(n*(n+1))/2;f++){something;} you could do for (int j=0;j<n;j++){for (int i=0;i<=j;i++){ something; } } – LedHead Jun 2 '18 at 18:38