Algorithm to calculate Inverse Factorial of Natural Numbers

Note:

1. All numbers are Natural numbers. Unless until specified
2. This works if the inverse factorial of the number is guaranteed to be a natural number. If you came here hoping to get gamma or pi function based solutions, Sorry turn back.

Calculating factorial is hard. But is there a way one can speedily calculate inverse factorial?. Suppose you were given a number that was promised to be factorial of a whole number will you able to tell the inverse factorial of that number. The post presents two observations on factorials and then formulates an algorithm to use these observations to perform the inverse of a factorial.

Observation 1 [Counting trailing zeroes]

Observation: All the factorials after 5! end in zeroes, i.e. The factorial has a lot of trailing zeroes at the end.

First step was to gather data. And to make matters simple I wrote a python script to plot the number of zeroes in factorial of the given number vs the number.

The graph is linear. Which is good!!. Now maybe we could find some relation to the number of zeroes in factorial of the number and the number itself. Just to make sure I also ran it from 0 to 20000. 

No surprises there. 

You can try the same using this python script.

How are the zeroes in the factorial related to the number itself?

This is simple a factorial is simply a product of all the natural numbers from 1 to that number. So a zero occurs every time we multiply a 10. Which means every time a 2x5 happens there is a zero. So there is a extra zero every 5 numbers. We don't have to worry about availability of '2's as they are in abundance (By the time you gain a factor of 5 we cross two even numbers).

[0] :: 0!   -> 1

[0] :: 1!   -> 1

[0] :: 2!   -> 2

[0] :: 3!   -> 6

[0] :: 4!   -> 24

[1] :: 5!   -> 120

[1] :: 6!   -> 720

[1] :: 7!   -> 5040

[1] :: 8!   -> 40320

[1] :: 9!   -> 362880

[2] :: 10! -> 3628800

[2] :: 11! -> 39916800

[2] :: 12! -> 479001600

[2] :: 13! -> 6227020800

[2] :: 14! -> 87178291200

[3] :: 15! -> 1307674368000

[3] :: 16! -> 20922789888000

[3] :: 17! -> 355687428096000

[3] :: 18! -> 6402373705728000

[3] :: 19! -> 121645100408832000

[4] :: 20! -> 2432902008176640000

It is clear that the pattern seems to follow. So the graphs look linear for big data. But are actually stepped. So generating the same graph for 0 to 100 we get

Now this is interesting. our hypothesis seems to hold, somewhat. But there seems to be no factorial with 5 zeroes at all, and there are these weird places where the zeroes seem to increase an extra digit. In fact 24! -> 620448401733239439360000 and  25! -> 15511210043330985984000000, from 4 zeroes to 6 zeroes. Lets zoom out a little.

As you can see the jumps seem to happen at factors of powers of 5. Or one zero jump at 25! 50! 75! and two zero jump at 125! 250! 375! etc. Lets plot the increase in number of zeroes.

For a larger data set

Try it out using this python script.

So this is cool. Lets try and explain. Our hypothesis that for every 2x5 there is a zero is correct. But that doesn't mean that for every 5 numbers there is a jump in number of zeroes of the factorial of the number. Lets see 24 has 4 '5's which are at 5, 10, 15, and 20, But 25 has 6 '5's at 5, 10, 15, 20 and two at 25 because 25 = 5x5. So given a number if we can calculate number of 5's that make the factorial of the number we can say the number of zeroes that the number makes. 

Formulating it given a number n

sum of (n/k) where {k = 5^m, m = 1,2,3.... | k < n}. ('/' signifies integer division)

For n = 26 we get (26/5) = 5 and (26/25) = 1. We cannot do (26/125) as 125 is > 26. So we can conclude that as 5+1 = 6. 26! has 6 zeroes. 

Doing the same for 80! we get (80/5) = 16, (80/25) = 3. Therefore 80! must have 19 trailing zeroes.

80!=71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000

Which is correct. 

Lets summarize,

Given a number we can safely say how may zeroes that the factorial might have. Which is done by the formula above.

So given a factorial of a number, By counting the number of zeroes one must be able to say that the number is within these 5 numbers, as all of them have factorials with same number of zeroes. But how does one work this in reverse. 

Let try to figure out the number given that factorial of that number has 44 trailing numbers. 

Now we know that 44 was written as a + b + c .... , where a is number of factors of 5, b of 25 ...

So we can work reverse 44/5 = 8, 44/25 = 1. Therefore 44 - 8 = 36 must be the number of '5' factors and 8 - 1 = 7 must be the number of factors of '25' and 1 must be the number of factors of '125'

Therefore number must be somewhere between 36*5 = 180 and 37*5 = 185(not inclusive). So the factorials of numbers 180 to 184 have 44 trailing zeroes  

180!=200896062499134299656951336898466838917540340798867777940435335160044860953395980941180138112097309735631594101037399609671032132186331495273609598531966730972945653558819806475064353856858157445040809209560358463319644664891114256430017824141796753818192338642302693327818731986039603200000000000000000000000000000000000000000000

181!= 36362187312343308237908191978622497844074801684595067807218795663968119832564672550353604998289613062149318532287769329350456815925726000644523337334285978306103163294146384971986648048091326497552386466930424881860855684345291680413833226169665212441092813294256787492335190489473168179200000000000000000000000000000000000000000000

182!=6617918090846482099299290940109294607621613906596302340913820810842197809526770404164356109688709577311175972876374017941783140498482132117303247394840048051710775719534642064901569944752621422554534336981337328498675734550843085835317647162879068664278892019554735323605004669084116608614400000000000000000000000000000000000000000000

183!=1211079010624906224171770242040000913194755344907123328387229208384122199143398983962077168073033852647945203036376445283346314711222230177466494273255728793463071956674839497876987299889729720327479783667584731115257659422804284707863129430806869565563037239578516564219715854442393339376435200000000000000000000000000000000000000000000

184!=222838537954982745247605724535360168027834983462910692423250174342678484642385413049022198925438228887221917358693265932135721906864890352653834946279054097997205240028170467609365663179710268540256280194835590525207409333795988386246815815268464000063598852082447047816427717217400374445264076800000000000000000000000000000000000000000000

One has to be careful while evaluating these. Because, take for example you find 10 zeroes this corresponds to 9 + 1 not 10 - 10/5 = 8 and 10/5 = 2 therefore 8+2. The best way to evaluate this, that I could come up with is to take an array where 0 index corresponds to number of '5's and 1 corresponds to number of '25's and so on and populate it. Check the final code for my answer

Now we can point out the number from its factorial to the accuracy of 5. But how do we get to the exact number.

Observation 2 [Number of digits in the number]

The number of digits of a factorial of a number increases with the increase in the number. This was obvious, But first the data

It is steadily increasing. Though not linear. Trying the same on a larger data set.

So, Its settled. The length of the factorial has something to do with the number. However one has to take into account that for smaller numbers this wouldn't work. 

And this seems to happen only below 10 twice. Shouldn't be a big deal as for these numbers the regular way of calculating the factorial and verifying would suffice and would be sufficiently fast enough.

Now the standard way of determining the number of digits in the number is to do a logarithm base 10 of the number and add one to the lower round off. Or to say

floor(log10(n)) + 1 (floor does the round off to lower number)

For example number of digits in 342345234 can be calculated by this method as log10(342345234) = 8.53446428616 so 8 + 1 = 9

Now to the magic part 'Stirling's Approximation'. It is written as 

ln(n!) = nln(n) - n , where ln is logarithm base e

So given n!, floor( log10(n!) + 1) gives us the number of digits in the number. 

Adapting the approximation formula. 

Let d be the number of digits in the factorial of a number n

d = floor( log10(n!) ) + 1
d = floor( ln(n!) / ln(10) ) + 1
d = floor( ( nln(n) - n ) / ln(10) ) + 1 

Can we approximate n from d?. I am not gonna try. But some careful observation should tell you that it might not simplify things.

Algorithm for Inverse Factorial

Now we can get back to the main problem. 

We can make guesses for 5 numbers and calculate the number of digits to pinpoint the number. As long as you can calculate ln(n) and ln(10) accurately we can approximate the number. And hence the inverse factorial.

However, its worth noting that it is all an approximation. And might not hold all too well for long. You might want to read through the error in stirling's approximation. But this must be accurate for quite large numbers. As the number of digits increase too rapidly in factorial function evident from the graph.

So for the final act lets put all together and guess the factorial of the number.

I wrote a python script to do all the simulations. Get it here.

Here are the results.

This is the error in determining the inverse factorial of the number vs the number. The script used to generate this is here.

And this shows the number vs the inverse factorial of the factorial of the number. You can try it out using this script.

I've tried this method up to 20000!. And does seem to do really well. However any bigger would heat up my computer crazy. But if you can, try and let me know.

Cheers!!

Note:

1. This algorithm assumes that there exists an inverse factorial for the given number. However this might not be the case always.
2. This only works for numbers written in base 10. Which is very inefficient. However it can be made to work for other base numbers with a few modifications.

Building Racket for Android

I've been using Racket for academic purposes and decided to try it running on android. I was able to get it built for android. This post details the efforts made and is also meant to be sort of a log entry.

Download the source from github. Use this script to compile it on linux/mac.

It's simple to compile it for android. However the real trouble lies in getting it to run, because you need to have all the startup files and also the binary should know where to find them. So first time you run it on a android device it shows this error message

Welcome to Racket v6.7.0.3.
standard-module-name-resolver: collection not found
  for module path: (submod (lib "racket/init") configure-runtime)
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
   /home/regnarts/workspace/scheme/android/armv5/racket/collects
standard-module-name-resolver: collection not found
  for module path: racket/interactive
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
  /home/regnarts/workspace/scheme/android/armv5/racket/collects
standard-module-name-resolver: collection not found
  for module path: racket/base
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
   /home/regnarts/workspace/scheme/android/armv5/racket/collects

Which is expected. Now you can fix this in two ways one is by using '-S' to specify the path that the interpreter is expected to look at. Or as the README suggests, edit the binary to change the default collects directory path name!!. You might want to go through the README and this post to get it working .

Once that is done the interpreter should start-up and behave as it would do on any other platform. However the boot time is notoriously long. Got to figure out a way to reduce it. This is not a main project but something I did to kill time. So I am not going to look into it now. However it would be really nice to get something like DRRacket to work on Android. This can be made into a app with moderate effort. But that's the story for another day.

Finally I could get my interpreter to run on racket running on Android.

Cheers!!

Cross-Compiling for Embedded Linux based systems

After my recent work with porting multiple things for android. I thought that it would be nice to do a tutorial for cross compiling existing linux projects over to the embedded devices. I will soon get into the details. For cross-compiling linux based binaries/libraries basically you need 3 things

1. Toolchain
2. Headers
3. Libraries

Toolchain

Depending upon the selected target you can always find a toolchain. Toolchains are always architecture specific (Duh!?). For example if your device is ARM based you cannot compile for it with MIPS toolchain. The most common toolchain that you will find for a device is GCC. It is open source toolchain. You might also find different flavours like linaro. Or find a different toolchain itself like clang/LLVM. Whatever the choice you will need these for most of the projects.

1. C compiler 
2. Assembler
3. C++ compiler
4. Pre-Processor
5. Linker utilities
6. Archive utilities

However, Observe that we are talking of a c or c++ based project here. Java, Python, Perl projects inherently depend upon their Interpreter or Virtual Machine to run. And also they are designed to be portable. Hence once compiled they should be able to run on any system provided the availability of the fore said things.

Headers 

These are basically collection of .h/.hh files that contain definitions of the functions/structures ,etc., the way it would be found on the real device. These are mostly created when you compile the kernel, and many more are added by the supporting libraries. Pre-Processor uses these to verify that the function calls that you will be making to the Operating system actually exist and are defined. One might in theory edit these files and add his own stuff or definitions and the project would pass the pre-processing step and compile. However if the system is to be linked these definitions have to be found somewhere. If the OS expects its binaries to be pre-linked then the linking process would fail. If dynamic linking is taken into account then it would fail and throw up a fault at run time. For example you might link your project with a 3.xx kernel based header and newer version of libraries. But if you try to run the project on a older kernel or with older libraries. Then it would not run and throw up a fault.

Libraries

These are basically there so that the linker can verify and statically link the binaries. It is however expected that the same library files exist on the device for it to work. You might in theory simply copy the library to the device and expect it to work. But sometimes, or most of the times the dependencies may not be the same and it would fail.

Now for a practical example take a look at port of LibAV to android. LibAV is an open source implementation of codecs for media play back and encoding. I had to use it to a personal project. I have however uploaded the source to github. It would be interesting to look into the build scripts that I have used to build the libraries. There are basically 3 of them for different architectures, namely ARM, MIPS and X86. This project was configured with autoconf. So it has a configure script that can be easily run. And thanks to popularity of Android, LibAV actually officially claim to support android(previously, wasn't the case). Observe that I configure the build with multiple parameters. But mainly the cross-compiler toolchain

which is configured at cross-prefix. The headers and libraries are located in sysroot, under include and lib directories respectively. Rest of the configurations are mainly project specific. Running this script obviously requires to to edit for your system, the locations would not be same. But in the same project under android directory you will find that multiple ARCH directories are there with executables of the same library compiled. If you are trying to port something linux to android, then do take a look in to the build scripts. You will find a variety of pointers for the job.

Have Fun!

Cheers !!

The Androux project

Finally, I've completed the linux support for the ports. I have decided to call the project androux. A play on words android and linux. You can grab the source from github. Finally "make" works and the compile script works on linux x86_64. The build scripts still won't run if you are using 32 bit machine. Will try to bring support for that in future. The android shell is not fit to run the configure scripts and hence a port of few utilities like sed and bash shell is required. I am working on it.

As of now you can create a Makefile and compile your projects on the device. I have tried a basic test and make works fine.

Visit github for instructions on compiling.

After compiling, you need to copy system folder created to the system folder of your device. You also need to copy the include and lib folders from platform directory corresponding to android version that your device runs.

The final system image will be quite big and I am quite sure that the partitions that are created in your phone by default are not enough to hold it all. There are two ways of approaching this problem, either extend the system partition, if the inbuilt flash can hold it or create a new partition in the sdcard and change the mount scripts to mount that partition as system instead.

When writing install scripts in make file we need to take care that system partition is mounted r/w. By default the system partition is read only in android. Or you could choose another install location.

I still haven't had time or resources to test on an actual device. Please let me know if any of you can do so and share the results

Cheers ! :-)
Stay Awesome  

MAKE compile script added

Quick repo update. I've added the compile script for make

Have fun!! Cheers :-)

c++ and g++ compile scripts fixed to build on mac OS X

I have finally found time to fix the scripts to build c++ and g++. I have pushed the code to the github. You can grab a snapshot here - https://github.com/heliumfire/androux. Or you can alternatively do

git clone -depth=1 https://github.com/heliumfire/androux

I am also working on getting linux scripts to work so that building can be supported on ubuntu. Next plan is to fix make and bash so that everything can be run smoothly on the device.

Future plans is to grab a AOSP source and integrate into it. I was thinking of first trying it on GB. Still haven't done it yet.

As far as putting it up on a real device. I am trying to procure an android device, unfortunately its an old one running GB (xperia play). I need help to try it out on other devices. Let me know if anyone is willing to.

Source for linux utilities on Android

Hi all,

I have finally made time to push the source of my ports to github. Access the source at https://github.com/heliumfire/androux. To get the source clone the repo by
git clone https://github.com/heliumfire/androux. As of now the source only compiles binutils gmp mpc and mpfr. And will only work on linux. I will put up more stuff as the time comes

Cheers, Have fun :)