MC: Faster User-RPL HILBERT

[Thomas Okken]

(07-09-2018 11:43 PM)Joe Horn Wrote:  

(07-09-2018 09:46 PM)Valentin Albillo Wrote:  Ah well, I thought that the point of the execise was to avoid unnecessary loops, nested loops in particular.

Also correct. A great way to avoid unnecessary calculations is by avoiding unnecessary nested loops. Thomas' program accomplishes both.

Yes and no. Depending on the coding style, you may have two nested loops, with n^2 iterations of the inner loop, or two sequential loops with n iterations each (as in the RPL code that we wrote), or one loop with n iterations (as in the 42S code that I described), but no matter which coding style you use, you're still creating and populating an n*n matrix, so there will always be O(n^2) operations somewhere.

What the algorithms we came up with accomplish is to keep the number of floating-point divisions to a minimum, computing only 2n-1 reciprocals, rather than n^2 reciprocals as in the nested-loop algorithm, but they still perform O(n^2) operations overall because the DUPN calls are O(n) each.