Strange Quarks

I listened to an ABC Radio National Ockham’s Razor podcast episode called “The magic of storytelling… in maths?” awhile ago and the speaker reminded me about triangular numbers. I realised there was a connection between this and the current problem that leads to a more compact way to represent the first method presented in part 1.

Recall also from previous posts the intention to generalise the gift total calculation to any positive number of days n, i.e. not just n = 12 days, just because we can, not because we have to! 🙂

Imagine a triangle of height 12, the interior of which is represented by dots, and so consists of 12 rows of dots. The first row has 1 dot, the second row as 2 dots, the third row has 3 dots, the 12^th row has 12 dots, and in general, the n^th row has n dots.

The first so-called triangular number is 1 with each subsequent number being that row’s number of dots plus the number of dots in all the previous rows.

So for example, the second triangular number is 2+1 = 3. The 7^th triangular number is 7+6+5+4+3+2+1 = 28, as shown above.

This simple function in the Julia programming language yields the n^th triangular number:

function triangular(n)
    num = 0
    for i in 1:n
       num += i
    end
    num
end

with the following run yielding the first 12 triangular numbers:

julia> [triangular(n) for n in 1:12]
12-element Vector{Int64}:
  1
  3
  6
 10
 15
 21
 28
 36
 45
 55
 66
 78

or even more simply:

julia> [sum(1:n) for n in 1:12]

In case you’re wondering, Int64 is just the type (64 bit integer) of the elements of the resulting list or sequence (vector) of triangular numbers.

Adding these numbers gives 364, the number of gifts in the 12 days of Christmas since the triangular numbers are just the green column of the table from part 1.

Now imagine the dots converted to green squares.

If we place another triangle, inverted on top of the green triangle with the same 12 x 12 dimension (in red, as shown), we now have a 12 x 13 rectangle, or in general, n x (n+1), or simply n(n+1).

Since the area of a triangle is half that of a rectangle, the area of the green (or red) triangle is only half of n(n+1).

Here is the mathematical notation for:

• the resulting function
• applying the function to 12 to get the number of gifts on day 12 (calculation detail shown), and
• the resulting summation of function applications for the days 1 to 12:

Since each component of the triangle has unit size (1×1 square, or in other words, a dot), it turns out that the triangle area is equivalent to the sum of all these units, which is the same as the number of gifts for day n.

Here is some Julia code that gives the number of gifts for the 12 days of Christmas using the triangular function:

function triangular(n)
    n*(n+1)/2
end

julia> sum([triangular(n) for n in 1:12])
364

We can wrap this up in the function daysofxmas, which I’ll label #8, since the last function in part 3 was #7:

# 8
function daysofxmas(n)
    sum([triangular(n) for n in 1:n])
end

In the language of computational complexity and Big-O notation, the second triangular function has time complexity O(1) — or, order 1 — whereas the first implementation of triangular has time complexity O(n).

What O(1) means for n(n+1)/2 is that computing the n^th triangular number takes so-called constant time: as fast the a machine can carry out the addition, multiplication, and addition operations. As n gets larger, the time to compute remains the same.

What O(n) means for the first triangular function in this post is that computing the n^th triangular number has so-called linear time complexity, or time proportional to the number of days, n. So, as n gets larger, so does the time taken to complete the calculation.

For an n of 12, the time taken in the calculation for both implementations of the function triangular is very small, around a millionth of a second. For n = 1 billion, the first function (using a loop) takes about 4 seconds, whereas the second still just takes around a millionth of a second.

While the area-based triangular function is a big improvement over the brute force approach to find the number of gifts on the n^th day (by replacing each row addition), it must still be coupled with a summation step to give the total number of gifts for the 12 days of Christmas, as shown in the example run above (function #8), using sum. This requires O(n) time to complete.

For n = 1 billion, that’s around 6.8 seconds to compute the total of gifts. Not bad, but we can do better, as we saw in the last post where we went down numerous implementation rabbit holes for the daysofxmas function.

Note: Before wrapping up (gift pun unintended) below, it’s worth going back to read part 3 later if you haven’t yet, to peek down those rabbit holes, but it’s quite a bit longer than this post and may be best viewed on a screen larger than a smartphone’s (or printed). While it doesn’t introduce additional mathematical approaches it’s likely to be interesting to anyone wanting to understand more about the computational approach, the tradeoffs of different algorithms, why I chose to use the Julia programming language here, optimisation, and the likelihood that your intuition regarding how to make things run faster is very likely to lead you astray. It also spells out further the relationship between the brute force approaches and the mathematics (e.g. see reference to dot product in table below).

So, let’s summarise the performance of all the functions from part 3 and part 4 now, this time with n = 100,000 — a paltry 100 thousand days of Christmas, yielding a mere 166,671,666,700,000 — about 167 million million gifts.

Function	Time (seconds)
#1: single loop with sum function	0.0005
#2: two loops	24
#3: two sum functions	0.0004
#4: dot product	0.0007
#5: dot product refinement	0.0007
#6: parallelised version of #2	13
#7: remembering all previous day totals	0.0005
#8: summation over triangular numbers	0.0003

Apart from the obvious outliers, #2 and #6, there’s not much difference for n=100,000. As n becomes larger, #2 and #6 become impractical and the difference between the others becomes more obvious. See the next post for more.

What I said in part 1 is that I want the most compact function (the simplest, with the least number of terms) possible that computes the gift total for any n. But because I also want this to be done in the shortest time possible, the function daysofxmas itself must have constant time, not linear time complexity. That means not doing any kind of summation at all!

Is there a more compact function that does not require the use of a summation step? Answering that question is the focus of part 5.

This entry was posted on January 19, 2024 at 8:52 pm and is filed under Mathematics, Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.