Monday, November 24, 2014

Changes 11/24/14

Stuff:

  • Replied to Mr. Elkner's comment about infinite meta refresh
  • Read Kevin's email, he suggested that I improve the timings program by adding multiple values for n.  I was originally going to do values of {100, 1000, 10000, 100000}, but some of the algorithms seem to take a very long time values of n past 1000 so I'm not sure if I should figure out which ones run in a reasonable amount of time at large N values and run those, or just cut off the test after like 2,000 or so.
  • To keep run-time down, I only did three passes for each level, so the average values aren't as accurate as they could be.
  • Timings:
    Strategy UMD solution with n 100: 2 ms.
    Strategy UMD solution with Math.pow with n 100: 17 ms.
    Strategy UMD solution with pre-squared array with n 100: 1 ms.
    Strategy pre-squared with hash with n 100: 2 ms.
    ======
    Strategy UMD solution with n 1000: 103 ms.
    Strategy UMD solution with Math.pow with n 1000: 753 ms.
    Strategy UMD solution with pre-squared array with n 1000: 70 ms.
    Strategy pre-squared with hash with n 1000: 13 ms.
    ======
    Strategy UMD solution with n 2000: 797 ms.
    Strategy UMD solution with Math.pow with n 2000: 6051 ms.
    Strategy UMD solution with pre-squared array with n 2000: 637 ms.
    Strategy pre-squared with hash with n 2000: 21 ms.
    ======
  • I realized that these numbers were being averaged as longs, and changed it so that they would be divided as doubles.  I re-ran the test:
  • Timings:
    Strategy UMD solution with n 100: 2.75 ms.
    Strategy UMD solution with Math.pow with n 100: 19.75 ms.
    Strategy UMD solution with pre-squared array with n 100: 1.75 ms.
    Strategy pre-squared with hash with n 100: 1.75 ms.
    ======
    Strategy UMD solution with n 1000: 94.25 ms.
    Strategy UMD solution with Math.pow with n 1000: 754.5 ms.
    Strategy UMD solution with pre-squared array with n 1000: 70.75 ms.
    Strategy pre-squared with hash with n 1000: 15.0 ms.
    ======
    Strategy UMD solution with n 2000: 725.75 ms.
    Strategy UMD solution with Math.pow with n 2000: 6063.0 ms.
    Strategy UMD solution with pre-squared array with n 2000: 559.5 ms.
    Strategy pre-squared with hash with n 2000: 19.0 ms.
    ======

No comments:

Post a Comment