Why is factorial so slow in nerdamer?

[Saikedo]

I noticed that calculating big factorials can be super slow in nerdamer. For example doing something like this

console.time("a");

nerdamer("factorial(720)").evaluate().text();

console.timeEnd("a");

Takes somewhere from 2-4 seconds to calculate.

I am fine with the calculation returning Infinity in this cases but I was wondering why the calculation is so slow.

A simple function like this

console.time("a");
var f = [];
function factorial (n) {
  if (n == 0 || n == 1)
    return 1;
  if (f[n] > 0)
    return f[n];
  return f[n] = factorial(n-1) * n;
} 
factorial(720)
console.timeEnd("a");

Takes less than a millisecond to compute.

[Saikedo]

I just realized that nerdamer factorial also works with floating numbers like factorial(5.5) and so on. I am assuming calculating these takes longer?

Is it a good idea to use the simple factorial function if both inputs are Integers and fall back to whatever nerdamer uses right now if the arguments are not integers?

[Saikedo]

Sorry for spamming the post so much but I just did some debugging and realized that my above post is not correct. The following function is actually the reason for the slowdown. The loop inside seems to be running very slow.

bigfactorial: function (x) {
            var retval = new Frac(1);
            for (var i = 2; i <= x; i++)
                retval = retval.multiply(new Frac(i));
            return retval;
        },

Is this happening because .multiply is slow or because we are keep creating Frac on every loop iteration?

[jiggzson]

@Saikedo, I'll take a look at this and see if we can improve on this. You may be right and the constant calls to Frac are gumming up the works. I don't even see a reason for doing so and at a quick glance it does appear to be very inefficient. Who knows what past me what thinking.

Either way, always keep in mind that you're free to override the Math2 functions with your own if they're not to your liking. I always appreciate it if you let me know when you find a more efficient algorithm. Just know that I can't troubleshoot your custom implementation and you own it. The Math2 object is basically the sister object to the Math object. It's there because I don't like touching native objects.

You can get the Math2 object by calling var Math2 = nerdamer.getCore().Math2.

[Saikedo]

@jiggzson The reason I did not wanted to implement a custom factorial function, in this case, is because the function itself seems to be doing great and the algorithm that you use is actually quite fast. One improvement you can make there is to use memoization but I agree with you that most likely creating Frac is what causing the major slowdown in this case.

And yes, I also sometimes go back to my previously written code and wonder why the hell I did things in a certain way :) I interpret that fact as me being a better programmer today compared to yesterday hehe.

[jiggzson]

@Saikedo, fixed.