MC: Faster User-RPL HILBERT

[Thomas Okken]

(07-09-2018 09:46 PM)Valentin Albillo Wrote:  

(07-09-2018 05:25 PM)Joe Horn Wrote:  Exactly.

Ah well, I thought that the point of the execise was to avoid unnecessary loops, nested loops in particular.

This can be cleverly accomplished using vector operations but I can't elaborate the concept further as (1) I don't indulge in cryptolanguages, and (2) I don't know if the various cryptodialects do include the necessary vector operations in their respective instruction sets.

Regards.
V.
.

I started out thinking about this problem in terms of vector operations, HP-42S style, and what I came up with was this:

1. Create a row vector containing the numbers 1 through n
2. Use the 10^X function to obtain a row vector containing the numbers 10 through 10^n
3. Calculate the outer product of said row vector and the corresponding column vector
4. Use the LOG function to obtain a matrix where each element with indices (m, n) equals m+n
5. Subtract 1 from each element
6. Take the reciprocal of each element

This is pretty compact and reasonably efficient: after creating the initial [ 1 2 ... n ] vector (step 1), all the following steps are basic 42S logic: 10^X TRANS LASTX * LOG 1 - 1/X. This works because applying 10^X, LOG, and 1/X to a vector or matrix all work element-wise, and so does the subtraction of a scalar from a matrix. The LOG and 10^X operations are efficient, too, in this case, because we're applying 10^X to integers and applying LOG to integral powers of 10.

However, the challenge that was presented here was about speed, and the above algorithm fails in that regard, just like the obvious algorithm with two nested loops, because they use O(n^2) floating-point operations.

Since the Hilbert matrix contains only 2n-1 distinct numbers, O(n^2) FLOPS is really bad, at least when the cost of a FLOP is significant compared to the cost of allocating elements.

If you have a vector-based solution that outperforms my code, please share!