Index Retrieval, and Proving Two Rules Are Inverses
Chapter Twenty-Four
Syllabus topic Module 1, "Naṣṭa and Uddiṣṭa (index retrieval mechanisms)", "minimum 10 test cases"
Pages 77 to 79 of 378
In one line
Naṣṭa and uddiṣṭa are two directions of the same index: number to pattern, and pattern to number, neither of which needs the table.
In the wording you can write in an examination: an index retrieval mechanism provides access to an element of an ordered collection by its position, and to the position of a given element, in time that does not depend on the size of the collection. Naṣṭa and uddiṣṭa together provide both directions for the prastāra, each in time proportional to the number of syllables, and they are exact inverses of one another.
What "index retrieval" means, and why it is not a small thing
Consider three ways to answer "what is the forty-first row of the gāyatrī?".
Scan. Generate rows from the first and count. Cost: proportional to the row number. For row 4000, four thousand rows of work.
Store and look up. Write the whole table once and index into it. Cost: one step per query, but the table has to exist, and it costs n times 2 to the power n to build and to hold.
Compute. Derive the row from its number with no table at all. Cost: proportional to n, and nothing is stored.
The third is what naṣṭa does, and it is the one that scales. For a thirty-syllable metre the table would hold about a billion rows and the computation still takes thirty steps.
The modern name for what the third option exploits is a direct or computed address. An array index works this way: the address of element i is the base plus i times the element size, computed rather than searched. A hash table works this way too, with a function from the key to the address. Piṅgala's rules are a computed address into a structure that was never built.
The two directions, side by side
| Naṣṭa | Uddiṣṭa | |
|---|---|---|
| Given | a row number | a pattern |
| Returns | the pattern | its row number |
| Sūtras | 8.24 lardhe, 8.25 saike g | 8.26 pratilomaguṇaṃ dvirlādyam, 8.27 tato'pyekaṃ jahyāt |
| Direction of writing | left to right | right to left |
| Arithmetic per syllable | halve, adding one first if odd | double, subtracting one at a guru |
| Cost | proportional to n | proportional to n |
| Needs the table | no | no |
The symmetry is exact, and it is the symmetry of an encoder and a decoder: one takes a number to a representation and the other takes the representation back to the number.
The proof that they are inverses
Two functions are inverses if applying one and then the other returns you to where you started, both ways round. For a finite set that can be checked exhaustively, and here it can.
def nasta(n, r):
out = []
x = r
for _ in range(n):
if x % 2 == 0:
out.append("L")
x //= 2
else:
out.append("G")
x = (x + 1) // 2
return "".join(out)
def uddista(pattern):
y = 1
for ch in reversed(pattern):
y *= 2
if ch == "G":
y -= 1
return y
print("%-6s %-8s %-10s %s" % ("n", "rows", "inverses", "first failure"))
for n in range(1, 17):
bad = [r for r in range(1, 2 ** n + 1) if uddista(nasta(n, r)) != r]
print("%-6d %-8d %-10s %s" % (n, 2 ** n, "yes" if not bad else "no",
"none" if not bad else bad[0]))Index Retrieval, and Proving Two Rules Are Inverses
n rows inverses first failure
1 2 yes none
2 4 yes none
3 8 yes none
4 16 yes none
5 32 yes none
6 64 yes none
7 128 yes none
8 256 yes none
9 512 yes none
10 1024 yes none
11 2048 yes none
12 4096 yes none
13 8192 yes none
14 16384 yes none
15 32768 yes none
16 65536 yes noneSixteen syllable counts, 131,070 rows in total, every one checked in both directions.
Why exhaustive checking is worth something here, and where it stops
What it establishes. For every metre up to sixteen syllables, the two rules are exactly inverse. No case within that range can be wrong.
What it does not establish. That they are inverse for every n. A test over a finite range is a test, not a proof.
The proof, for the record, is the argument given in the two previous chapters: both rules compute the same correspondence between row numbers and binary values, one in each direction, and a bijection's inverse is unique. State the argument and offer the check as evidence, never the check alone. That is the difference between a program that passes and a claim that is justified, and it is the distinction MU's "analysis of correctness" is asking for.
Worked example: the other direction, and the round trip
Take the jagatī, twelve syllables, and row 2731.
Naṣṭa. 2731 is odd, so add one and halve to 1366, writing G. 1366 halves to 683, writing L. 683 is odd, so 342, writing G. 342 halves to 171, L. 171 odd, 86, G. 86 halves to 43, L. 43 odd, 22, G. 22 halves to 11, L. 11 odd, 6, G. 6 halves to 3, L. 3 odd, 2, G. 2 halves to 1, L. The pattern is G L G L G L G L G L G L.
Uddiṣṭa on that pattern. From the last syllable, which is L: 1 doubles to 2. G: 4 less one, 3. L: 6. G: 12 less one, 11. L: 22. G: 44 less one, 43. L: 86. G: 172 less one, 171. L: 342. G: 684 less one, 683. L: 1366. G: 2732 less one, 2731.
Index Retrieval, and Proving Two Rules Are Inverses
The round trip closes, and the alternating pattern is worth noticing: the row numbers of alternating patterns are the numbers whose binary form alternates, which for twelve places is 2730 as a value and 2731 as a row.
What this does NOT give you
It does not give you search. Neither rule answers "which rows have exactly four laghus?". That is lagakriyā, and it is a different pratyaya with a different answer, in [Meru-Prastāra: Halāyudha's Staircase].
It does not give you a sorted order other than its own. The index is the index of Piṅgala's order. A question about a different order needs different rules.
It does not validate anything. Neither rule checks that the row exists or that the pattern has the right length. A program that exposes them to a user must.
Quick revision
- Index retrieval: reaching an element by its position, and a position by its element, in time independent of the collection's size.
- Naṣṭa is number to pattern; uddiṣṭa is pattern to number. Each costs one step per syllable and needs no table.
- The modern analogue is a computed address, as in an array index or a hash function.
- The pair is exactly inverse; checked over 131,070 rows up to sixteen syllables, and proved by the binary correspondence.
- An exhaustive check over a range is evidence, not a proof. Give the argument and offer the check.
- Neither rule searches, validates, or works for a different ordering.
Test yourself
1. What does it mean to call naṣṭa and uddiṣṭa index retrieval mechanisms?
They give access to a row by its position and to a position by its row, in time proportional to the syllable count and independent of the number of rows, without the collection being stored.
2. Compare the three ways of answering "what is row 4000 of the jagatī?" by cost.
Scanning costs about 4000 rows of work. Storing the table costs 4096 rows of space to build and hold, then one lookup. Computing by naṣṭa costs twelve steps and no space.
3. Why is the exhaustive check in this chapter not a proof, and what is the proof?
Because it covers only n up to sixteen. The proof is that both rules compute the same bijection between row numbers and binary values, one in each direction, and the inverse of a bijection is unique.
4. Which question do these two rules NOT answer, and which pratyaya does?
They do not answer how many patterns have a given number of light syllables. That is lagakriyā, answered by the Meru-prastāra.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.