How much memory may a HPPL program use on a G2?

[jte]

There’s certainly many algorithms for subset checking, string searching, etc. but one thing this reminded me of was my dad’s program (that he did for a comp. sci. assignment in the ’60s, on punched cards — he told me about it several times…) for handling pizza toppings. His idea was to encode each pizza topping option as a prime so that a selection of pizza toppings could be encoded as a product of those selected.

This sort of encoding could be used whilst still staying in the “lists” (or “lists of lists” etc.) approach. (Rather than introducing fancier data structures.)

Since the positions are important, primes 2, 3, 5, … could encode “a”, “b”, “c”, for the first letter; 103, 107, 109 encoding “a”, “b”, “c”, for the second letter; … (I used CAS.ithprime(27) to determine 103.) With this sort of approach, one can use divisibility to check whether a pattern matches a word.

For short words, this approach allows a single MOD to decide a match (rather than looping in PPL). (The length of “short” being decided by the need to keep the product of encoded letters within the 64 bits PPL provides for integers; evalf(product(ithprime(K*26),K,1,7)/2^64) produces 0.215352256925.)

For long words, one could employ the longer integers of CAS or break up the longer words into pieces. Hand-tuning the encoding to the used word dictionaries might help “tweak” performance. (Rearranging the ordering of which prime corresponds to which placed letter, … perhaps using products of primes rather than individual primes for placed letters.)