Archive for the ‘Maths’ Category

ELI5: monoids

Monday, February 29th, 2016

(Resulting from my claim that “a child of 8 can understand monoids…”)

Wikipedia says: “In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.”

Wolfram says: A monoid is a set that is closed under an associative binary operation and has an identity element I ∈ S such that for all a ∈ S, Ia = aI = a.

Mathematics has to be precise, which is why it uses jargon. But what do these concise definitions mean in everyday language? Consider adding up numbers.

  • The set is the whole numbers (and we need zero). 0, 1, 2, 3 etc.
  • The associative binary operation is addition.
    • “binary” just means it’s a thing you do to two numbers.
    • “associative” means it doesn’t matter what order you group things in. 1 + 2 + 3 gives the same answer whether you add 1 and 2 first and then add 3, or add 2 and 3 first and then add the answer to 1.
  • The set being “closed” under addition means that when you add two numbers you get another number – you don’t get some other kind of thing. (You might think this is obvious, but in maths it has to be stated.)
  • The identity element is 0 – the thing that doesn’t make any difference when you add it. Anything plus zero is itself.

So adding whole numbers is a monoid. A mathematician would say that the non-negative integers form a monoid under addition. The important thing is that the numbers aren’t a monoid on their own; it’s the combination of the set (0, 1, 2, 3…) and the operation (+) that makes the monoid. If we chose another operation, we could get another monoid. Think about multiplication, for instance.

It turns out that lots of things behave the same way as addition on numbers, which is why the notion of a monoid is very useful to mathematicians and computer scientists.

Amaze your friends, and confound your enemies!

Wednesday, November 4th, 2015

When I was young, I read lots of books with titles (or at least subheadings) along the lines of, “Amaze Your Friends and Confound Your Enemies” – a lot of them were filled with tricks and oddities like the Birthday Paradox, or the old saw about the elephant from Denmark.

It turns out that if you read and continue to read enough of this kind of thing, you can continue to amaze your friends well into adulthood! A lot of times this means appearing to be good at mental arithmetic. And the trick to being good at mental arithmetic is not to be especially fast at rote calculation. It lies in a web of knowledge about numbers.

An aside about maths teaching

I often think that number theory is poorly served by the mathematical curriculum almost everywhere. Kids learn times tables and are introduced to prime numbers, and then I think the number theory track more or less stops, and a student doesn’t meet it again until university-level maths. Which is a shame, because there are many interesting and fun problems in number theory that can be easily stated and understood by a ten-year-old but which still remain unsolved. Also, a more continuous (ha!) grounding in number theory would give us a better understanding of some very important features of the modern world – an obvious example being cryptography.

I was lucky enough, as a 12-13 year old, to have a recreational maths class at school for a year where we tackled problems together. It was distinctly constructivist in nature – whether by design or not – and it was a really fun class because we were typically all trying to solve a hard problem over the course of a few weeks. “Copying” other people’s work and building on it towards a solution was par for the course – as in real life! We took inspiration from the writings of people like Martin Gardner, Sam Loyd, Raymond Smullyan, Henry Dudeney and Eric Emmet. The teacher would ramp up the difficulty of problems as we went – and in mathematics there is almost always a way, having solved one problem, to remove a constraint or make it more general in some way to provide a step up to the next level.

A typical class exchange:

Teacher: Who can tell me how many squares there are on a chessboard?
Student A: 64!
Teacher: Ah yes. Correct. But I see you’re only counting the squares that are one square in size, as it were. I think there might be more squares there…
Student A: …
Student B: Wait a minute…
Class: *realization* *time passes, working-out*
Class: 204!
Teacher: Correct. For your chessboard there. But my chessboard has n squares on a side, not 8.
Class: *argh* *more time passes, probably a week*
Class: Um… (a few tries, and then)… n(n+1)(2n+1)/6 ?
Teacher: Right! But… hm… my chessboard got broken, now it’s not square any more, it’s n by m. Oh, and I want to know how many rectangles are on it.
Class: *mind blown*

Associations – it’s what brains do

Anyway, the human brain is fantastically good at constructing associations. And being “good at maths” is about having lots of those associations when it comes to numbers. Mathematicians often have this. Computer people have this facility, when it comes to powers of 2, and it looks astounding to muggles when it comes out in another context (eg Biology class):

Teacher (thinking he is asking a hard question): This germ divides in two every hour. If we start with just one germ here, how many will we have after a day?
Nerdette in the back row (instantly): 16,777,216
Rest of the class: How the hell…?

When you have enough associations, they start to overlap and provide multiple ways to an answer. I was recently out with a group of friends and at the end of the night we came to pay the bill. There were seven of us, and the bill was $195. I immediately knew it was about $28 each, and I didn’t have to calculate, because of some associations:

  • 196 is 14 squared, which is 7 * 28. Immediate answer. (Square numbers up to 20 or so – very useful to know.)
  • In the UK weight is often measured in stones. 14lbs = 1 stone, and I know that 98lbs = 7 stones or 7*14 = 98. And as 98*2 = 196, because (100-2)*2 = 200-4 = 196, so 14*2 = 28. Corroboration by overlapping association.

“Wizardry” with 1/7

Another second’s thought provides the exact amount per person, because 1/7 is a useful and interesting fraction to know. It has a recurring 6-digit pattern, and it cycles. Once you know the six digits of 1/7, it’s trivial to figure out/remember the other fractions:

  • 1/7 = 0.142857142857142857…
  • 2/7 = 0.285714…
  • 3/7 = 0.428571…
  • 4/7 = 0.571428…
  • 5/7 = 0.714285…
  • 6/7 = 0.857142…

This is a fun trick for kids: compute 142857 * 2, 142857 * 3, etc and see how the digits cycle. Then try 142857 * 7… and you get 999999. Neat.

Anyway, 28*7=196 but the bill is $195, which means actually everyone pays $28, less 1/7 of a dollar. So the exact figure is $27 and 85.714285… cents.

Fun for kids

When numbers are your friends, it’s easy to look like you’re a wizard. And it’s really just about forming those associations. When I see 41, I think of Euler’s famous expression x2 + x + 41 which is prime for every x from 0 to 39. When I see 153, I think, “Hello, 13 + 53 + 33!” And similarly for many other numbers and mathematical techniques, thanks to all that reading and playing with numbers as a child. These days I entertain my kids by having them do fun math tricks like:

Enter any three-digit number into your calculator (say 456)
Multiply by 7
Now multiply again by 11
Now multiply again by 13
The result is the original number “doubled up” (say 456456) – because 7 * 11 * 13 = 1001

I’m teaching them how to amaze their friends and confound their enemies!

How many bugs are left? The Lincoln Index

Friday, March 6th, 2015

You’re working on some software, and you have some QA folks testing it. How do you know how many bugs are left? You know the bugs that the testers find, but how can you estimate the number that aren’t yet found?

If your testers work independently, and if your feature is not under continuous development (i.e. you’re not adding bugs), (and maybe a couple of other ifs) you can use a thing called the Lincoln Index.

It’s quite simple.

Assume that there are N total bugs (found and as-yet-unfound).
Tester a finds A bugs. A = PaN, where Pa is the probability of a finding a bug.
Similarly, tester b finds B bugs. B = PbN, by the same reasoning.

There will be some bugs found by both testers, call that number C. It is evident that C = PaPbN. (The probability that both find a bug is the product of the individual probabilities.)

Now:

AB / C = PaNPbN / PaPbN = PaPbN2 / PaPbN = N2 / N = N

So a simple calculation gives us an estimate for N, the total number of bugs.

Explaining Maths

Sunday, September 11th, 2011

Recently, I was talking to my Dad about fiddling about programming the iPad (which I haven’t got around to yet) but I did mention that I might have a go at something simple just to get my feet wet. Beyond Hello, World there are many simple small-to-medium-size projects of course, and I mentioned I might do something like a Mandelbrot set explorer.

What followed was a bit of a Wikipedia-esque delve into some Mathematics as I tried to explain what the Mandelbrot set is.

Of course, everyone knows what the Mandelbrot set is. It’s the iconic heart-shaped box of springs and wire that is the poster child of fractal art. And as any mathematically-inclined person knows, it’s a colouring of the complex plane. It’s easy for computers to calculate: you take a complex number c, and iterate the equation zn+1 = zn2 + c, starting with z0 = 0. If the result tends to infinity, that number is not in the Mandelbrot set, otherwise it is. Anything in the set is coloured black, and things on the edge get coloured according to how many iterations it takes to pin down their non-membership of the set.

Most of that last paragraph is of course in Martian for many people, so I started explaining complex numbers. Which necessitated a bit of maths history.

To start at the beginning, we have the natural numbers, aka the counting numbers. These are the numbers we all learned as small children, starting at 1 and counting arbitrarily high. The natural numbers are conventionally called ℕ.

Natural numbers are fine for addition, but you get to a problem with subtraction: if you take 5 from 3, you end up with a number that isn’t in ℕ. So the next obvious way to expand is to add the negative integers and 0. Now we have the integer line stretching to infinity in both directions, with 0 in the middle, and this set, the integers, is called ℤ. As you can understand, ℕ is a subset of ℤ.

So far so good. ℤ is closed under addition, subtraction, and multiplication, meaning that if you take any two numbers in ℤ and either add, subtract, or multiply them together, you get a third number also in ℤ. However, what if you divide? You get a fraction – potentially a non-integer! And of course that’s not in ℤ. So the next set is the set of rational numbers (because they are ratios), called ℚ. Once again, ℚ is a superset of ℤ (any integer can be thought of as a ratio of itself over one).

All good, and this was as far as anyone thought for a while. Then a bright spark in Ancient Greece discovered numbers that couldn’t be ratios, and by many accounts, this was quite upsetting to the Greek geometers. Nevertheless, it was true, so Mathematics had to account for the so-called irrational numbers as well as the rational numbers, and taken together these constitute the real numbers ℝ.

At this point there are many fascinating asides involving mathematical efforts to tame infinity and infinitesimality, which meant that basis of much of maths (eg. calculus) was worryingly unstable and not well understood for quite a while, at least until brains like Georg Cantor had a go at it. There is also an aside about transcendental numbers (like π) which are a subset of irrationals that cannot be the root of any polynomials.

Anyway, sweeping all this under the table and assuming that the real numbers ℝ are perfectly well-understood, there remains a final snag for our story. Taking square roots is undefined for negative numbers, which in mathematical terms means that ℝ was not closed under exponentiation. To fix this final problem, we come to the complex numbers ℂ, each of which has a real part and an imaginary part (which is expressed as a multiple of i, the square root of -1).

Because they have two parts, the complex numbers can be thought of as a two-dimensional space: an x-y graph space where x is the real axis and y is the imaginary axis. And this is the complex plane. So finally we’re back to the original explanation with enough context to understand it: the Mandelbrot set is simply a colouring of each value in the complex plane (with suitable limits in x [real] and y [imaginary] parts) according to whether it’s in the set or not, or how fast the iterative process can determine that. Because there are an infinite number of values in the plane, you can zoom in without limit, and the fractal nature of the set means you will discover finer and finer detail.

Maths is fun

Friday, April 1st, 2011

The other week, a colleague walked into my office and posed the following problem to me:

For all n where n is prime and n > 3, show that n² – 1 is divisible by 24.
Examples: 5² – 1 = 24; 7² -1 = 48; 11² – 1 = 120.

(If you’re interested, give it a go before looking at the solution. It doesn’t require any advanced Maths.)

First, what does it mean to be divisible by 24? Well, it means being divisible by 2, 2, 2, and 3 (the prime factorization of 24). So we have to find a factor of 3, and 3 factors of 2.

As any highschool mathematician knows, n² – 1 = (n + 1)(n – 1).

Since n is prime and n > 3, it must be odd. Which means that both (n + 1) and (n – 1) must be even (divisible by 2). Moreover, since they are consecutive multiples of 2, one of them must be divisible by 4, and the other by 2.

We also know that (n – 1), n, (n + 1) are three consecutive numbers, so one of them must be divisible by 3. Since n is prime and n > 3, it cannot be divisible by 3. So either (n – 1) or (n + 1) must be divisible by 3.

Which means that (n + 1)(n – 1) is divisible by 24. QED.

Approximating elliptical arcs with Bézier curves

Saturday, March 29th, 2008

In doing my modulation work with curves and ellipses, I extended the vecto function for drawing an ellipse to enable an oriented ellipse. Lately it occurred to me that this didn’t go far enough in terms of functionality, and I began wondering about how to draw part of an elliptical arc.

Vecto’s ellipse drawing function works by drawing the ellipse in quarters, with four cubic Bézier curves. Each curve’s control points are calculated according to the radii and kappa, the constant that is 4(√2 – 1)/3, as explained by G. Adam Stanislav. This works fine if you are drawing quarters, halves, or complete ellipses (or circles of course), but what I wanted was a function like this:

(defun approximate-elliptical-arc (cx cy a b theta eta1 eta2)
…)

With (cx, cy) being the centre, a and b being the radii, theta being the orientation, and eta1 and eta2 being the start and end angles specifying the arc. The return value would be a Bézier curve, or a list of curves, depending on the required accuracy.

So I did some research and found an interesting paper by Luc Maisonobe on approximating such elliptical arcs with lines, quadratic and cubic Bézier curves. The maths is straightforward, if rather heavy on the constants, and it was less than an hour’s work to code up the function. I now have functionality to draw arbitrary elliptical (or circular) arc segments.

The interesting thing is that this method of approximating ellipses is not the same as G. Adam Stanislav’s method: to put it another way, when I compute a quarter-circle arc with a single Bézier curve, the control points are not quite coincident with the kappa-method control points. The error in the circle approximation is still undetectable to the eye, but careful comparison of two large circles shows that the kappa-method one is slightly larger: the curves are slightly more “pushed out”.

G. Adam writes: “It is my contention that we get the closest to a real circle if we draw the one curve with properties already discussed, and with the center point of the curve lying at the same point the center point of the circumference of a true quadrant of a circle would lie.” I would be interested to know if he has a proof behind this contention, and/or an expression for the error in such a curve. The derivation of kappa is based around this idea that the midpoint of the curve should be coincident with the midpoint of the arc.

G. Adam’s method seems accurate. But the Maisonobe method can be used to subdivide the arc, obtaining successively closer approximations to the true arc by using multiple Bézier curves, and includes a method for calculating an upper bound on the error. This, together with the fact that it easily handles start and end angle specification of the arc, leads me to favour it.

A bit of Pythagoras

Saturday, March 15th, 2008

Given Pythagorean triples that satisfy the Diophantine equation:

a² + b² = c²

where a, b and c share no common factors, one of a and b must be odd, the other must be even, and c is always odd.
First, note that squares of even numbers are always divisible by 4. [Lemma 1]

(2n)² = 4n²

And squares of odd numbers are of the form (4n + 1). [Lemma 2]

(2n + 1)² = 4n² + 4n + 1
= 4n(n+1) + 1

If a and b are both even, it is trivial to see that a, b and c share the factor 2.

c² = (2n)² + (2k)²
= 4n² + 4k²
= 4(n² + k²)

By Lemma 1, c is even. Therefore the solution reduces to the more primitive form:

n² + k² = (c/2)²

Consider a and b both odd:

c² = (2n + 1)² + (2k + 1)²
= 4n² + 4n + 1 + 4k² + 4k + 1
= 4n² + 4n + 4k² + 4k + 2
= 2(2(n² + n + k² + k) + 1)

This (by Lemmas 1 & 2) is not a perfect square, so this cannot be a solution. In fact, in this case c must be irrational:

Let p = n² + n + k² + k
c = √2√(2p + 1)

2p + 1 cannot have 2 as a factor. And since √2 is irrational, so is c. Therefore one of a and b must be odd and the other even.

c² = (2n + 1)² + (2k)²
= 4n² + 4n + 1 + 4k²
= 4n² + 4n + 4k² + 1
= 4(n² + n + k²) + 1

And c is odd (Lemma 2). QED.

Even more on ellipses and splines

Saturday, March 15th, 2008

Honestly, they’re incredibly interesting. Anyway, I’ll skip straight to the pièce de résistance:

Ellipse Modulation VI

This is a 4-curve cubic Bézier spline modulated onto an ellipse. The ellipse [a=4, b=3] is at an angle of π/4. C1 continuity of the complete curve is preserved. The flickr set tells the story of how I got here.

This is around 450 lines of my naive lisp, including class definitions and test code. So Gary, this is your g-code challenge!

The lisp code is object oriented (oh, and so much nicer than C++’s so-called object orientation). I rewrote the earlier code now that I knew what I was doing, and I added lines and polylines to the mix too (see the flickr set) so I can easily modulate whatever edge I want. You’ll notice if you look closely at the earlier attempts that they had a bit of a problem with c1 continuity, which is now fixed with the new code.

In closing, thanks, Zach!

Ellipses & Splines again

Monday, March 10th, 2008

After some code cleanup and generalisation, I can now modulate whole splines onto ellipses and onto splines themselves. Here is my simple 4-bezier spline modulated onto an ellipse:
spline_on_ellipse
And onto itself:
spline_on_spline
Repeatedly modulating a spline onto itself while varying the frequency parameter leads to some interesting and fractal patterns. Nice.

Splines and modulation

Sunday, March 2nd, 2008

My efforts to equally subdivide a curve along its length have, in part, been leading to this. First, I extended the sampling to work with splines (made up of cubic Bézier curves with c1 continuity). This shot shows 4 curves put together to form a spline:
spline
Next, I wrote some code to modulate a curve onto another curve. Here’s a curve, and the same curve with another curve modulated onto it.

plain modulated