2

I am working with a lower triangular matrix, the function below calculates a row index of such matrix. How can I optimize it in terms of execution time?

The triangular matrix can hold at most N (N + 1) / 2 nonzero elements (where N is the matrix dimension - N x N).

I have a set of numbers 0, 1, 2, ..., N (N + 1) / 2 - 1 and from those, I have to calculate the matrix row index.

My current solution:

inline 
unsigned int calc_row(unsigned int i)
{
    return static_cast<unsigned int>(floor(sqrt(static_cast<double>(0.25 + 2 * i)) - 0.5));
}

// example:
calc_row(0) == 0;
calc_row(1) == 1;
calc_row(2) == 1;
calc_row(3) == 2;
calc_row(4) == 2;
calc_row(5) == 2;

Question:

1) Do you think my current solution is performance friendly?
2) If not how can I optimize it (in terms of the function execution time)?

If You believe an alternate method to calculate the row index would perform better, I am fine with it. Unfortunately the lookup table is not an option in my case.

EDIT #1:

I just had an idea: Is there a way to make a template metaprogramming version of the lookup table? A way to generate the row number at a compile time could prove to be a significant optimization. The biggest unsigned int i would be around 10 million in my case.

EDIT #2:

I edited the entire question because it caused a major confusion. I am sorry about that.

EDIT #3:

calc_row() calculates the formula: (sqrt(1 + 8 * i) - 1) / 2 which is the solution for the quadratic equation x(x + 1) / 2 = i. Where i is row index.

The main idea for this solution lies in the fact that the linear index for a triangular matrix with diagonal can be calculated as: i (i + 1) / 2 + j. Where i is row index and j is column index.

PatrykB
  • 1,579
  • 1
  • 15
  • 24
  • You could do `2 * n` to `n << 1` but compiler probably already done it. – kocica Aug 13 '17 at 11:10
  • Have you measured it? Also, you might want to read https://ericlippert.com/2012/12/17/performance-rant/ – Kris Vandermotten Aug 13 '17 at 11:15
  • 2
    I don't understand. The page you linked shows the formula is `n*(n+1)/2`. Where do you get the formula you're using? – Banex Aug 13 '17 at 11:20
  • @Banex I am using the code in the example to calculate the `row index` of the triangular matrix having only a `natural number`. I got this code from [here](https://stackoverflow.com/questions/9674179/getting-the-row-and-column-of-a-triangular-matrix-given-the-index/9674523#9674523) I have a number in range `N = 0, ..., N * (N + 1)/2` and i need to convert that into a pair of numbers `{ row, col }` – PatrykB Aug 13 '17 at 11:24
  • What does that have to do with "generating a set of triangular numbers"? – Oliver Charlesworth Aug 13 '17 at 11:27
  • you say in the title that you want to generate a set, but in your code it doesnt look like a set. How do you want the resulting set to look like? – supinf Aug 13 '17 at 11:27
  • @supinf sorry this is my mistake. I just need to generate a number having another number. The idea of a set in my question comes from the fact that I am generating tons of the `triangular numbers` in a `for loop`. – PatrykB Aug 13 '17 at 11:32
  • @OliverCharlesworth because the `row index` is the same as a `triangular number`. unfortunately, I am unable to calculate it in the simplest way using the formula from the `math wiki` page. (the input is different from what I have). I have `0, 1, 2, ..., N * (N + 1)/2` numbers but in my case, the formula on the `wiki page` will accept only `0, 1, 2, .. N` numbers. – PatrykB Aug 13 '17 at 11:35
  • Then it seems we have different definitions of "triangular number". I'm using the standard one ;) – Oliver Charlesworth Aug 13 '17 at 11:36
  • @OliverCharlesworth I am sorry I make such a confusion. The difference lies in the fact that I am working with triangular matrices. In order to optimize memory and execution time, I want to store a matrix in a 1D array. A triangular matrix has at most `N * (N + 1)/2` entries (`N` is dim of the matrix - `N x N`). So in my case, i will be working with `0, 1, 2, ..., N * (N + 1)/2` numbers, so the equation from the `math wiki` page will not work. – PatrykB Aug 13 '17 at 11:39
  • Then you should probably update your question to just say that. People are going to be confused because you don't want what you're asking for (i.e. you're not trying to calculate triangular numbers). – Oliver Charlesworth Aug 13 '17 at 11:44
  • Done. One more time sorry... – PatrykB Aug 13 '17 at 11:53
  • 1
    Cool, now it all makes sense :) – Oliver Charlesworth Aug 13 '17 at 11:59
  • 1
    A comment rather than an answer: your solution is fragile in the face of floating-point error, since it depends on sqrt giving exact answers when possible: for example, if `n=55`, `sqrt(0.25 + 2*n) - 0.5` is exactly `10.0`, and a single unit-in-the-last-place of floating-point error could result in the floor operation returning `9.0` instead of `10.0`. `sqrt(1 + 2*n)` or `sqrt(1.25 + 2*n)` would be safer. On typical machines supporting IEEE 754, `sqrt` _is_ likely to be correctly rounded, but it's better safe than sorry. – Mark Dickinson Aug 13 '17 at 13:22
  • @MarkDickinson I edited my question (**EDIT #3**) to show how to get the equation for row index. Do you think `(1 + sqrt(1 + 8 * n)) / 2` would be better, or `sqrt(1 + 2*n) - 0.5` is sueficient? – PatrykB Aug 13 '17 at 13:38

0 Answers0