Как преобразовать индексы треугольной матрицы в строку, координаты столбца?

Question

У меня есть idxs:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15...ect.

которые являются индексами узлов в матрице (включая диагональные элементы):

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15
16 17 18 19 20 21
etc....

и мне нужно получить координаты i,j из этих индексов:

1,1
2,1 2,2
3,1 3,2 3,3
4,1 4,2 4,3 4,4
5,1 5,2 5,3 5,4 5,5
6,1 6,2 6,3 6,4 6,5 6,6
etc..

когда мне нужно вычислить координаты, у меня есть только один idx и я не могу получить доступ к другим.

Answer 1

Совсем не оптимизировано:

int j = idx;
int i = 1;

while(j > i) {
    j -= i++;
}

Оптимизировано:

int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5);
int j = idx - (i-1) * i / 2;

А вот и демонстрация:

Вы ищете я такой, что:

sumRange(1, i-1) < idx && idx <= sumRange(1, i)

когда sumRange(min, max) суммирует целые числа между min и max, оба включаются. Но так как вы знаете, что:

sumRange(1, i) = i * (i + 1) / 2

Тогда у вас есть:

idx <= i * (i+1) / 2
=> 2 * idx <= i * (i+1)
=> 2 * idx <= i² + i + 1/4 - 1/4
=> 2 * idx + 1/4 <= (i + 1/2)²
=> sqrt(2 * idx + 1/4) - 1/2 <= i

Answer 2

В моем случае (ядро CUDA, реализованное в стандарте C) я использую индексацию с нулевым отсчетом (и хочу исключить диагональ), поэтому мне нужно было внести несколько корректировок:

// idx is still one-based
unsigned long int idx = blockIdx.x * blockDim.x + threadIdx.x + 1; // CUDA kernel launch parameters
// but the coordinates are now zero-based
unsigned long int x = ceil(sqrt((2.0 * idx) + 0.25) - 0.5);
unsigned long int y = idx - (x - 1) * x / 2 - 1;

Что приводит к:

[0]: (1, 0)
[1]: (2, 0)
[2]: (2, 1)
[3]: (3, 0)
[4]: (3, 1)
[5]: (3, 2)

Я также повторно вывел формулу Флёрез-Руэда и Морено 2001 и пришел к следующему:

unsigned long int x = floor(sqrt(2.0 * pos + 0.25) + 0.5);

Примечание CUDA: я пробовал все, что мог придумать, чтобы избежать использования математики с двойной точностью, ноsqrtФункция в CUDA просто недостаточно точна для преобразования позиций, превышающих 121 миллион или около того, в координаты x, y (при использовании 1024 потоков на блок и индексации только по одному измерению блока). В некоторых статьях использовалась "коррекция", чтобы поднять результат в определенном направлении, но в определенный момент она неизбежно разваливается.