version: desktop | mobile

Dave's Free Press

the Slightly Less Bad And Wrong Blog Edition

 

Recent posts

(subscribe)

Recently commented posts

(subscribe)

Less important journals

Search

geeky politics silly review culture rant music religion meta weird books drinking perl london media transport cooking language hacking photography olympics whisky maths web spam film phone holidays sport bastards iphone bryar rsnapshot palm telecoms bbc cars travel clothes lolcats amazon etiquette yapc deafness home radio environment latin privacy linux curry security unix work go anglo-saxon review-of-reviews gps
Sat, 3 Oct 2009

Graphing tool

I made a shiny thing! It can plot arbitrary functions of the form x=f(y) or y=f(x). Under the skin, it just massages its arguments and passes them through to Gnuplot. Here's the source code.

Update: now 48.3% even shinier - see on the right

Posted at 21:35:19 by David Cantrell
keywords: geeky | hacking | maths | perl
Permalink | 0 Comments
Wed, 30 Sep 2009

Optimising n! - revisited again

For the background, see this post and this post.

I have had An Branewave! When I said that

  100! = 250 * 333 * 520 * 714 * 119 * ...

was wrong (which it is) I stupidly didn't realise that there is a pattern to the missing terms. The 250 comes from observing that there a 50 multiples of 2 less than or equal to 100. There are also 25 multiples of 4 (also known as 22), 12 multiples of 8 (aka 23), 6 multiples of 24, 3 multiples of 25, and 1 of 26. the 25 multiples of 4 contribute another 225. The 12 multiples of 8 (which of course are also multiples of 4) contribute another 212, and so on.

So we see that 100! is divisible by 250 + 25 + 12 + 6 + 3 + 1, or 297.

There is, of course, a similar pattern for all the other prime factors.

Posted at 01:44:23 by David Cantrell
keywords: geeky | maths
Permalink | 0 Comments
Fri, 25 Sep 2009

Combining functions

There was a great programme on Radio 4 yesterday about Newton and Leibnitz. I'm not sure why, but it inspired me to consider the curve that is constructed from y = x2 when x <= 0, and y = x when x > 0 . I want to reduce that to a single function.

It can obviously be done.

Consider that to fit a curve to any* three points, you can do it with a curve y = a + bx + cx2. Figuring out the three constants a, b and c is trivial, you just solve three simultaneous equations. Similarly, for four points, you fit y = a + bx + cx2 + dx3, and so on. To accurately fit the curve I described at the beginning, you need an infinite number of points, thus an infinite number of constants.

I'm sure that this can be done - obviously you can't actually calculate an infinite number of constants, but I'm sure that with a bit of integration it could be done. And it can be done for any such pair of functions which meet at a point. However, on further reflection I'm not entirely convinced that it can be done in the general case - you have that pesky discontinuous yes/no conditional in the middle: "is x <= n?".

* not strictly true - consider (0,0), (0,1), (1,0).

Posted at 00:54:13 by David Cantrell
keywords: geeky | maths
Permalink | 3 Comments
Tue, 28 Apr 2009

Factoring Factorials

Take a factorial. Any factorial. Factor it*. Notice a Pattern.

That pattern is that if you list all of the prime factors in order and the number of times they appear, at no point does any larger factor appear more often than any smaller factor. This would appear to be obvious, and it "obviously" applies to all factorials** (I've verified it by hand up to 28!, at which point I got bored). But I'm finding it hard to put a proof into words - or more concisely but equivalently - into symbols.

* this is easy. While factoring 1124000727777607680000 might be quite hard, if you know that it's 22! it becomes trivial because we know that it is divisible by 2, 3, 4, 5, ..., 21, 22, each of which is trivially factorable. Given that each number is the product of a unique set*** of factors, the factors of 22! can only be the set of all the factors of all the numbers we multipled to get 22!. Easy!

** it becomes obvious when you consider Eratosthenes' method for testing primality.

*** yes, I know, it's not really a set.

Posted at 17:53:19 by David Cantrell
keywords: geeky | maths
Permalink | 0 Comments
Mon, 10 Nov 2008

Umbrellas

What's the point of umbrellas? To be effective, their diameter needs to be slightly more than h * sin(ϑ) (where h is your height and ϑ is the angle of the rain from the vertical). So, if rain is falling vertically you need an umbrella with diameter slightly more than* the width of your shoulders. If rain is going horizontally, you need an umbrella slightly wider than you are tall. If rain is coming down at 20° from the vertical, you need an umbrella diameter just over 0.34 * your height, and so on.

Given that rain can subtend any angle from 0 to 90° from the vertical, then unless you wish to be your umbrella supplier's very best friend in the whole world, you need a Very Large umbrella. And yet, no-one carries such a thing. Indeed, I don't think anyone makes such a thing suitable for anyone other than midgets. So we see that every umbrella user has, from the point of view of keeping themselves dry, made the wrong decision. Their partial solutions are no better than what they would achieve by wearing a good coat and a hat.

Unfortunately, their partial solutions come at the cost to everyone else of getting poked in the face by the metal spikes at the edge of the umbrella.

* the value of "slightly more" is a function of ϑ and the shape of the human body. A good approximation would be to assume that a person's width is h/3 and their depth is h/4.

Posted at 22:21:42 by David Cantrell
keywords: etiquette | maths | rant
Permalink | 2 Comments
Wed, 27 Aug 2008

Optimising n! - revisited

For the background, see this post.

Late one night I thought that you might be able to simplify n-factorial thus:

Take the product of p(i)int(n/p(i)) for i=1 to i=Φ(n). Damnit, I wish there was a good and easy way of writing mathemagics on t'interwebnet.

Where:

  • n is the number whose factorial we wish to calculate;
  • p(i) is the ith prime number;
  • Φ(n) is the number of primes less than or equal to n

Now, without using a lookup table, p() and Φ() are hard to calculate, but at least you'd avoid a lot of the problems that come from using the stupendously big numbers that come as intermediate results in calculating factorials.

Unfortunately, that formula is wrong anyway. It's a restatement of this:

100! = 250 * 333 * 520 * 714 * 119 * ...

which came from noticing that 100! is the product of 50 numbers which have 2 as a prime factor, 33 numbers which have 3 as a prime factor, 20 numbers that have 5 as a prime factor, and so on. Unfortunately, it doesn't take account of numbers like 4 and 18 which have a repeated prime factor - 4, for example, is 2 * 2 and 18 is 2 * 3 * 3. Bother.

Posted at 17:13:10 by David Cantrell
keywords: geeky | maths
Permalink | 0 Comments
Tue, 22 Jul 2008

Wikipedia: WRONG AGAIN

Wikipedia has a reputation for being of rather low quality, particularly in the humanities. In the sciences and technology it is supposed to be pretty good. But today, I found an error in their article about ... the triangle. One of the most basic mathematical concepts. And they got it wrong. Joy.

OK, to be fair, it's only subtlely wrong, is correct for the majority of cases, and one could argue that the context in which the inaccurate information is presented makes it OK. But I disagree.

In a section called "Basic facts" they first mention that triangles were described thoroughly by Euclid. Good. In the next paragraph, they say that the internal angles add up to 180°. Not so good. They only do so in some spaces, the most commonly known of which is the Euclidean space. Anyway [click click click type click] I've fixed it now. I wonder how long it'll stay fixed, or whether some wanker will revert my pedantry.

Posted at 00:31:44 by David Cantrell
keywords: geeky | maths | web
Permalink | 0 Comments
Wed, 11 Jun 2008

Optimising n!

If you want to add up all the numbers from 1 to n, you can do it two ways. The slow, inefficient way is to calculate:

1 + 2 + 3 + ... + n

The quick way is to remember what you were taught in school, that:

1 + 2 + 3 + 4 + 5 + 6 = (6 + 1) + (2 + 5) + (3 + 4) = 7 + 7 + 7

and that in general:

1 + 2 + ... + n = n(n+1)/2

This optimisation might not matter for small values of n, but for n = 1000000 it really makes a big difference. This got me thinking whether there was a similar trick for calculating the product of all numbers from 1 to n - that is, n-factorial, or n!.

This matters even more for n! because it gets so large so quickly that computers are unable to accurately represent the intermediate values. In fact, 20! is the largest that can be respresented on a 64 bit machine. 21! can only be approximated, as you need to use a floating point number. This means that not only is calculating really big factorials time-consuming, it's not possible at all to do it accurately with native datatypes.

I don't even know if there is a simple re-statement of n! like there is for the sum above, but I'm gonna spend a few idle minutes working on it.

Posted at 20:10:32 by David Cantrell
keywords: geeky | maths
Permalink | 1 Comment

Archive

2009

Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan

2008

Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan

2007

Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan

2006

Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan

2005

Jan Feb Mar Apr
May Jun Jul Aug
Sep Oct Nov Dec
Dec
Nov
Oct
Sep
Aug
Jul
Jun
May
Apr
Mar
Feb
Jan