如何将三角矩阵索引转换为行、列坐标？

Question

我有这些索引：

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

这是矩阵中节点的索引（包括对角线元素）：

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

我需要从这些索引中获取坐标：

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...

当我需要计算坐标时，我只有一个索引，并不能访问其他的。

- Martin877

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;

下面是演示：

您正在寻找满足以下条件的i：

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

当使用sumRange(min, max)函数时，会将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

- Victor Drouin

---

我刚刚检查了j坐标的公式，发现不正确，但程序工作得很好。我将尝试找出其中的问题。 - Martin877

我弄清楚了。j的正确等式是：idx - i * (i+1) / 2 + i，没有在末尾加上+i的话，j坐标会反转并变成负数。可能只是打错了，谢谢。 - Martin877

确实是一个打字错误，谢谢；我本来应该写(i - 1) * i / 2，而不是i * (i + 1) / 2。我已经纠正了。 - Victor Drouin

Answer 2

在我的情况下（一个使用标准C实现的CUDA内核），我使用从零开始的索引（并且我想排除对角线），因此我需要进行一些调整：

// 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)

我还重新推导了Flórez-Rueda y Moreno 2001的公式，得到了：

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

CUDA笔记：我尽了一切努力避免使用双精度数学，但是在CUDA中，单精度的sqrt函数对于将大于121百万左右的位置转换为x、y坐标（当每个块使用1024个线程，并且仅沿着1个块维度进行索引时）并不够精确。一些文章采用了“修正”来将结果向特定方向推进，但这最终会在某个点上崩溃。

- Parker