Post Reply 
MC: Faster User-RPL HILBERT
07-10-2018, 01:25 AM (This post was last modified: 07-10-2018 01:32 AM by Thomas Okken.)
Post: #9
RE: MC: Faster User-RPL HILBERT
(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.
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
MC: Faster User-RPL HILBERT - Joe Horn - 07-09-2018, 01:28 PM
RE: MC: Faster User-RPL HILBERT - Joe Horn - 07-09-2018, 05:25 PM
RE: MC: Faster User-RPL HILBERT - Joe Horn - 07-09-2018, 11:43 PM
RE: MC: Faster User-RPL HILBERT - Thomas Okken - 07-10-2018 01:25 AM
RE: MC: Faster User-RPL HILBERT - Gerald H - 07-10-2018, 09:50 AM
RE: MC: Faster User-RPL HILBERT - ttw - 07-09-2018, 05:10 PM
RE: MC: Faster User-RPL HILBERT - Werner - 07-10-2018, 07:20 AM
RE: MC: Faster User-RPL HILBERT - Juan14 - 08-05-2018, 06:31 PM



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