5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – deasmhumnha Jun 2 '18 at 17:03
  • $\begingroup$ @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; } } $\endgroup$ – LedHead Jun 2 '18 at 18:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.