Why is my subfactorial function off by one?

Question

I'm working on implementing a subfactorial function in JavaScript to calculate the total number of derangements possible for n elements, and I seem to have screwed something up. My calculation always seems to be one high, or one low. What did I screw up? Is it a rounding error?

function subfactorial (x) {
  x = parseInt(x);
  var i;
  var sub = 0;
  var sum = 0;
  sum += factorial(x);
  for (i = 0; i < x; i++) {
    sub += (Math.pow(-1, i)/factorial(i));
  }
  return sum * sub;
}

function factorial (y) {
  var negative = y < 0;
  y = parseInt(Math.abs(y)); // Ints only
  var acc = 1;
  for (y; y > 0; y--) {
    acc *= y;
  }
  return negative ? -acc : acc;
}

function getSubfactorial () {
  var val = document.getElementById('subfac').value;
  document.getElementById('result').innerHTML = subfactorial(val);
}

<label for="subfac">Subfactorial input:</label>
<input type="number" id="subfac">
<button type="button" onClick="getSubfactorial()">Get Subfactorial</button>
<div id="result"></div>

For example, subfactorial(3) returns 3, when the answer should be 2. subfactorial(4) returns 8, when the answer should be 9. subfactorial(5) returns 45 (with a floating point rounding error) when the answer should be 44, and so on, and so forth. It seems to alternate being too low and too high between even and odd numbers respectively.

The formula I'm using comes out to be this:

In TeX:

!x = x! \sum_{k=0}^{x}\frac {(-1)^k}{k!}

Rendered TeX:

Michael Lorton · Accepted Answer · 2016-05-03T02:06:39.317

7

You're going to laugh:

for (i = 0; i < x; i++) {

That not what the Sum symbol means. It should be

for (i = 0; i <= x; i++) {

Also, that is the most literal-minded way to implement subfactorial imaginable. The exponentiation is just a way to represent "oscillate between positive and negative one" -- but in Javascript, there are about 10 better ways to do that. And there is no reason to use (or worry about) floating-point. Instead of calculating 1/k! and then multiplying by x!, calculate x!/k!, which can be done as

var factDiv = function(x, k) {
  return (k >= x) ? 1 : (x * factDiv(x-1,k)); 
}

And then subfactorial() can be defined as

var subfactorial = x => {
  var p = 1;
  var sum = 0;
  for (var k=0; k <= x; k++) {
    sum += p * factDiv(x, k);
    p *= -1;
  }
  return sum;
}

edited May 03 '16 at 02:06

answered May 03 '16 at 01:24

Michael Lorton

43,060
26
103
144

I can't believe I missed that. I should have paid more attention in math class. I completely forgot that sum's upper bound is inclusive. Thanks so much! – Brandon Anzaldi May 03 '16 at 01:27
@BrandonAnzaldi You're cool for missing ur math classes. I haven't been in one. And I don't even know how to read that thing. :( – choz May 03 '16 at 01:29
1

@choz Haha. As daunting as it looks, it basically rolls out to some relatively basic code. I haven't touched math since High School. :P – Brandon Anzaldi May 03 '16 at 01:33
@Malvolio What are parameters `x`, `k`, passed to `factDiv`? – guest271314 May 03 '16 at 01:36
2

@guest271314 -- they are the same as `x` and `k` in the original question: the argument to subfactorial and an iterator. – Michael Lorton May 03 '16 at 02:01
1

@BrandonAnzaldi -- I made it a little more basic in my answer. – Michael Lorton May 03 '16 at 02:07
@Malvolio Looks awesome :) Thanks so much for all your insight. – Brandon Anzaldi May 03 '16 at 03:16

score 3 · Answer 2 · answered May 03 '16 at 01:24

The sum goes from x=0 to x included. Change the exit condition of the for loop

function subfactorial (x) {
  x = parseInt(x);
  var i;
  var sub = 0;
  var sum = 0;
  sum += factorial(x);
  for (i = 0; i <= x; i++) {
    sub += (Math.pow(-1, i)/factorial(i));
  }
  return sum * sub;
}

function factorial (y) {
  var negative = y < 0;
  y = parseInt(Math.abs(y)); // Ints only
  var acc = 1;
  for (y; y > 0; y--) {
    acc *= y;
  }
  return negative ? -acc : acc;
}

function getSubfactorial () {
  var val = document.getElementById('subfac').value;
  document.getElementById('result').innerHTML = subfactorial(val);
}

<label for="subfac">Subfactorial input:</label>
<input type="number" id="subfac">
<button type="button" onClick="getSubfactorial()">Get Subfactorial</button>
<div id="result"></div>

Yup. That's my problem. I completely forgot that sum's UB is inclusive. I haven't been in math class in forever. I honestly don't know why I didn't try that first. But thanks for your answer! — Brandon Anzaldi, May 03 '16 at 01:28

score 2 · Answer 3 · answered May 03 '16 at 01:35

2

This seems to fix it.

for (i = 0; i <= x; i++) {
    sub += (Math.pow(-1, i)/factorial(i));
}

Change the loop to i <= x. Still some rounding issues though. Probably a javascript thing. Looks like it gets the right numbers now though.

answered May 03 '16 at 01:35

Spellapeaka

21
2

Not so much a JavaScript thing as it is a [floating point thing](http://stackoverflow.com/a/588014/1905944), but you are indeed correct. I was missing the inclusive upper bound on the for loop. – Brandon Anzaldi May 03 '16 at 01:40
Has nothing to do with Javascript or floating point. It was the definition of the function. The summation is from 0 to x, not 0 to x-1. – Michael Lorton May 03 '16 at 02:00
@Malvolio I should have specified I was specifically referring to `Still some rounding issues though.`. – Brandon Anzaldi May 03 '16 at 19:00
1

@BrandonAnzaldi -- rounding errors are inherent in the use of floating point, which is why you should avoid it whenever possible (as it is here). – Michael Lorton May 03 '16 at 22:50
@Malvolio No arguments here. – Brandon Anzaldi May 03 '16 at 22:52

Why is my subfactorial function off by one?

3 Answers3