exercism / exercism/julia

Improve mentoring notes for difference of square

Open
#264 0 comments 0 reactions 0 assignees View on GitHub
good first issue
Dominant language
Julia
Stars
73
Forks
82
Avg merge
2h 17m
Merged PRs (30d)
5

Description

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:

```julia
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)
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.