Catecon: Factorial

Prior video Catecon: Introduction.

My first machine to play on beyond some sticks to rub together (a slide rule) was an Olivetti Programma 101 with magnetic cards.

My first program, well, one with loops, was to compute factorials.

Let’s do that here, with recursion.

Given a natural number n, the factorial of n is n times the factorial of n minus one.

To begin, create a new diagram.

Given the name, say factorial, and for HTML entities let’s use n-bang.

For the description say it’s the recursively defined factorial.

To begin let’s drag the natural numbers onto the diagram.

Control-drag from it to begin a new identity morphism.

Select the morphism and edit the data.

We know zero factorial and one factorial, so let’s add that data.

Zero factorial is one, and one factorial is one.

Change the automatically generated name to n-bang.

Control-drag the morphism to create another copy.  We need this for the recursion.

Next let’s see where we can go from a natural numbers object.

Let’s pick delta under the Transforms section so we can make two copies of our original object.

We need the predecessor to setup the recursion.  Drag it over.

Fuse predecessor’s codomain with n-bang’s domain.

Compose the two and control-drag to take a copy.

Control drag from N to form an identity.

Select it and detach it.

Drag it over our composite until it turns blue.

Drop it to form the product of the two morphisms.

Fuse the product’s domain with the delta’s codomain.

Select the product’s codomain and see where we can go from there.

Multiplication looks like a good choice.  Do it.

Now fuse that codomain onto the other.

Select the three morphisms in order, then click the compose button.

We see the composite morphism appear in the same hom-set as n-bang.

Now that we have a composite representing the recursion for n-bang, select n-bang and then the composite.

Click on the recursion button and we see that the recursor has been set.

If we look at the recursively defined n-bang we see that the recursor is set.

Basically, we can think of this as each time we recurse, we add another bit of diagram to the bottom.

Talking our way through the composite, we take two copies of our original number, then decrement the first followed by recursively determining it, and then multiply the original value times that.

Perhaps we should test this.

Take a natural number object and control-drag an identity from it.

Fuse the codomain to the n-bang’s domain.

Now edit the morphism and add a range.

Start at index 0, with a range of 100, and start the codomain at zero.  We should get to 99 factorial this way.

Select that morphism followed by n-bang with a shift-click.

Hit the compose button.

Evaluate it.

That creates a new data map.  Select it and view the contents.

That looks factorially, but I think the Programma 101 had more digits.  No floating point though.

Ecmascript implementations of numerics are nominally double precision floating point, so this expires around e308.