Improve mentoring notes for difference of square

[cmcaine]

Surprisingly to me, the generator sum(x^2 for x in 0:n) appears to be constant rather than linear time, and I feel like that should probably be mentioned.

Should probably mention that the evalpoly solution is real fast, too. And that this is an example where not adding type annotations means that this will happily work with floats (though of course the answers are bunk if the float has a fractional part).

My benchmarking code:

using BenchmarkTools

# Naive
square_of_sum1(n) = sum(1:n)^2
sum_of_squares1(n) = sum(x -> x^2, 0:n)
difference1(n) = square_of_sum1(n) - sum_of_squares1(n)

# Analytical
square_of_sum2(n) = (n*(n+1) ÷ 2)^2
sum_of_squares2(n) = n * (n + 1) * (2n + 1) ÷ 6
difference2(n) = square_of_sum2(n) - sum_of_squares2(n)

# n111b111's solution
square_of_sum3(n) = evalpoly(n, (0,0,1,2,1)) ÷ 4
sum_of_squares3(n) = evalpoly(n, (0,1,3,2)) ÷ 6
difference3(n) = evalpoly(n, (0,-2,-3,2,3)) ÷ 12

# Constant time generator
square_of_sum4(n) = square_of_sum1(n)
# This seems to be constant time, so I guess there's 
# a cool LLVM optimisation in here?
sum_of_squares4(n) = sum(x^2 for x in 0:n)
difference4(n) = square_of_sum4(n) - sum_of_squares4(n)


for s in ("difference",)
    for i in 1:4
        func = Symbol(s, i)
        @info func
        # Test if this is constant or linear time.
        # Note that the answers are all wrong at 10^5
        # anyway due to overflow.
        for x in 2:5
            @eval @btime $func($(Expr(:$, Ref(10^x)))[])
        end
        # Paegodu's test
        @eval @btime $func(n) setup=(n=rand(UInt16))
        # Use in a reduction
        @btime maximum($func, 1000:1000:50000)
    end
end

Example results:

[ Info: difference1
  12.864 ns (0 allocations: 0 bytes)
  12.603 ns (0 allocations: 0 bytes)
  166.506 ns (0 allocations: 0 bytes)
  1.295 μs (0 allocations: 0 bytes)
  13.797 ns (0 allocations: 0 bytes)
  18.697 μs (0 allocations: 0 bytes)
[ Info: difference2
  3.187 ns (0 allocations: 0 bytes)
  3.183 ns (0 allocations: 0 bytes)
  3.187 ns (0 allocations: 0 bytes)
  3.182 ns (0 allocations: 0 bytes)
  3.182 ns (0 allocations: 0 bytes)
  133.089 ns (0 allocations: 0 bytes)
[ Info: difference3
  1.869 ns (0 allocations: 0 bytes)
  2.131 ns (0 allocations: 0 bytes)
  1.869 ns (0 allocations: 0 bytes)
  2.185 ns (0 allocations: 0 bytes)
  1.929 ns (0 allocations: 0 bytes)
  103.341 ns (0 allocations: 0 bytes)
[ Info: difference4
  5.439 ns (0 allocations: 0 bytes)
  5.444 ns (0 allocations: 0 bytes)
  5.439 ns (0 allocations: 0 bytes)
  5.443 ns (0 allocations: 0 bytes)
  3.998 ns (0 allocations: 0 bytes)
  285.111 ns (0 allocations: 0 bytes)