On the N Days Of Christmas, part 6 (TL;DR)

This post summarises the results of earlier posts.

For each method, the following are given:

• A worked example for n=12 days, the only one that matters in practice for The Twelve Days of Christmas as opposed to the general problem of The N Days of Christmas I’m interested in.
• The mathematical notation generalising the method, sometimes shown together with the worked example.
• A function in the Julia programming language showing:
  • how to compute the N Days of Christmas using the method;
  • the time taken for n=100,000 and n=1000,000,000 on my M2 Mac OS X laptop, i.e. the time taken for the function calls daysofxmas(100000) and daysofxmas(1000000000) to complete.

Where multiple functions were presented for a method in earlier posts, the most efficient and representative (closest to the mathematical notation) is given.

Subtle considerations regarding function parameter and variable types that allow larger values of n to yield correct results are omitted from the code here; assume very large (128 bit) integer types.

Headings link back to the post in which the method was first introduced.

Cumulative Row Addition

Worked example for 12 days

• Day 1: 1
• Day 2: 1 + 2 = 3
• Day 3: 1 + 2 + 3 = 6
• Day 4: 1 + 2 + 3 + 4 = 10
• Day 5: 1 + 2 + 3 + 4 + 5 = 15
• Day 6: 1 + 2 + 3 + 4 + 5 + 6 = 21
• Day 7: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
• Day 8: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
• Day 9: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
• Day 10: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
• Day 11: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 = 66
• Day 12: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 = 78

Adding all the results in bold gives: 1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 + 55 + 66 + 78 = 364.

Mathematical notation

Julia function

function daysofxmas(n)
    total = 0
    for day in 1:n
        daysum = sum(1:day)
        total += daysum
    end
    total
end

Run-time for n=100,000: 0.0005 seconds

Run-time for n=1000,000,000: 8.5 seconds

Notes

• The mathematical notation is given with application to 12 days. 12 can be replaced by n for generality.
• The run-time for this method can be significantly higher. In particular, if two nested loops are used instead of a single outer loop and the efficient sum() call shown here, the time taken can be closer to 20 seconds instead of a fraction of a second. See the Row Addition post for more details.

Column Addition, i.e. Dot Product

Worked example for 12 days

• 12 lots of gift 1 = 12
• 11 lots of gift 2 = 22
• 10 lots of gift 3 = 30
• 9 lots of gift 4 = 36
• 8 lots of gift 5 = 40
• 7 lots of gift 6 = 42
• 6 lots of gift 7 = 42
• 5 lots of gift 8 = 40
• 4 lots of gift 9 = 36
• 3 lots of gift 10 = 30
• 2 lots of gift 11 = 22
• 1 lot of gift 12 = 12

Mathematical notation

Julia function

function daysofxmas(n)
    days = [1:n;]
    sum(days .* reverse(days))
end

Run-time for n=100,000: 0.0007 seconds

Run-time for n=1000,000,000: 33.7 seconds

Notes

• The mathematical notation is given with application to 12 days.
• There’s a lot more going on in the function code than meets the eye. Reversing a large list (of 100,000 elements in this case) takes time, multiplication is time consuming, and so on. There are faster ways to do this, but few quite so concise.
• The simplification shown in the worked example of doubling half the sequence of additions is not used in the function here, because as noted in the Dot Product post, it does not help the run-time and complicates the code.

Triangular Numbers

Worked example for 12 days and mathematical notation

Julia function

function triangular(n)
    div(n*(n+1), 2)
end

function daysofxmas(n)
    total = 0
    for n in 1:n
        total += triangular(n)
    end
    total
end

Run-time for n=100,000: 0.0003 seconds

Run-time for n=1000,000,000: 6.8 seconds

Notes

• See the Triangular Numbers post for the background of how we arrive at triangular numbers. Spoiler alert, it involves triangles. 🙂 A clue is that half of the width times the height of a rectangle is the area of a triangle, which if you peer closely at the triangular function above, you’ll see.

Polynomial Model

Worked example for 12 days and mathematical notation

Julia function

function daysofxmas(n)
    div(n^3, 6) + div(n^2, 2) + div(n, 3)
end

Run-time for n=100,000: 0.00001 seconds

Run-time for n=1000,000,000: 0.00001 seconds

Notes

• See Polynomial Model re: how the polynomial expression is arrived at.
• This is the fastest of all the approaches, for any value of n.

Summary

Taking the results for n=100,000 and n=1,000,000,000 into account, we have the following ranking:

Ranking	Method
1	Polynomial Model
2	Triangular Numbers
3	Row Addition
4	Dot Product

As n gets larger, the run-time difference between the methods due to these time complexity variations becomes more obvious, as can be seen from the results.

The polynomial model method computes the N Days of Christmas in constant time vs linear or quadratic time for the other methods.

It satisfies my initial goal of a simple expression with the lowest computational time complexity and shortest run-time, for any value of n. It is more than a million times faster than its nearest competitor for n = 1 billion.

If I was looking for the fastest possible function implementations, I’d use a language like C, but Julia is better than some other scientific computing languages in this regard.

“Simplest” or “most compact” may be in the eye of the beholder when it comes to mathematical notation (they’re all fairly compact) but shortest function run-time is harder to argue with.

The final post, part 7, briefly explores a possible link between triangular numbers and the polynomial model.