Factorial Division with Functional Javascript

Photo by Jeswin Thomas on Unsplash

Background

In a Algebra book chapter about Factorial Operation, I found that the division operation can be solved manually through arithmatic method like multiplying each number succession and divide the numerator to the divisor. Or, it can be solved algebraically — which is less intensive — by finding greatest common factor of both numerator and divisor, then multiply the rest of the fraction.

For a computer, multiplying a great length of number may only take a fraction of a second, for us it may take forever — and more. Computer are good at doing repetitive things, until it no longer have the capacity for computing certain problem with large numbers.

Here I’ve provided a factorial function — from my older article — which can be used for testing and proofing:

let facto = x =>
  x === 1 ? 1 : x * facto(x - 1)

facto(6) // 720
facto(4) // 24
facto(6)/facto(4) // 30
facto(4)/facto(6) // 1/30 or 0.0333333

This factorial function is the simplest one I can create and good enough to solve any factorial with big numbers, until — I try factorial of 171 in Chrome console panel:

facto(171) // Infinity
facto(170) // 7.257415615307994e+306

I know that factorial of 171 should be a large number way bigger than factorial of 170, but it ain’t even close to Infinity right? Yet when I try:

facto(171)/facto(170) // Infinity

It still return Infinity as the final answer, which I immediately know that it isn’t correct. Though, we can solve the problem above algebraically like:

171! / 170! = 170! * 171 / 170! = 171 : Correct Answer, not Infinity

My question is, how would I create a function that solve a fraction of factorials algebraically?

Method (#1)

I’m a JS cultist, and I’ll do my best to prove that it capable of solving almost any problems including mathematics. Here I’ll use utility functions to help me create the final function of factorials division:

let withAs = (obj, cb) => cb(obj)

It’s a function to help me chain a value inside a function without declaring a variable.

let mul = arr => arr.reduce((a, b) => b * a)

mul([1, 2, 3, 4, 5]) // 120
facto(5) // 120

It’s a function to help me multiply each number in a given array.

let makeList = (start, stop) =>
  start > stop ? [] : [
    start, ...makeList(
      start + 1, stop
    )
  ]

makeList(2, 5) // [2, 3, 4, 5]
makeList(-2, 3) // [-2, -1, 0, 1, 2, 3]

It’s a function to help me create an array of number from ‘start’ to ‘stop’ increments by 1 recursively. I love recursion that much.

let factoDiv = (a, b) => withAs(
  mul(makeList(
    Math.min(a, b) + 1,
    Math.max(a, b)
  )), res => a > b ? res : 1 / res
)

Finally, a function whence given a numerator and divisor, shall return the division of fractional factorials. Here is how it works:

1. Make a list of numbers that start from the smallest number of the two and stop at the biggest one.
2. Multiply each number in the array
3. Test it with ternary, if a > b then return as is, else return the reciprocal

factoDiv(171, 170) // 171

Now, the function finally return the expected correct answer as 171, not Infinity.

Result

When everything combined:

let
withAs = (obj, cb) => cb(obj),

mul = arr => arr.reduce((a, b) => b * a),

makeList = (start, stop) =>
  start > stop ? [] : [
    start, ...makeList(
      start + 1, stop
    )
  ],

factoDiv = (a, b) => withAs(
  mul(makeList(
    Math.min(a, b) + 1,
    Math.max(a, b)
  )), res => a > b ? res : 1 / res
),

facto = x =>
  x === 1 ? 1 : x * facto(x - 1)

Example

facto(170) // 7.257415615307994e+306
facto(171) // Infinity
facto(171)/facto(170) // Infinity
factoDiv(171, 170) // 171
facto(6)/facto(4) // 30
facto(4)/facto(6) // 1/30 or 0.0333333
factoDiv(6, 4) // 30
factoDiv(4, 6) // 1/30 or 0.0333333

What if the problem is a fraction contains both numerator and divisor which contains more than one element? Here is the example:

6!4!/5!3! = ?
? = (6!/5!)*(4!/3!)
? = (5!6/5!)*(3!4/3!)
? = 6 * 4 = 24
factoDiv(6, 5)*factoDiv(4, 3) = 24

6!/4!3! = ?
? = 4!*5*6/4!3!
? = 30/3! = 30/6 = 5
factoDiv(6, 4)/facto(3)

Caveat

No known caveat so far, be my guest.

Method (#2)

I found another method which is much simpler and more elegant, but only works if the numerator if bigger than the divisor. It also utilize recursion.

factoDiv = (a, b) =>
  a === b ? 1 : Math.max(a, b) * factoDiv(
    Math.max(a, b) - 1, Math.min(a, b)
  )

factoDiv(171, 170) // 171
factoDiv(6, 4) // 30

But what if the divisor is bigger than the numerator?

factoDiv(4, 6) // 30
// manually reciprocate the result above to 1/30

Thanks, peace from Indonesia.