Content deleted Content added
→Examples: In the strings counted by Catalan's triangle, open parens are not unmatched, either! Ad URL for citation. Clean up a number of other citations (title first, volume/issue/page together) |
→Indexing: New section briefly (one paragraph) describing memory addressing techniques. |
||
Line 134:
| year = 1996 | doi=10.1006/jcta.1996.0087| s2cid = 15637402
}}.</ref>
In general, a triangular array is used to store any table indexed by two [[natural numbers]] where ''j'' ≤ ''i''.
==Indexing==
Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates (''i'', ''j'') to a linear [[memory address]]. If two triangular arrays of equal size are to be stored (such as in [[LU decomposition]]), they can be combined into a standard [[Array (data structure)|rectangular array]]. If there is only one array, or it must be easily appended to, the array may be stored where row ''i'' begins at the ''i''th [[triangular number]] ''T<sub>i</sub>''. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (<code>i*(i+1)/2</code>), so some optimizations such as using a [[Multiplication algorithm#Usage in computers|sequence of shifts and adds]] are not available.
==See also==
| |||