MC: Faster UserRPL HILBERT

07092018, 11:03 PM
Post: #7




RE: MC: Faster UserRPL HILBERT
(07092018 09:46 PM)Valentin Albillo Wrote:(07092018 05:25 PM)Joe Horn Wrote: Exactly. I started out thinking about this problem in terms of vector operations, HP42S 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 elementwise, 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) floatingpoint operations. Since the Hilbert matrix contains only 2n1 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 vectorbased solution that outperforms my code, please share! 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)