Is This a Fast Factorial Algorithm?

[Asterisk Propernoun]

I believe I created either faster or slower factorial algorithm than the standard bottom-up multiplication used by computers. Allow me to explain. I first started out by coming across some patterns:

 

((10+10)/2)^2-10x10=((20+20)/2)^2-20x20=0=0^2
((11+9)/2)^2-11x9=((21+19)/2)^2-21x19=1=1^2 1-0=1
((12+8)/2)^2-12x8=((22+18)/2)^2-22x18=4=2^2 4-1=3
((13+7)/2)^2-13x7=((23+17)/2)^2-23x17=9=3^2 9-4=5
((14+6)/2)^2-14x6=((24+16)/2)^2-24x16=16=4^2 16-9=7
((15+5)/2)^2-15x5=((25+15)/2)^2-25x15=25=5^2 25-16=9
((16+4)/2)^2-16x4=((26+14)/2)^2-26x14=36=6^2 36-25=11
((17+3)/2)^2-17x3=((27+13)/2)^2-27x13=49=7^2 49-36=13
((18+2)/2)^2-18x2=((28+12)/2)^2-28x12=64=8^2 64-49=15
((19+1)/2)^2-19x1=((29+11)/2)^2-29x11=81=9^2 81-64=17
((20+0)/2)^2-20x0=((30+10)/2)^2-30x10=100=10^2 100-81=19

 

Now this is showing quite a few things. First off, it's showing that, although the mean of numbers stay the same when you add 1 to a number and subtract 1 to another, the product of the two numbers isn't. The difference between the mean squared and simply multiplying the two numbers together is the absolute value of the difference between one of the numbers and the mean squared. The second thing this is showing is that the size of the numbers alone does not play a role in the difference between the mean squared and the product of the two numbers, since we could do the same things with 11 & 9 that we did with 21 & 19 and get the same answer. The third thing this pattern is showing is that you can easily get perfect squares by adding up odd numbers:

 

0=0^2

0+1=1^2

0+1+3=4=2^2

0+1+3+5=9=3^2

0+1+3+5+7=16=4^2

 

And so-on. With these patterns in mind, many impressive, yet impractical things can be done such as (((a+b)/2)^2-ab)^0.5x2=|a-b|. However, I'm trying to use this to get a faster factorial method, which I might have succeeded in doing.

 

Most people know that a factorial is multiplying all of the natural numbers that comes before the natural number listed once, and that's obviously a characteristic that the patterns listed above can manipulate (keep in mind that this will only work with odd numbers, but I have a simple trick at the end to where this method can be used with even numbers).

 

9!=9*8*7*6*5*4*3*2*1

 

So if we where to take the mean of 9 and 1, we would get 5. All that needs to be done is take the square of 5 and subtract it by odd numbers until we're left with our original number, which is 9.

 

9!=5*24*21*16*9

 

This will get us the correct answer, 362880. If we wanted to perform this trick with an even number like 10, then we would just do what we did with the number below it and multiply that by 10.

 

10!=5*24*21*16*9*10

 

The answer here is 3628800. The process can pretty much be written as so:

 

n!=((n+1)/2)(((n+1)/2)^2-1^2)(((n+1)/2)^2-2^2)(((n+1)/2)^2-3^2)... until (((n+1)/2)^2-m^2)=n

 

And, if the number happened to be even, then we would simply subtract it by 1 before starting the algorithm, and then, come the time for the final multiplication, we'll include the original number to the numbers we're supposed to multiply. Now, this may seem significantly slower at first glance, but there are some things you have to keep in mind:

 

You only have to find (n+1)/2 and ((n+1)/2)^2 once before you can simply save the numbers for when you need them.

 

In order to find the perfect squares, you only need to add up odd numbers.

 

This can be combined with a fast multiplication algorithm so it can be even faster, though this can be included in simple bottom-up multiplication as well.

 

Your thoughts?

[Schneibster]

It's plausible. Since I'm not being paid I'll leave it to a real mathematician (and there are some here) to comment on whether it will actually work.

 

If it does work, then if you can design the algorithm right in terms of primitives you'll get something that's ripe for compiler optimization in a RISC.

 

This is an assembly/machine language level optimization, however, something you do in a compiler, not in, say, C or Fortran.

 

That's my opinion as a CS. You should wait for a mathematician to confirm the algorithm works.

[imatfaal]

IANAM

 

first bit is just simple algebra

 

[latex]\left(\frac{(n+j)+(n-j)}{2}\right)^2-(n+j)(n-j)[/latex]

 

[latex]\left(\frac{2n}{2}\right)^2-(n^2+nj-nj-j^2)[/latex]

 

[latex] n^2-(n^2-j^2)[/latex]

 

[latex]j^2[/latex]

 

second bit ditto

 

[latex](x+1)^2-x^2 = x^2+2x+1-x^2=2x+1[/latex]

 

this bit

 

(((a+b)/2)^2-ab)^0.5x2=|a-b|

 

[latex]2*\left(\left(\frac{(a+b)}{2}\right)^2-ab\right)^{0.5}=|a-b|[/latex]

 

Unless I have misinterpreted is not true

9!=9*8*7*6*5*4*3*2*1

9!=5*24*21*16*9

 

Not sure I follow your logic - but this is trivially correct as it is associative rule

9!=9*8*7*6*5*4*3*2*1

=5*(6*4)*(3*7)*(2*8)*(9*1)

=5*(24)*(21)*(16)*(9)

[Schneibster]

Snicker @ IANAM

[Asterisk Propernoun]

IANAM

 

first bit is just simple algebra

 

[latex]\left(\frac{(n+j)+(n-j)}{2}\right)^2-(n+j)(n-j)[/latex]

 

[latex]\left(\frac{2n}{2}\right)^2-(n^2+nj-nj-j^2)[/latex]

 

[latex] n^2-(n^2-j^2)[/latex]

 

[latex]j^2[/latex]

 

second bit ditto

 

[latex](x+1)^2-x^2 = x^2+2x+1-x^2=2x+1[/latex]

 

this bit

 

(((a+b)/2)^2-ab)^0.5x2=|a-b|

 

[latex]2*\left(\left(\frac{(a+b)}{2}\right)^2-ab\right)^{0.5}=|a-b|[/latex]

 

Unless I have misinterpreted is not true

9!=9*8*7*6*5*4*3*2*1

9!=5*24*21*16*9

 

Not sure I follow your logic - but this is trivially correct as it is associative rule

9!=9*8*7*6*5*4*3*2*1

=5*(6*4)*(3*7)*(2*8)*(9*1)

=5*(24)*(21)*(16)*(9)

 

I'll assume that by IANAM, you mean 'I Am Not A Moron'. I've read from a book about how to write scientific reports that it's always better to provide too much information than too little. I may have over explained things a bit, but I just wanted to be on the safe side.

 

For the part of (((a+b)/2)^2-ab)^0.5x2=|a-b| not being true, I don't get why you're saying that it isn't (more over-explanation, incoming!):

 

11+13=24 10007+9887=19894

24/2=12 19894/2=9947

12^2=144 9947^2=98942809

11*13=143 10007*9887=98939209

144-143=1 98942809-98939209=3600

1^0.5=1 3600^0.5=60

1*2=2 60*2=120

|11-13|=|13-11|=2 |10007-9887|=|9887-10007|=120

 

It may just be associative rule, but the method I used to reach the step 9!=5*24*21*16*9 is what (I believe) makes this algorithm faster than normal.

 

Please keep in mind that I'm just a high school math enthusiast, and not a legitimate mathematician. Thanks.

[John]

I'll assume that by IANAM, you mean 'I Am Not A Moron'.

M probably stands for "mathematician," and I'm not one either, though I may be someday.

 

I've read from a book about how to write scientific reports that it's always better to provide too much information than too little. I may have over explained things a bit, but I just wanted to be on the safe side.

 

For the part of (((a+b)/2)^2-ab)^0.5x2=|a-b| not being true, I don't get why you're saying that it isn't (more over-explanation, incoming!):

 

11+13=24 10007+9887=19894

24/2=12 19894/2=9947

12^2=144 9947^2=98942809

11*13=143 10007*9887=98939209

144-143=1 98942809-98939209=3600

1^0.5=1 3600^0.5=60

1*2=2 60*2=120

|11-13|=|13-11|=2 |10007-9887|=|9887-10007|=120

Two examples aren't enough to establish the equality, but it can be shown true (though at first glance I thought it was false too). We have

 

[math]2\sqrt{\left(\frac{a+b}{2}\right)^{2} - ab} = 2\sqrt{\frac{a^{2} + 2ab + b^{2} - 4ab}{4}} = \sqrt{a^{2} - 2ab + b^{2}} = a - b[/math].

 

Since addition and multiplication are commutative, it's easy to see that b - a is also a square root here (and in fact is the one we want if b > a, since we're looking for the principal square root), and we can codify this by using the absolute value as you've done.

 

It may just be associative rule, but the method I used to reach the step 9!=5*24*21*16*9 is what (I believe) makes this algorithm faster than normal.

 

Please keep in mind that I'm just a high school math enthusiast, and not a legitimate mathematician. Thanks.

I'm not a computer scientist, and I don't know whether the extra required comparisons in your method outweigh any potential savings in terms of multiplication operations, but if nothing else, this does yield some insight into the mechanics of the factorial, even if (as imatfaal noted) it's ultimately an application of the associative (and, maybe more importantly, commutative) properties of multiplication.

 

Edit: I retract some of this, because I don't actually think any comparisons are added to what's required originally, and this method may require fewer. It is a nice little algorithm, in any case.

Edited April 11, 2014 by John

[Acme]

Accepting that the algorithm is correct, i.e. returns n!, then the best way I know to see if it's faster than others is to bench test it against others. Here's a page with 5 flavors for you to try: >> http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

[Schneibster]

I agree, Acme. It's actually an A/B Taste Test of two RISC compilers. (I'd go with IBM or SPARC.) I'd use a direct test of the machine language length, watch memory usage (probably not a problem but remember that step where you store the value) and run a sprint test of factorials overnight. Finally, I'd test the output values to make sure it works rather than just outputting whatever.

 

I'd compare the results with a standard RISC compiler's factorial handling using the same test, and also with the performance of a CISC compiler which both the standard and your modified RISC compilers should beat.

 

I suspect you'll find, Asterisk, if you try to use CISCs and CISC compilers, that it performs worse. But that's because they don't have optimized primitives, so that's OK; your goal isn't a better CISC algorithm, but a better RISC algorithm. If your algorithm really works right, then it will work only on RISCs.

Edited April 11, 2014 by Schneibster

[uncool]

When asking whether it's faster, you'll have to define how "fast" each operation is. Please note that the following is from memory:

 

I'm going to approach this from two assignment of "speeds" to each operation.

 

The first assignment is that multiplication takes "infinitely long" compared to addition. In other words, the way we "rate" any algorithm that only uses addition and multiplication is to check how many multiplications it uses.

 

Using the usual factorial algorithm (put 1 in memory for the factorial, put 1 for the index, start the loop, multiply the factorial by the index, add 1 to the index, end the loop), you need n multiplications to find n!. Using your algorithm, you will also need n multiplications, as follows:

 

Assuming n is odd:

1: Find (n + 1)/2 (this doesn't actually count as a multiplication but rather a shift; multiplication and division by 2 is a special case).

2: Find ((n + 1)/2)^2 (this does count; you are multiplying (n + 1)/2 by itself) - 1 multiplication

3: For each i from 1 to (n + 1)/2 - 2, find ((n + 1)/2)^2 - i^2 (one multiplication), and multiply that in (another multiplication) - 2 multiplications for each i from 1 to (n + 1)/2 - 1.

 

Step 3 gives us a total of n - 1 multiplications, while step 2 gives us one multiplication, for a total of n multiplications.

 

If n is even, it takes (n - 1) + 1 = n calculations, since you reduced it to the case that n is odd.

 

The second assignment is a bit more interesting. When doing circuitry, it turns out that the algorithm for multiplication takes 3 cycles, whereas addition only takes 1 cycle, so to evaluate how many cycles it takes, you "assign" any algorithm 3 times the number of multiplications it does plus the number of additions it does.

 

The "naive" factorial algorithm just adds 1 each time and multiplies, for a total of 4n cycles.

 

I think that your algorithm uses 2 additions (one by adding 1 to i, and one for subtracting the squares) for each i from 1 to (n - 1)/2 and one more (to get (n + 1)/2 in the first place); it does use 2 multiplications for each i from 1 to (n - 1)/2 and 1 more, for a total of n multiplications and n additions. So it turns out that as long as all you care about is additions and multiplications, your method will take exactly as long as the naive method.

 

I would be surprised if there were a "fast" method to calculate factorials exactly without using some kind of lookup table.