Gresham College Lectures
Gresham College Lectures
A History of the World in Four Algorithms - Sarah Hart
Use Left/Right to seek, Home/End to jump to start or end. Hold shift to jump forward or backward.
Algorithms are fundamental to the story of mathematics – they’ve been around for over four thousand years. A theorem may prove that a solution to a problem exists, but an algorithm gives you the directions to actually find it.
This lecture explores four key algorithms that have not just shaped pure mathematics, but have found unexpected applications in areas as diverse as nuclear physics, film-making, medicine, and music.
This lecture was recorded by Sarah Hart on October 15th 2026 at Binks Hall, St John's College, Durham University, Durham.
Sarah Hart was the first woman Professor of Geometry at Gresham College, and Acting Provost between March and October 2025. She is also Professor Emerita of Mathematics at Birkbeck, University of London.
Professor Hart studied at Oxford and Manchester, gaining her PhD in 2000. Postdoctoral research and teaching followed, including a prestigious Engineering and Physical Sciences Research Council Fellowship, before she was appointed to a lectureship at Birkbeck in 2004. She became Professor of Mathematics there in 2013, and served in various management roles including as Head of Mathematics and Statistics, Assistant Dean, and Programme Director for the MSc Mathematics.
Her academic publications have been mainly in the area of pure mathematics known as group theory, which has many applications both inside and outside of mathematics, for example in coding theory and cryptography. She is actively involved in the British Society for the History of Mathematics, and has served a three-year term as President of the Society from 2021-2023.
The transcript of the lecture is available from the Gresham College website: https://www.gresham.ac.uk/watch-now/galileos-journey-underworld-case-interdisciplinary-thinking
Gresham College has offered free public lectures for over 400 years, thanks to the generosity of our supporters. There are currently over 2,500 lectures free to access. We believe that everyone should have the opportunity to learn from some of the greatest minds. To support Gresham College's mission, please consider making a donation: https://www.gresham.ac.uk/get-involved/support-us/make-donation/donate-today
Website: https://gresham.ac.uk
X: https://x.com/GreshamCollege
Facebook: https://facebook.com/greshamcollege
Instagram: https://instagram.com/greshamcollege
Bluesky: https://bsky.app/profile/greshamcollege.bsky.social
TikTok: https://www.tiktok.com/@greshamcollege
Support Us: https://www.gresham.ac.uk/get-involved/support-us/make-donation/donate-today
My name's Jolly Mitchell. I'm the principal of St. John's College, and it's really great to see each of you here. And I'll just tell you a few things about Professor Hart, apart from being a fellow of Gresham College, she was also the proverb there. She was the Gresham Professor of Geometry from 2020 to 24, and she was the first woman to hold this chair since its creation in 1597. Sarah.
SPEAKER_01Thank you. So thank you very much, Julian, for the introduction. Thank you all for coming. Algorithms are fundamental to the story of mathematics. A theorem may prove that the solution to a problem exists, but it's the algorithm that is a mathematical recipe to actually take you there and find the solution. So I'm going to show you four algorithms today that span the history of mathematics from the ancient world to today. And we're going to trace their impact not just within mathematics but beyond in places as diverse as filmmaking, medicine, particle physics, and music. So to Babylon. This is where we begin our story. And it's when mathematics is really at its beginnings, and we see clay tablets that have mathematics written on them, and this is all kinds of calculations and problems to solve, and the first algorithms. So they really are starting with mathematics. They've been there right from the beginning. So that the tablet that I'm showing you, is it a tablet? Is it a prism? This thing that I'm showing you is from the ancient city of Lhasa, which is in what's now Iraq. And on that tablet, one of the things is a problem. It's about finding the dimensions of a rectangle. And there's an algorithm which we'll see for solving this problem. So here is the problem. It's kind of you know translated obviously into English. To the area of this rectangle, which we don't know, I added the length and then subtracted the width. And the result was 183. Um we're also told I added the length and width together, the result was 27. Required. Length, width, and area. Okay, so we can think about how we might do this now. We've got these two pieces of information, we've got two unknowns, right? The length and the width, which if we find them, we can multiply to make the area. So how could we solve this problem? Well, here's the information summarized for us, just to remind us, this mystery rectangle. Well, this tablet, the ancient tablet, gives us a procedure to follow, an algorithm to follow. Now it doesn't say let x equal this, let y equals that, we're a long way pre anything like algebra. But it gives you this procedure with those two numbers and says you do this, you do this, you do this. I can talk you through it briefly, and this is the Babylonian method for solving that problem. Okay, so step one, you take your 183 and you add your 27, and you get, in this case, 210. And then there are lots more steps. We'll go. I'm not expecting you to memorize this algorithm, by the way. There will not be a test. Um have to admit, this is not an algorithm we still use today. But it's you know, it's really interesting. This is the first perhaps the oldest algorithm, one of the oldest algorithms we we know about. Okay, so the next step is you take that 27, you add two to it. Okay, you get some number, which you then halve. None of this is explained, right? You just hit do this sequence of steps. Um we hopefully don't teach mathematics like this nowadays. Um you've halved this thing, now you square it, still none the wiser as to why, then you take away that 210 you found a while ago, you get another number, 0.25, um, then you square root that, and then magically the length, the width, and the area are given to you, right, by adding various things and subtracting others. Um so this it's an algorithm, though. So what I wanted to show you, this is an algorithm. It qualifies why? Because what is an algorithm? It is a finite sequence of steps which are executable, unambiguous steps that terminates, you get to the end, and you get an output, and that output is hopefully the solution to your problem. Now, it's not explained, you know, on this tablet why this works or why we're doing what we're doing. We just get the steps and we follow the steps and we get to the answer. But this is an algorithm. It's a very early algorithm. And I was thinking about, you know, if you look at those numbers that are there, it feels, I mean, it's clearly not random because you can check that this is a valid solution. Um, these numbers that you get at the end work, um, give you a rectangle which has the properties described. But it it can they feel a bit like they're coming from nowhere. I was thinking, if I was solving this problem now, well, the first thing I'd do, because I'm a modern mathematician, is I'd I'd get some X's and Y's in there. I mean, then you feel like you're on safe ground. So we're now we can relax. Um the length, let's say the length is x, the width is y, right? And now we can convert those words into some friendly soothing equations. The area is x, y. Then we add the length, x, take away y, the width, and we get 183. Right? And I convert length plus width equals 27. Well, I can convert that now into x plus y equals 27. And now we feel like we're on safer ground. We can now solve. We've got two equations in two unknowns. Um, maybe I'll eliminate y from the first equation by I know y equals 27 minus x, right? We might do that. And then substitute it in. Fiddle around, do some algebra. Quadratic equation. Hazar! We know how to solve quadratic equations. We've all learned this in school. But look at the coefficients. 29, 210. Those are the first two numbers that came out of the Babylonian algorithm. So they weren't just flailing, there was method in their madness. These numbers actually arise in what we now would think of as the natural quadratic equation that we might want to solve here. And there are lots of ways now of solving quadratic equations. My favorite is completing the square because it feels more instinctive than just bugging numbers in a formula. If you do that, again you start seeing more numbers from the algorithm cropping up. They're all there. So what's what this algorithm is doing essentially is solving a quadratic equation without admitting it. And that's there's a good reason for that, because the concept of a quadratic equation was not, they say I'm being very anachronistic, talking in this way. So you can solve this quadratic equation, and okay, you get two possible solutions. The Babylonian method only gives you one of those solutions. And there are kind of historical reasons for that, like being a bit suspicious of negative numbers at that point. I mean, this is millennia before we have the concept of a symbol for zero. You know, there's all sorts of reasons going on why this 4,000-year-old algorithm gives us one solution, and it's kind of the solution they were thinking of. Implicit in their writing is that the length is always bigger than the width. Okay, so for reasons like that, there's only one valid solution to the problem as they would have conceived it. Um, but we can solve a quadratic and get and get two solutions if we like, because after all, it's 4,000 years later. Um we've learnt a lot since then. So that's I wanted to show you this algorithm, not because we use it now, we definitely do not still use this algorithm, but because it shows right from the beginnings, the earliest mathematics that we can find records of, there are algorithms being used. But if you want an algorithm that is still in common use, well, we have to come a bit forward in time. On the way, let's just remind ourselves that actually mathematicians trying to solve equations is something that's kept us going for a very long time. And it took many thousands of years for us to have worked out really ways to solve any old quadratic equation. And um, one of the people involved in that journey was a mathematician called Al-Khwarismi, uh, who wrote the compendious book of calculation by restoration and balance. It's the English translation of the Arabic title, which I put here. And I wanted to mention this because he does, there are lots of diagrams in his work writing in Arabic. There's completing the square, sort of happening, there's the square that we're completing, right? Um, so he developed lots of processes, algorithms for doing what we now call algebra because of him. That's one of the words from the title, um, means restoration, which is kind of um adding the same thing to the same to each half side of the equation. Again, this isn't how he would have phrased it. Balancing is like gathering like terms. So we get the word algebra from him, but we also get the word algorithm from him. Alcharismi, so the methods of doing this algebra, um, are known as now as, well, things done by Alcharismi which became morphed into the word algorithm. So the word algorithm comes from someone, a mathematician, doing algebra in the way that we the sort of way that we describe. Okay, but if we want the oldest algorithm in continuous use, it is widely believed to be something called the Euclidean algorithm. And as the name suggests, it goes back to ancient Greece. Um Euclid. And it is an algorithm for calculating greatest common divisors, which, depending on when you went to school, may have been called highest common factors, it's the same thing. Why would you care about doing that? Well, it's because of calculations like this one. Um if you have a fraction like 51 over 85, as we know, it's illegal not to simplify that to its lowest terms. You have to do that. So um so to do that, okay, you can factorize top and the bottom, 51 is 317s, 85 is 517s, then you can. So 17 is the greatest common divisor of the top and the bottom, so you cancel that, and you get three-fifths, and you're done. Easy if you can factorize your two numbers. A bigger, a bigger fraction like this, not so easy to simply cancel, because you can't tell what the greatest common divisor of these pair of numbers is on site, and it's quite hard, in fact, notoriously it's very hard to factorize big numbers. So here's a clever little trick that's the basis of the algorithm I'm gonna show you. Um, if anything divides both of those numbers, say D, then it divides the difference between them. In fact, it divides any combination of those numbers, like three times the first one plus seven times the second one. Um, anything that divides both of those is gonna divide any combo, including this difference. And that's useful because it does a great thing, it makes this problem into a smaller problem. Because now, instead of working out the greatest common divisor of two big numbers, we could swap out the biggest number with this smaller 34, the difference between them. And anything that divides any pair of those must divide any other pair of those. And this is the basis of the algorithm. It goes like this. If you want to find the greatest common divisor of two numbers, like five and thirteen, I know we all already know what the answer is to this, um, then but this is a toy example. What you do is you write 13 as, well, you divide 13 by 5. Um, it's twice five plus a remainder of three. And you can say by what we've just said that anything that divides both 13 and 5 is also a divisor of that smaller pair, 5 and 3, the remainder. And okay, even if we don't know the answer to that yet, maybe we don't, we can repeat this idea. We can do another division, this time with 5 and 3. 5 is 1 lot of 3 and a remainder of 2. And then we can keep going. Take this the 3 now and this new smaller number, the remainder. Do it again. 3 is one lot of 2 and a remainder of 1. Do it again. 2 is 2 lots of 1. Ooh, now the remainder is zero. If you've got no remainder, that means you've got a number that one number divides the other. In this case, well, one divides everything. I mean, we could actually have stopped when we got to one, because it's pretty clear that if one is one of your numbers, well, the only thing that divides one is one. I'm talking about positive integers here, I should say. Um, so yeah, we could have stopped there, but but you can definitely stop when you get a remainder of zero. And you can follow that trail all the way down, and your greatest common divisor is the last non-zero remainder in this process. So it's a finite set of steps. Why is it finite? Because the remainder has to decrease every stage, because the remainder is always smaller than the number you're dividing by. So it always goes down, so eventually you're going to get to zero. And you so it's going to stop, it's an algorithm. It's not very fast for these pair of numbers in the sense that we already could tell they were co-prime. We knew the answer. But it has very, very great benefits when the numbers get big. Um, in fact, another distinction for this algorithm, it's the first one we know of that anyone subjected to some kind of complexity analysis. In other words, what's the runtime? Like how efficient is this thing? Um, those words were not being used at that time, but uh in the 19th century, mid-19th century, this very dapper French mathematician, Gabriel Lamey, looked at the Euclidean algorithm and showed that in terms of efficiency, it's pretty good. The number of steps it takes, of these like dividing and remainders, is at most five times the number of digits in the smaller number of the pair. So if you've got, say, 89 and 144, 89 is a two-digit number, so times five, it it's gonna be done in at most ten steps. Again, that doesn't look so impressive for two-digit numbers, but for seven-digit numbers, like you know, the low millions, seven digits, that's gonna take five times seven at most 35 steps. And that is way, way, way, way better than the alternative, which is factorizing both your numbers and looking for common factors. Because um, if you want to find the the factors of a number and you don't have any better way of doing it, well, you just have to sort of go through is it divisible by two, by three, by five, and check, and you may have to go up to the square root of the number until you either find no prime factors, so it's prime, or you find a prime factor. So that could take potentially a thousand steps. So that's huge time saving for the Euclidean algorithm, this 2,000-year-old algorithm, still using it in mathematics constantly, everywhere in mathematics and elsewhere, as I'll I'll mention shortly. Um, Lamey also did a calculation of well, that's that's an upper bound, right? That's at most five, at most ten steps, at most this number of steps. What's the what are the worst-case scenarios here? So he managed to prove this really cool connection between the Euclidean algorithm and Fibonacci numbers. Very nice. He proved that the smallest pair of numbers for which you genuinely do need n steps is when you're looking at the n plus first and n plus second Fibonacci numbers. So the smallest pair where we really do need 10 steps, that would be the 11th and 12th Fibonacci numbers, which are 89 and 144. Almost as if I chose that example on purpose. Um so this we're seeing the beginnings of this idea of, yeah, algorithm, we've got an algorithm, but we also want to understand how efficient it is, and maybe can we improve it? Euclidean algorithm is incredibly efficient, as I say, still in use across mathematics. Um, and also beyond it. So I want to give you um a variant of this algorithm, which has found a use in particle physics. So this is it's called uh Bjorkkland's method, Eric Bjorkland, a mathematician, uh applied mathematician, and he was studying the problem of okay, if you're doing uh physics and you've got particles that you want to fire into a nuclear reactor, which is potentially a little bit dangerous if you don't get it right. In particular, maybe you want to inject um a certain number of pulses of energy or like high velocity particles in a certain number of time periods, and maybe it's you want to fill some of the time slots with these energy bursts, um, and you don't want to clump them all together, because clumping together concentrations of energy inside a nuclear reactor historically hasn't always gone very well, so let's not do that. We want to space them as evenly as we can. For example, let's say the numbers are going to be bigger than this in practice, but let's stick with our five and thirteen. Maybe you want five pulses out of 13 time slots. There are your 13 time slots. Five of those want to be pulses of energy. So you do something a bit like the Euclidean algorithm. So if we're doing 13, we divide by five, you get two lots of five and a remainder of three. Um, so I don't really care how many things are in my piles at this point, I've got five big piles and three little piles. So now I've got into sort of the five and three step, like I had before. Five divided by three is one lot of three, remainder of two. Do it again. Three divided by two, one lot of two, remainder of one. We can stop when we have a remainder of one, as we said before, because we kind of know the outcome. So at this point, how has this helped us with our pulses of energy? Well, secretly all along, at the beginning, I I coloured those first five dots separately. They're going to be my energy pulses. And then we do this whole process, and you didn't know I was secretly doing it because I'm just uncovering it now. Um, but then at the bottom, that final step, you read down the columns, and that gives you a pattern. And this is the pattern that the Bjorkland's method with the Euclidean algorithm gives you. And it can be shown, mathematically, that this is optimal in terms of even distribution. You can't have exactly equal gaps because five does not go into 13 exactly. But the distribution of these energy pulses is as even as it is possible to get. So that's good, we've got to solve the problem in physics. Um, but there's another place in life where we get patterns like this, where you're sort of stronger and weaker. And it's in music, in rhythms. We might have a rhythm of a certain number of beats, and some of those beats are stressed. And another mathematician called Godfrey Toussaint was wondering if the rhythms that would be predicted by this Euclidean algorithm cropped up or would occur in music that we produce. Like, do they predict the kinds of rhythm that we like in music? So, for instance, okay, you can work out using this algorithm, um, predict a rhythm that it that has three stressed beats out of eight. I've written it here, and we could count it as one, two, three, one, two, three, one, two, one, two, three, one, two, three, one, two, something like that. Um, would that occur in music? And well, yes, it does. Uh, it's in fact one of the most popular rhythms in all of world music, specifically, well, particularly in Latin music, uh in lots of African folk music, and all over, it's all over pop music. I'm gonna play you a snatch of music just now, and you can see if you can hear it. See, see if you can count that one, two, three, one, two, three, one, two. One, two, three, one, two, three, one, two, one, two, three, one, two, three, one, two. You can hear it, and once you have identified that pattern, you will hear it everywhere. I you know, I don't know if I apologize. I'm just saying it'll happen. Um if you now you have to be able to count very, very quickly for this next one, um, which is a song that's so popular it's it's been downloaded, I think, five billion times on streaming services. So you I'm pretty sure you'll recognise it, but let's see if we can count very quickly and spot the same rhythm but faster. One, two, three, one, two, three, one, two, one, two, three, one, two, three, one, two, one, two, three,
unknownone two
SPEAKER_01three, one, two, one, two, three, one, two, three, one, two. Okay. Oh, irrational. Um I guess. Um yes. So this the the Euclidean rhythms that are predicted by this algorithm have have been found in music from all musical traditions across the world. And, you know, it's just fascinating how we as humans seem to select those rhythms that have this even distribution that are predicted by the Euclidean algorithm. So that's very nice. Um we're gonna move on to our next to our next uh algorithm, number three. And this is an algorithm which is I mean it's very important, but it's only important because computers exist. That's because the benefits that that that it brings, a bit like the Euclidean algorithm, only really start to come into play when the numbers involved are very large. So the background for this algorithm is in. Which is called the Far-Furrier transform, and we'll get to what all of those words mean. It's in, if you're trying to understand sounds, that's one of the places where you might encounter the things we're going to talk about. So here is some sound happening. It's some music, we don't know what it is. But the basic shape of this is, you know, time is passing from the left to the right, and then you've got the strength of the signal is being shown in the vertical axis. Now, sound, what is it? It's vibrations in the air. If those vibrations repeat regularly, then that gives you a frequency. A frequency defines a pitch, and that's musical notes. So what we find in this is a big stretch of time, but if you pin this down or focus in on a very small, like few microseconds, what you find is this regular repeating periodic function. That's what makes up music. And if we want to record music, reproduce it, understand it, synthesize it, we need to understand these kinds of periodic repeating, repeating, repeating functions. And fortunately for us, a mathematician called Joseph Furrier in the early 19th century managed to show that essentially all periodic functions, that word essentially is covering me for any mathematicians in the audience who know the exact theorem, essentially all periodic functions can be broken up into their constituent parts, and those constituent parts are sine waves. So this one, here are the sine waves that make it up. You've got one that's sort of one whole wave in the period, and then you've got one that's twice the frequency, so two sine waves in that time period, and then is that the next one a three? But it might be shifted a bit, so it's really a cause rather than a sign. But they're all the same shape. Okay, this is great that it can be done. But this, you know, a one that says this can be done is like me saying, Um, you know, I'm a brilliant chemist because I'm telling you that everything in the world is made up of chemical elements. Um, if you want to synthesize something, you need to know what the elements are and how much of each there is. So what what we know from you know theorem is yes, any periodic function, repeating one like this, can be written as a sum of lots of signs and causes of different frequencies. That's nice. I mean it's brilliant that that's true, but unless you know how to find those coefficients, not very much help in practical terms. So, how do you find the coefficients? Well, I mean, that's like a few weeks of university level mathematics, so I'm not going to go into huge detail, but I will indicate to you. Um, here's the kind of thing we want to understand. So here's a graph, here we've got two sine waves. And one of them, um, so in that stretch of space, we the the smallest frequency we could get is like one whole sine wave. In that, that would be sine of t in that example. So then we've got two sine waves, the frequency is doubled, it's sine two t. And then there's three sine waves squished into that space, that's a higher frequency. If we want to understand how much, for example, of the sine 2t there is in our function that's made up of sine waves of some frequencies we don't know, what we might do, and this seems to work, is we multiply our function by this sine 2t. Now, why would that help? Well, if you multiply, if you do this multiplication, then sine 2t is kind of emphasized. Every time it's positive, you get a positive times a positive, which is still a positive number. Every time it's negative, well, if you're multiplying by itself, two minuses make a plus. So those negative times where it's below the axis, they turn into um positive parts in the product. So when you multiply it by itself, you get a graph where lots of positive area, like this. If you worked out the area of that graph on the right, it's gonna be a positive number bigger than zero. Whereas this other one, if you multiply sine 2t now by sine 3t, those are sort of out of phase with each other. So sometimes they're both positive, sometimes they're both negative, but quite often, in fact, exactly half the time, um, one's positive and one's negative. So when you work out the area under this product graph in that case, it turns out all of the positive bits cancel out with the negative bits, and so the net effect is it's zero. So making this product gets rid of everything except the frequency you're interested in, and therefore you can pull out the coefficient that you need and add in a bit of technical stuff. So that's the basic idea. You find these coefficients by multiplying by all these frequencies of sine wave, in turn and doing some calculations. Now that's all great, except there's a problem. The problem is when you are actually trying to understand a signal in real life, you don't know what the function exactly is. All you know is you've sampled it in a few points. Maybe lots of points, maybe thousands, but you've got a bunch of values that you've measured, you don't know what's underneath that. You haven't got a nice y equals x squared function to do all these calculations with. You have to infer that from a finite amount of information. So you've turned a continuous problem into a discrete problem. So your problem now is to try and solve this thing called the discrete Fourier transform. Um you do this very basic thing. At each place you've measured your function, you have to multiply it by all possible uh frequencies. Um actually, only the first, the the same number of frequencies as the number of sample points, and that's because if you've got very high frequency things, you kind of can't spot them. This is very unscientific, they kind of can fit between the gaps. And so you can't you can't detect them. Like theoretically, even there's no way to detect them from if you've got eight sample points, you're not going to suddenly detect a tiny meany squiggle between two of them. So you have to sample it enough so that the human ear can't detect any potential missing frequencies. That's okay. Lots of samples will do this. So you've got n data points, which you have to test against n possible frequencies. And that's kind of n squared calculations, right? Roughly. Um that doesn't that's not too bad if you have a small number of data points, eight, you need six to four calculations. Things with squaring is it gets bigger. Um, so if you have a thousand points, that's a million calculations. Um, and if you use the standard for something like recording music for a CD in the olden days, um that would be 44,100 samples per second, which is about two billion calculations. That's not feasible, that's too many. So we need we need a solution to this. And the solution is a brilliant one. It's called the fast Fourier transform because it's you know fast, and it exploits the symmetry of the sine curve. And uh so here's what I mean. Suppose you've you've you're taking eight sample points equally distributed, so you divide your your period um that you're looking at into eight and measure each of those points. Here's a sine curve, that's like the the basic frequency. Let's say this is one second, this is one hertz. Um, what about three hertz? Um if you want to, you you're gonna need to look at that as well. There's a good thing. At that first sample point, those two curves have the same value. So you don't need to do that calculation twice, you've saved some time. And if you look at the five hertz version and the seven hertz version, they also coincide at that place. So you can save yourself even more work. And if you join all the other curves you need to draw, you can see there's loads of places where they overlap. So it's in that middle point, all of these have the same value. So it saves you having to do like eight different calculations. You can reduce it a great deal. In fact, you can reduce from n squared, the False-Fourier transform reduces your amount of calculations to n log n. If you don't know what log n is, that's okay. Here's some examples of how much of a saving that is. That 44,100, instead of two billion calculations required, the Fulfill-Fourier transform gets it down to 680,000, which is still a lot, but it's it's a 97% improvement. It makes it possible. So anything like streaming um algorithms, uh, compression algorithms, um, recording, synthesizing, all of these things are possible because of the Farse Fourier transform, bringing the number of calculations down to something that's feasible. So it's a really powerful and very important algorithm. It is important because we have computers that can do 680,000 calculations a second. This is not, you know, human beings doing this is not feasible, but computers can do it. And so this is an algorithm that is important because of computers existing. Um, so before we go to our final algorithm, just shout out for Ada Lovelace because the very first computer program, before either of those words actually meant what it does now, was written by Ada Lovelace and it was an algorithm. It's an algorithm for calculating something called Bernoulli numbers for Charles Babbage's not actually built eventually analytical engine. And this is a computer program. Um, but it's an algorithm. And most computer programs are algorithms, not all, because as I mentioned, not all computer programs terminate until you make them terminate. Um, but most computer programs are algorithms. And there's actually another layer of algorithm in the process of programming, and that is there's an often an intermediate stage where you program in a high-level language that is understandable to humans, like C, and then a compiler translates that into the machine's native language, machine code or assembler or something like this. Um, compilers began to um be around in the early 1950s, and the earliest, or one of the earliest, was created by Grace Hopper here in her team. So this is her in 1957, sitting next to a very small, convenient, compact computer. Uh and these compilers, so they themselves are algorithms that turn high-level code into low-level code. So the message here is even the algorithms are made of algorithms, right? It's algorithms all the way down. And we they are fundamental to us. They've always been fundamental to maths, but they are fundamental to us, all of us, in everyday lives, because that's what computers are made of. So our final algorithm comes from this guy. Or at least he he kicked off the algorithm. This is Stanislav Ulam. This is his identity photograph for Los Alamos, where he was working in the war. His next door neighbor was another mathematician called John von Neumann. So, you know, that's quite a team to have a little chat over the garden fence. Um he was on one occasion, he'd been very unwell. He was recuperating, passing the time by playing games of patience, card games. Um he was playing a variant he called Canfield, but when I grew up, I I would call this game demon. Um it's quite hard to get out. Um but and he got to wondering, he's a mathematician, he can't help himself, hmm, I wonder what the probability is of winning a game of Canfield. So he got to thinking, now it is impossible to play every possible game of Canfield and then count how many you've won. Because the number of different shuffles of a pack of cards is a vast number greater than the number of atoms in the known universe. Like you can't you can't do this by brute force. But he thought, okay, how about we could do sampling? We could play a hundred random games and see how many of those we won, and that gives us an estimate for the answer. So using randomness to give an estimate for your for your solution to your problem. Hence, the name of this approach, um, which he then wanted to formally develop with John von Neumann, is the Monte Carlo method, because you know you're kind of gambling. Um but it's a really, really effective approach, especially when you have a situation like this where in theory you know how you could work out the answer, but it's just not computationally feasible. So you take a random sample and that's how you how you get your estimate. Um but he's actually not the first person to have employed this sort of experimental method, um, using randomization to work out or estimate a mathematical quantity. That honor probably goes to this guy, who was he's the Count de Buffon, a uh 18th century French aristocrat. If you've heard of him, it's probably because you've heard of a puzzle called Buffon's needle. Here's the puzzle: you have a floorboard, um, a floor with parallel floorboards like this, and you drop a needle onto it, and what's the probability of it that needle will land in a way that crosses two floorboards? So, you know, homework, you can work, you can see if I'm right about this. I claim the probability is, now it's a small item, two l over pi w. L is the length of the needle, w is the width of a floorboard. Okay, you can you can test that if you don't believe me. Um so if say your needle was half the width of the floorboard, so then two l equals w, then the probability would be one over pi. So that's the answer to the question, great, but it gives you a way if you want. You can use this to estimate pi experimentally. What you do is you chuck a load of needles on the floor, warning any housemates that you want to do this, a load of needles on the floor, and you work out what proportion of them cross over a floorboard. Um, that's your estimate for one over pi, right? So if a third of them cross the floorboard, then that gives you that pi is about three. Okay, fine. We can do we you know we have deterministic ways of finding pi. Um you'll read on the internet that that Buffon did this. Um you'll also read in uh in other bits of the internet that he, in fact, he didn't throw needles, he threw baguettes onto the floor. Garage pie that way. Um this guy, this is the 1780s. Like, this is the let them eat cake era. I don't think that's a safe thing for an aristocrat to do. Luckily, he didn't do this. Um, the reason people say this is because their French isn't very good. The original program the problem that he posed said, onto my floor, I throw unbaguette. Like that just means stick. Okay, so you will read this. It isn't true. However, Buffon did do experiments where in particular we know he experimented with a certain game which involved tossing coins, um, and he he experimented by actually playing this game many, many hundreds of times to see what the probabilities would be. So he did do some experiments to estimate the solutions to problems, but not with baguettes. Um, okay, so the Monte Carlo method then, it the idea is you use randomness to solve problems that are too hard to solve in any other way. And there are two uh applications of this, it had so many applications, the Monte Carlo method, in all areas of mathematics and beyond. I'm gonna talk about just a couple of them briefly to finish up. So the first is say you're making a film, it's it's gonna be an amazing film, and into this scene, which you filmed a real life scene, you know, light streaming into a room, suddenly a mysterious alien orb appears. Very convincing. Only it it isn't though, right? It's not convincing because I've just clearly put a circle on top of that photograph. Now, what would I need to do to make it convincing? Um, is well, I'd need to understand how that object would interact with, for example, the light sources in that room. Because some of it would be in shadow and some of it wouldn't. How am I going to do that? Well, so what you can do is you can sort of set up a virtual situation, a simulation. We're looking down now onto the room, we've got the light coming in from the window, and all of the rays are coming in. We know how light behaves, we've all done a bit of optics, right? So the light comes in, it goes in straight lines, and it hits things. Um there's your virtual camera recording, so you can make your picture and insert the relevant pixels into the right places. That would be a very inefficient way to do this, though, because almost none of these rays coming in the window actually interact in any way with that object. So instead, what you do is you kind of work out which ones you're interested in by doing it in reverse. So it's called ray tracing. You send virtual rays from your virtual camera and then you know to to the object. So you already, you know, nothing is is is wasted here, only the ones that go to the object, and then you draw what are called shadow rays to the light source. If they're not impeded and they get to the light source, then the relevant pixel is light. If they're blocked, the relevant pixel is dark. Easy peasy. Only life isn't like that. Life is more complicated than that. Um so here's where the Monte Carlo process of simulations come in. The first way is, well, there are many ways, but one way is light sources are not points. So here, if we just got, you know, this is the pixels we're colouring in, the path to the light source is clear for some of them, so they're fully 100% bright, and then other ones, the path is blocked 100%, you know, 0% bright. It's it's you know, one thing or the other. That's not what life is like. So instead, what you do, um, you can't, you haven't got the computational power to, for every pixel, draw a million rays and see what's going on. So you do a simulation in which you send a random um rays randomly like maybe 50 rays to random points on the light source, and then if, say, 80% of them reach that light source, then the pixel is 80% bright. And you get something much more nuanced like this, a much more realistic shadowy effect. The other kind of thing that happens is um in real life, things aren't perfectly reflective, and it's it's worse than that, it's not even some percentage of the light gets reflected. The angle of reflection is not guaranteed to equal the angle of incidence in the sense that microscopically on the surface, even a flat thing that looks flat is going to have little imperfections. So the light might not quite bounce off where you thought it would. So the answer to that is you do another Monte Carlo simulation where you have a little cone around the theoretical line of reflection, and you send, you pick random directions within that cone, maybe again 50 of them, send the light off along those, and then you sort of average out the brightness that is encountered from those. Again, it gives you more nuance and subtlety. You do the same thing with refraction if that's relevant. And the net effect is you can produce amazing images like this, which uh um I I found um to describe this molecule, or it's a couple of molecules that kind of it's all simulated, all on a computer, but like glass molecules, it's very beautiful, lots of shadows, reflections, refractions. And this is done using Monte Carlo simulations. The other uh application I want to mention to you is a really important one, and that's in medical imaging. So, what we've got here is we've got um two scans of a human body, like through the pelvis. The kind of the the black and white, well the grey one, monochrome parts are from a CT scan. CT scans are great at detecting uh bone, differentiating bone from from other tissue and things like this. They're not good at differentiating healthy tissue from cancerous tissue. So on the right, what you've got there superimposed is a PET scan. PET scans produce these hot spots where there are areas that are maybe cancerous. And they do that by you inject a uh a modified glucose molecule. Um, glucose is uptaken, uptaken, is that a word? Taken up disproportionately much by um cancerous cells because they need the energy for growth, so you sort of greedily grab it all. But in this case, the glucose has been modified to include a radioactive isotope, fluorine 18, and so that's what's being detected. Um let me give you just a tiny bit more information, mini chemistry lesson. What's happening here? So PET, that's positron emission tomography, that's what it stands for. So where's the positron? It's because what's happening is your fluorine 18, um, that's unstable, it's kind of too many protons for the number of neutrons it has. So one of the protons decays, and so you end up with oxygen 18, um, but that proton decays to form a neutron, so the positive charge has to go somewhere and it becomes a positron, just like an anti-electron. Okay, so the positron zooms off, and it pretty soon it'll bump into an electron, and when that happens, they annihilate, and two high energy photons zoom off in opposite directions, and that is what we're detecting. So we're detecting um the photons that are emitted when the positron decays. Okay, fine. Um, all very nice, but then what how do we get from a photon to that beautiful image that tells us so much with all the hotspots? Um, well, this is. Scanner, the PET scanner, it's a cylinder, and all around that the that cylinder there are detectors, and they're looking for these photons. Um, but there are some issues. See, you can only detect that a positron has annihilated by detecting a pair of photons. So that image on the right, that's great, we've detected the pair of photons. But things can get in the way in a real-life machine. For example, a real-life physical machine has all these detectors, but detectors have edges and tiny gaps. So maybe one of the photons escapes and we miss it. Or, as in the picture in the middle, maybe they both hit a detector, but there's a microscopic flaw in one of the detectors, so we don't pick up the photon. So what it is done before the machine is ever used is that Monte Carlo simulations are run of trillions, trillions of virtual photon pairs, looking at how many of them are detected in each different position and direction within that space, so that you kind of you can counter any slight biases that may arise just in the natural physical design of this machine. That is, no machine can be perfect this way. So trillions of virtual photons, simulations are done, Monte Carlo methods, to explore this. Okay. That's one way they're used. Next thing is, okay, you're gonna the machine's installed, you're gonna have a scan, it detects a pair of photons, so somewhere on the line between them is the hotspot, right? So somewhere, well, okay, you lots of these photon pairs are detected, and then you kind of triangulate. In theory. There's a problem, again, with the real world not being lovely and theoretical. We're not in a vacuum. Inside the scanner is a human body. Human bodies have stuff inside them. Every human body is different, the distribution of bone and and muscle and all of those things vary from person to person. And the problem with matter existing is that your positron, when it makes these photons, they zoom off. Sometimes they bump into something. They bump into an atom, get diverted. It's called Compton scattering. So the inferred line of that we want to understand whether where our positron have been is wrong. So there are uh Monte Carlo simulation is done for your specific body. They do a CT scan of your body and they do a simulation for that to try and minimize this the noise created by this Compton scattering at the same time as they're doing the PET scan, which is like incredible. So again, billions of virtual photons. The final thing that can happen is that really we wanted to take the positron, because that's where the radioactive material is, but unfortunately, we're not detecting that. In fact, we're detecting where it got destroyed. That's where the photons are created. So that range, the positron, can travel a bit before it bumps into an electron, and that range, positron range, can then blur where we think the tumor is, and we don't want that. So again, more simulations are used, Monte Carlo simulations, with different kinds of um material like bone and blood and so on, that tells you how far positrons usually travel in those kinds of matter, and that again helps to de-blur the image. So Monte Carlo methods in medicine have made PET scans much more accurate, much more able to detect things early, allow the medical team to focus much more precisely on the area that needs to be targeted, and so have saved thousands of lives. And I mean at this point, we're at the end of our tour. Um, I've tried to pick four algorithms that show us how they've been intertwined with mathematics from its very beginnings. Um, and they've always been part of mathematics, and you know, whatever the future holds, they always will be. So thank you very much. We'll stop there.