Clarify and improve Chaikin curve

[mainej]

Up through aa53df0, these changes are just simplification and clarification of the chaikin-curve implementation (though 537c3a5 prevents stack overflows in the 1- and 2-arity calls.)

However, 451f76e changes the return value of chaikin-curve, to be more faithful to the published algorithm and to remove several extraneous points. See that commit message for details.

[thobbs]

Hey! Thanks again for the contribution! I glanced at the changes and they look good. I've been booked with business lately and haven't had a chance to test it out, which I'd like to do before merging. Will get to that soon, just letting you know I haven't overlooked this.

Also, I left in Windows line endings? How embarrassing.

[mainej]

No problem—take your time. A few more things which might help in your tests...

It occurred to me that the old implementation might have been faster so I benchmarked with hugoduncan/criterium@0.4.4. It appears that the new implementation is faster, though with more variance:

(let [points (repeatedly 100 (fn [] [(rand-int 500) (rand-int 500)]))]
    (doall points)
    (bench (doall (old-chaikin-curve points)))
    (bench (doall (new-chaikin-curve points)))

Evaluation count : 600 in 60 samples of 10 calls.
             Execution time mean : 109.178180 ms
    Execution time std-deviation : 2.284138 ms
   Execution time lower quantile : 105.425750 ms ( 2.5%)
   Execution time upper quantile : 113.538091 ms (97.5%)
                   Overhead used : 11.604389 ns

Found 1 outliers in 60 samples (1.6667 %)
    low-severe   1 (1.6667 %)
 Variance from outliers : 9.4050 % Variance is slightly inflated by outliers

Evaluation count : 12780 in 60 samples of 213 calls.
             Execution time mean : 5.648298 ms
    Execution time std-deviation : 1.944325 ms
   Execution time lower quantile : 4.678138 ms ( 2.5%)
   Execution time upper quantile : 10.827299 ms (97.5%)
                   Overhead used : 11.604389 ns

Found 8 outliers in 60 samples (13.3333 %)
    low-severe   1 (1.6667 %)
    low-mild     7 (11.6667 %)
 Variance from outliers : 96.4613 % Variance is severely inflated by outliers

After various similar tests, it appears that performance is dominated not by implicit vs explicit iteration, as I had originally hypothesized, but instead by concat'ing on the first and last points. That's what slows things down, in these tests by about 20x.

Also, I double checked: the old algorithm produces 2^depth co-linear points at the beginning of the sequence, and the same number at the end. For a depth of 4, that's only 32 extra points, but it still affects performance.

Anyway, hope those are useful bits of info.

Windows line endings

Usually git fixes line endings for you. Except when it doesn't. Who knows.

[thobbs]

I apologize for the additional delay! Finally got a good chance to test this out, and everything works nicely. Thanks again for taking the time to do this and also to investigate the effects thoroughly! Great contribution.