I am studying data structures/compiler design. And I am surprised that I can't find much reputed resources for learning LTM Column Major. There are books like sartaj sahni and debasis samnatha which lightly present this.<p>I google<p>filetype:pdf "row-major order" compiler design OR data structures "column-major order"<p>Still I didn't get accurate results.<p>Theere are some trash videos on youtube, and almost everyone is deriving hacky way. I want a mathematical way of deriving the address calculation. I would love if they're using different techniques to calculate the address.
> I want a mathematical way of deriving the address calculation<p>So, filling in some blanks, you<p>- want to store the lower triangular matrix as a single contiguous array of <i>n × (n+1) ÷ 2</i> items<p>- don’t want to store an additional array of column offsets<p>and hence need a way to compute an offset into that contiguous array from <i>(row,column)</i> coordinates with <i>row ≥ column</i> (elsewhere, the matrix contains zeroes)<p>I first would consider storing the columns in reverse order, as that would mean storing<p>- 1 item for the last column<p>- 2 items for the next-to-last<p>- …<p>- <i>n</i> items for the first column<p>Offsets then are 1, 3, 6, 10, etc. Those are the triangular numbers (<a href="https://oeis.org/A000217" rel="nofollow">https://oeis.org/A000217</a>)<p>Calculation of the column offset then would be (counting rows and columns from <i>1</i> to <i>n</i>; untested, so chances are there is an off-by-one error there somewhere)<p><pre><code> (n - column) × (n - column + 1) ÷ 2
</code></pre>
If you don’t want to reverse column order, I think it’s easiest to think of the problem as computing an offset from the end of the array:<p>- to find the column offset, you have to move back from there by <i>(n - column)</i> columns<p>- so, you have to move back <i>1 + 2 + 3 + … + (n - column)</i> items<p>- that’s <i>(n - column) × (n - column + 1) ÷ 2</i> items.<p>The offset from the start would be <i>n × (n - 1) ÷ 2)</i> minus that.
Start with small matrices (1×1, 2×2, 3×3, ...), do the calculations by hand to gain some intuition, come up with a generalization to n×n matrices, prove it by induction.