Archive - Sep 14, 2007

Date

Factorial Algorithms Part 1

Factorial algorithms are the main topic I'm working on from 2 months ago. A lot interesting founds.
The naive algorithm was discussed in a previous post.
This post will introduce a new way to find the factorials. The algorithm used in GMP was described briefly in the manual.

The first step is to find out all the 2 factors. I don't know how exactly GMP would do that. Divide all the number have the potential of having 2s? find how many binary zeros in the end of the number and remove them? Could be any of those.

Second step is to collect up the terms. Which will result some possible powers like (3*5)^3.

Third step is to multiple everything inside each term, using binary split method that is nice in chain multiplication.

Some of my analysis result.
1. All odd number except 1 will be a factor.
2. There will be around floor(base 2 log(n)) terms when finding the factorial of n

Considering binary splitting multiplication will take the most of the time because it contains n/2 multiplications. The process suppose to run at O(n log(n)^3) when used with FFT based multiplication according to mathematical constants and computations site's description on binary splitting. I guess the GMP one could run faster because factor 2 is out and exponentiation by squaring further increase the speed.

Bleach Movie: Memories of Nobody

The subbed version of the Bleach: Memories of Nobody takes so long to come out. But finally, XDarkred007X uploaded a subbed version on Youtube.(Search here)
So after like 1 hour and 30 minutes.

BORING!!!
What a corny movie!!! The boss want to destroy the world... Good guys have to stop it.... and the boss got owned so easily is not even funny! The ending is emotional but not emotional enough compare to FullMetal Alchemist's movie: Conqueror of Shamballa.
So I decide to watch some higher quality video: Hello Kitty!
Enjoy

Honey Pot that kill bots