Saturday, May 25, 2013

Hyperbolas and ellipses with one equation

Sometimes you don't discover something new in math. Actually, it's really hard to discover something new in math as people have been kind of busy, and I have a result I like which I rediscovered a few years back.

It is a way to get hyperbolas and ellipses with a single equation.

The equation is x2 - Dy2 = 1, in rationals, so to program it you need to use doubles:

y = -2t/(D - t2)


x = (D + t2)/(D - t2)

and you get hyperbolas with D greater than 0, and ellipses with D less than 0, and the circle when D=-1, giving the well-known circle parameterization:

With x2 + y2 = 1: y = 2t/(1 + t2) and x = (1 - t2)/(1 + t2)

So yeah, you can just draw an ellipse or a hyperbola by incrementing t, which gives you x and y. Easy.

I like easy.

When I came up with my own solution for x and y with a parameter, I was shocked to discover that I was so far off from the time of the initial discovery that Fermat himself knew the above.

And Pierre Fermat died in 1665. So he's been dead for over 340 years.

Turns out it's really hard to find something new in math. No big deal though. I also like rediscovering things too, as it's fun!

So you can use a single equation for hyperbolas and ellipses, just by shifting that thing D, and yup, if you remember your trigonometry--or is it algebra?--that means that D has to be connected to eccentricity. And if you're really smart, figure out the equation that connects them directly to prove your intelligence.

Now, derive the equations yourself. If some dude centuries ago could do it, why not you today?

I did it. It's not all that hard actually, and might be a fun exercise to test your limits with something easy.

See! Isn't math fun?

James Harris

Saturday, May 18, 2013

Simple and fast prime number counter

One of my favorite discoveries is one of my most innovative. It counts prime numbers. Here is the algorithm version. It uses a much smaller list of primes to count a much bigger number.

With positive ints or longs--where pj is the jth prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/pj,j-1) - (j-1)}

The P(x,n) function will count primes up to and including x, if n equals the count of primes up to sqrt(x), and if as you iterate you never let n be greater than the count of primes up to and including sqrt(x), if the function receives an n greater than that value it just needs to reset it to that count.

That is the fastest algorithm for counting primes for its size.

For say, the count of primes up to 100, if you tried P(100,10), the algorithm would reset n to n=4, so you'd have P(100,4), because there are 4 primes--2, 3, 5 and 7--up to sqrt(100).

Notice with just those 4 primes you count all primes up to 100.

P(100,4) = 100 - 1 - (P(50, 0) - 0) - (P(33,1) - 1) - (P(20,2) - 2) - (P(14,3) - 3)

Except P(14,3) needs a correction because the 3rd prime is 5 which squares to 25, so that is going too high as it's bigger than 14 and has to be reset to P(14,2). Then I have:

P(100,4) = 100 - 1 - 49 - 16 - 6 - 3 = 25

Those numbers are explained simply enough: there are 49 even composites, 16 odd composites with 3 as a factor, 6 composites with 5 as a factor but no smaller prime as a factor. And 3 that have 7 as a factor with no smaller prime, and I'll give those as it's just three numbers so easy to do and they are of course: 49, 77 and 91.

And you subtract 1 for 1 itself, where the principle is easy enough--subtract composites and 1 to get the count of primes.

Another example is P(10,2) = 10 - 1 - (P(5,0) - 0) - (P(3,1) - 1) = 10 - 1 - 4 - 1 = 4

Where of course the 4 primes are 2, 3, 5 and 7.

There are 4 even composites--4, 6, 8, 10--which are being counted by P(5,0) and one composite divisible by 3, which is NOT even, which is 9, and that count is given by P(3,1) - 1 = 1.

The algorithm is fairly easy to program.

So you need a list of primes up to sqrt(x), so the hardest thing is how you generate that list of primes, which is usually done using the Sieve of Eratosthenes, even for the currently established fastest prime counting algorithms known! But for something quick you can just enter a small list.

For example the first 10 primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

With that list using the algorithm you can count primes up to 29*29 = 841.

The P function also has to check to see that n is not greater than count of primes up to, and including sqrt(x), where a simple implementation is just brute force, find floor(sqrt(x)) and count primes, for instance for 840, floor(sqrt(840)) = 28, and you can just count up to see that n  = 9, as 23 is the last prime less than or equal to 28.

Notice at 529 = 23*23, you'd still have n = 9, as you go up to and including sqrt(x).

You can actually get clever here as n tries to go greater at a very specific place as you iterate, so you don't actually have to check the square root at each iteration, but am just showing the simplest route to implementation.

To see a recent rather long-winded explanation of how the algorithm is derived and to understand why it works you can click here. No advanced math in the derivation, as you just need to know what a prime is and what division is, as well as some basic algebra to follow it.

The basic idea of counting composites and subtracting 1 to count primes is centuries old.

What's new with my prime counting function is a slight tweak.

I just did one little extra thing that no one did before over those centuries, which makes it more concise, easier to explain, understand and, importantly, implement.

If you're mathematically adventurous you can have it call itself to remove needing to give it a list of any primes, but then it's a lot slower. Run timing tests if you wish to see how much slower. But that is just a lot more recursion, and you can do things to speed it back up, if you're bored.

I've had it for over ten years, so I no longer play with it. Had all my fun with it years ago.

James Harris