# Computing: The Science of Nearly Everything

Computer Science…Research, Education and Policy

## Primes

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length…Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated.

Disquisitiones Arithmeticae (1801)
Carl Friedrich Gauss (1777-1855)

Written by Tom

21 October 2012 at 9:53 pm

Posted in Mathematics

## Fractal food

Big whorls have little whorls
That feed on their velocity,
And little whorls have lesser whorls
And so on to viscosity.

Written by Tom

11 September 2012 at 7:50 pm

Posted in Mathematics, Science

## Life is a trap for logicians

The real trouble with this world of ours is not that it is an unreasonable world, nor even that it is a reasonable one. The commonest kind of trouble is that it is nearly reasonable, but not quite.

Life is not an illogicality; yet it is a trap for logicians. It looks just a little more mathematical and regular than it is; its exactitude is obvious, but its inexactitude is hidden; its wildness lies in wait.

Chapter VI: The Paradoxes of Christianity, Orthodoxy (1908)
G. K. Chesterton (1874-1936)

Written by Tom

9 August 2012 at 1:39 pm

## 2012: The Alan Turing Centenary Year

with one comment

Written by Tom

23 June 2012 at 12:00 am

## A set of top Computer Science blogs

This started out as a list of top Computer Science blogs, but it more closely resembles a set: the order is irrelevant and there are no duplicate elements; membership of this set of blogs satisfies all of the following conditions:

1. they are written by computer scientists and focus on computer science research;
2. they are of consistently high quality;

N.B. I have deliberately excluded blogs primarily focusing on computer science education (for another time).

• The Endeavour by John D. Cook (@JohnDCook)

John’s blog cuts across using computing, programming and mathematics to solve real-world problems, pulling in his wide expertise as a mathematics professor, programmer, consultant, manager and statistician. Some great posts across the technical and socio-technical spectrum. Also runs a number of useful Twitter tip accounts, including @CompSciFact, @UnixToolTip, @RegexTip and @TeXtip.

• Serious Engineering by Anthony Finkelstein (@profserious)

Anthony is Dean of the Faculty of Engineering Sciences at UCL, having previously been the Head of the UCL Computer Science. His regular blog posts are an insightful and thought-provoking journey across computer science, engineering, research and academia.

• Computational Complexity by Lance Fortnow (@fortnow) and Bill Gasarch

Since 2002, the first major theoretical computer science blog; computational complexity and other fun stuff in mathematics and computer science.

• Daniel Lemire’s blog by Daniel Lemire (@lemire)

Daniel Lemire is a professor in the Cognitive Computer Science research group at LICEF in Canada, with his popular blog covering topics across his research areas (databases, data warehousing, information retrieval and recommender systems), as well as programming, education, economics and open science.

• Gödel’s Lost Letter and P=NP by Dick Lipton (@rjlipton) and Ken Regan

This is a blog on $\mathrm{P} = \mathrm{NP}$ and other questions in the theory of computing, named after the famous letter that Gödel wrote to von Neumann which essentially stated the $\mathrm{P} = \mathrm{NP}$ question decades before Cook and Karp. Defined by the authors as a personal view of the theory of computation, it talks about the “who” as much as the “what”.

• Editor’s Letters by Moshe Vardi (@vardi)

Moshe Vardi, a distinguished and award-winning theoretical computer scientist, has served as Editor-in-Chief of Communications of the ACM since 2008, discussing a wide range of topics across computer science, research and technology. Certainly worth following on Twitter too.

• Alan Winfield’s Web Log by Alan Winfield (@alan_winfield)

Alan is the Hewlett-Packard Professor of Electronic Engineering at UWE and his blog is mostly, but not exclusively, about robots. It also touches upon artificial intelligence, artificial culture, ethics and biology, highlighting his definition of robotics as both engineering and experimental philosophy.

• Lambda the Ultimate, the Programming Languages Weblog (@lambda_ultimate)

This site deals with issues directly related to programming languages and programming language research, as well as forays to bordering issues such as programmability and language in general. This is a community, but not for specific programming problems in some language; unfounded generalisations about programming languages are usually frowned on.

• BLOG@CACM by Communications of the ACM (@blogCACM)

The Communications site publishes two types of blogs: the on-site BLOG@CACM expert blogs, as well as a blogroll of syndicated blogs, essentially covering the spectrum of computer science, research, education and technology. Something for everyone!

The latest news on Google research, focusing on some of their key areas of interest: e-commerce, algorithms, HCI, information retrieval, machine learning, data mining, NLP, multimedia, computer vision, statistics, security and privacy.

Clearly this set is incomplete — please post your CS research blog recommendations in the comments below; I’d be particularly interested in blogs covering hardware and computer architectures.

Written by Tom

7 May 2012 at 9:25 pm

## Mathematics is the language of nature

11:15, restate my assumptions:

1. Mathematics is the language of nature.
2. Everything around us can be represented and understood through numbers.
3. If you graph these numbers, patterns emerge. Therefore: there are patterns everywhere in nature.

Maximillian Cohen, π

Written by Tom

5 January 2012 at 10:32 pm

## Feynman, Bethe and the beauty of mathematics

To those who do not know mathematics, it is difficult to get across a real feeling as to the beauty, the deepest beauty, of nature…If you want to learn about nature, to appreciate nature, it is necessary to understand the language that she speaks in.

The Character of Physical Law (1965)
Richard Feynman

This term I have been teaching a new first year undergraduate module, Mathematics for Computing, in which I have been trying to impart a little bit of love for mathematics. While we have covered a number of underpinning topics relevant to computer science, such as propositional logic, set theory and number theory, I have also tried to show that there are a multitude of clever little tricks that can make arithmetic and performing seemingly complex calculations that little bit easier. And in doing so, I was reminded of the mathematical prowess of Richard Feynman as well as Hans Bethe, Nobel laureate in physics and Feynman’s mentor during the Manhattan Project. Bethe is one of the few scientists who can make the claim of publishing a major paper in his field every decade of his career, which spanned nearly 70 years; Freeman Dyson called Bethe the “supreme problem solver of the 20th century.

An example of Bethe’s mastery of mental arithmetic was the squares-near-fifty trick (taken from Genius: The Life and Science of Richard Feynman by James Gleick):

When Bethe and Feynman went up against each other in games of calculating, they competed with special pleasure. Onlookers were often surprised, and not because the upstart Feynman bested his famous elder. On the contrary, more often the slow-speaking Bethe tended to outcompute Feynman. Early in the project they were working together on a formula that required the square of 48. Feymnan reached across his desk for the Marchant mechanical calculator.

Bethe said, “It’s twenty-three hundred.”

Feynman started to punch the keys anyway. “You want to know exactly?” Bethe said. “It’s twenty-three hundred and four. Don’t you know how to take squares of numbers near fifty?” He explained the trick. Fifty squared is 2,500 (no thinking needed). For numbers a few more or less than 50, the approximate square is that many hundreds more or less than 2,500. Because 48 is 2 less than 50, 48 squared is 200 less than 2,500 — thus 2,300. To make a final tiny correction to the precise answer, just take that difference again — 2 — and square it. Thus 2,304.

Bethe’s trick is based on the following identity:

$(50 + x)^2 = 2500 + 100x + x^2$

For a more intuitive geometric proof of this formula, imagine a square patch of land that measures $50 + x$ on each side:

Its area is $(50 + x)^2$, which is the value we are looking for. As you can see in the diagram above, this area consists of a 50 by 50 square (which contributes the $2500$ to the formula), two rectangles of dimensions 50 by x (each contributing an area of $50x$, for a combined total of $100x$), and finally the small x by x square, which gives an area of $x^2$, the final term in Bethe’s formula.

While Feynman had internalised an apparatus for handling far more difficult calculations (for which he became famous for at Los Alamos, such as summing the terms of infinite series or inventing a new and general method for solving third-order differential equations), Bethe impressed him with a mastery of mental arithmetic that showed he had built up a huge repertoire of these easy tricks, enough to cover the whole landscape of small numbers. Bethe knew instinctively that the difference between two successive squares is always an odd number (the sum of the numbers being squared); that fact, and the fact that 50 is half of 100, gave rise to the squares-near-fifty trick.

Unfortunately, the skill of mental arithmetic that did so much to establish Bethe’s (as well as Feynman’s) legend was doomed to a quick obsolescence in the age of machine computation — it is very much a dead skill today.

Written by Tom

7 December 2011 at 11:58 pm

Posted in Mathematics

## Proof by intimidation

with one comment

First year students, beware! The axiom of choice may be used on Monday…

(As always, a big thanks to xkcd.)

Written by Tom

25 November 2011 at 10:34 am

## A 9999-sided polygon

What do you call a 9999-sided polygon?

A nonanonacontanonactanonaliagon.

While polygons are important in computer graphics, what’s special about a 9999-gon? Well, not much really, but it made me think about the nomenclature for polygons: the word “polygon” comes from the Greek polygōnon, meaning “many-angled”. Polygons are usually named according to the number of sides, combining a Greek-derived numerical prefix with the suffix -gon, e.g. pentagon (5-gon), dodecagon (12-gon) or icosagon (20-gon) — with the triangle, quadrilateral and nonagon (9-gon) being notable exceptions. But beyond decagons, professional mathematicians generally prefer the numeral notation (n-gon).

Nevertheless, a 10000-gon is called a myriagon.

Written by Tom

13 November 2011 at 10:20 pm

Posted in Mathematics

Tagged with ,

## Proof that the square root of 2 is irrational

with one comment

(N.B. this blog post is mainly directed at my undergraduate students for their first year Mathematics for Computing module!)

The square root of 2 ($\sqrt{2}$, often known as root 2) is the positive algebraic number that, when multiplied by itself, gives the number 2. Geometrically, the square root of 2 is the length of a diagonal across a square with sides of one unit of length; this follows from the Pythagorean theorem. A quick approximation for the square root of two is $\tfrac{99}{70}$ (despite having a denominator of only 70, it differs from the correct value by less than $\tfrac{1}{10000}$).

In the first few lectures we have covered the basics of logic and the propositional calculus, including the idea of reductio ad absurdum, or more specifically, proof by contradiction (indirect proof). One of the examples given in the lecture was proving that the square root of 2 is irrational using infinite descent:

Assume that $\sqrt{2}$ is rational; this means that we can represent it as the ratio of two integers:

$\dfrac{a}{b} = \sqrt{2}$

Then $\sqrt{2}$ can be written as an irreducible fraction $\tfrac{a}{b}$ such that $a$ and $b$ are coprime integers:

$\left(\dfrac{a}{b}\right)^2 = 2$

It follows that:

$\dfrac{a^2}{b^2} = 2$
$a^2 = 2b^2$

Therefore $a^2$ is even because it is equal to $2b^2$ ($2b^2$ is necessarily even because it is 2 times another whole number and even numbers are multiples of 2); it follows that $a$ must be even (as squares of odd integers are never even). Because a is even, there exists an integer $k$ that fulfils:

$a = 2k$

Substituting in $2k$ for $a$ in the earlier equation:

$2b^2 = (2k)^2$
$2b^2 = 4k^2$
$b^2 = 2k^2$

Because $2k^2$ is divisible by 2 and therefore even, and because $2k^2 = b^2$, it follows that $b^2$ is also even which means that $b$ is even. As we have shown that $a$ and $b$ are both even, this contradicts that $\tfrac{a}{b}$ is irreducible. $\square$

Because there is a contradiction, the original assumption that $\sqrt{2}$ is a rational number must be false. By the law of excluded middle, the opposite is proven: $\sqrt{2}$ is irrational.

This proof was hinted at by Aristotle, in his Analytica Priora, but it appeared first as a full proof in Euclid‘s Elements (as proposition 117 of Book X). There are a number of other methods of proving that the square root of 2 is irrational, including a simple geometric proof and proof by unique factorisation (using that fact that every integer greater than 1 has a unique factorisation into powers of primes). Check them out!

Written by Tom

30 October 2011 at 10:26 am

Posted in Mathematics

Tagged with ,