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
 Thomas Okken Senior Member Posts: 1,120 Joined: Feb 2014
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.
 « Next Oldest | Next Newest »

 Messages In This Thread MC: Faster User-RPL HILBERT - Joe Horn - 07-09-2018, 01:28 PM RE: MC: Faster User-RPL HILBERT - Thomas Okken - 07-09-2018, 03:16 PM RE: MC: Faster User-RPL HILBERT - rprosperi - 07-09-2018, 04:32 PM RE: MC: Faster User-RPL HILBERT - Joe Horn - 07-09-2018, 05:25 PM RE: MC: Faster User-RPL HILBERT - Valentin Albillo - 07-09-2018, 09:46 PM RE: MC: Faster User-RPL HILBERT - Thomas Okken - 07-09-2018, 11:03 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 - Thomas Okken - 07-10-2018, 01:58 AM RE: MC: Faster User-RPL HILBERT - Werner - 07-10-2018, 07:20 AM RE: MC: Faster User-RPL HILBERT - John Keith - 08-05-2018, 02:05 PM RE: MC: Faster User-RPL HILBERT - Juan14 - 08-05-2018, 06:31 PM RE: MC: Faster User-RPL HILBERT - John Keith - 08-05-2018, 07:40 PM

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