Calculating the Number of Trailing Zeros in a Factorial

The factorial function, denoted \( n! \), where \( n \in \mathbb{Z}^* \), is defined as follows: \[ n! = \begin{cases} 1 & \text{if $n = 0$,} \\ n(n - 1)! & \text{otherwise}. \end{cases} \] In the case of \( n = 10 \), \( 10! = 3\,628\,800 \). Note that that value has two trailing zeros. When \( n = 20 \), \( 20! = 2\,432\,902\,008\,176\,640\,000 \) and has four trailing zeros. Can we devise an algorithm to determine how many trailing zeroes there are in \( n! \) without calculating \( n! \)?

Let us define a function \( z : \mathbb{N} \to \mathbb{N} \) that accepts an argument \( n \) that yields the number of trailing zeros in \( n! \). So, using our two examples above, we know that \( z(10) = 2 \) and \( z(20) = 4 \). Now, what is \( z(100) \)?

An integer \( a \) has \( k \) trailing zeros iff \( a = b \cdot 10^k \) for some integer \( b \). Now, the prime factors of \( 10 \) are \( 2 \) and \( 5 \). So, what if we consider the prime factors of each factor in a factorial product? For example, consider the first six terms (after \( 1 \)) of \( 100! \) and their prime factors. We omit \( 1 \) because of its idempotence: \[ \begin{align} 2 &= 2 \\ 3 &= 3 \\ 4 &= 2^2 \\ 5 &= 5 \\ 6 &= 2 \cdot 3 \\ 7 &= 7 \end{align} \] We see that \( 7! \) contains one \( 5 \) and (more than) one \( 2 \). Therefore, \( 7! \) contains a factor of \( 10 \), so we should expect there to be one trailing zero in \( 7! \). And we see that \( 7! = 5040 \), which does indeed have one trailing zero. This suggests that we could, for any integer \( n \) in \( n! \), cycle through the integers from \( 2 \) to \( n \), finding the prime factorization of each integer, and counting pairs of \( 2 \) and \( 5 \) that we find.

You might have noticed from our example of \( 7! \) that there are four \( 2 \)s and only one \( 5 \). Consider that there are \( n/2 \) even factors in \( n! \)—that is, every other integer factor of \( n! \), starting at \(2\), is even. So there are \( n/2 \) even factors. Each of these has at least one \( 2 \) in its prime factorization, and many of them have more than one. Now consider how many factors of \( 5 \) there are in \( n! \): there are, in fact, \( n / 5 \). So, we can see that, for every \( 5 \) we find in \( n! \), there is a \( 2 \) we can match with it. This suggests that we only need count the \( 5 \)s and not the pairs of \( 2 \) and \( 5 \).

This now suggests an algorithm, presented here in Java:

Using this algorithm, we find that \( z(100) = 24 \).

Generate a Zero-Valued UUID

Say you want a UUID of 00000000-0000-0000-0000-000000000000, but you just want to make one fast, without having to find out the number and grouping of digits. Here's a way to do it:

The Beauty of Scheme

Bertrand Russell once noted that

Mathematics, rightly viewed, possesses not only truth, but supreme beauty—a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry.

I think much the same can be said of code, especially code written in certain languages. There is something so elegantly simple and beautiful about Scheme (and Racket), for example, that shares the same aesthetics of mathematics.

A Human-Usable URL Parser for Python

Yes, there is the urlparse module in Python 2.7 and the urllib.parse function in Python 3, but each of them just creates a 6-tuple of URL parts, and it's up to you to know that the query part, for example, is at position 4.

So here's a neat little wrapper around that functionality which gives named fields to each part:

So, to get the query part, you just do parsed_url.query instead of parsed_url[4].

Making System.Data.SQLite Work in an NServiceBus Endpoint

Today a colleague and I worked on getting an an NServiceBus endpoint in a .NET 4.0 project that referenced System.Data.SQLite to work properly. It turns out that this is not as straightforward as it may seem.

The System.Data.SQLite binaries are targeted for the .NET 2.0 runtime. When referencing a .NET 2.0 mixed mode assembly in a .NET 4.0 project, additional configuration is required:


OK, that's fine. But when running an NServiceBus endpoint in the NServiceBus.Host.exe executable, it seems that this setting in App.config does not get applied in the context of NServiceBus.Host.exe. So, to get this to work, we had to turn the NServiceBus endpoint into a console application with a Main method that used reflection to invoke the Main method of NServiceBus.Host.exe. Doing this enables the above setting to be applied in the context of NServiceBus.Host.exe.

It took us the better part of a day to figure this out, so I'm memorializing it here for (my own) future reference.

Generate Test Files From the Command Line

Note to self: I had to generate some files quickly to test the behavior of the .NET FileSystemWatcher. This little bash script will create 6 zero-filled files of of size \( 2 \times 10^i \) KiB, where \( i \in \{0, 1, \dots, 5\} \).

Retrying Code Execution

I have a bit of code I'm working on at work that makes use of an HTTP endpoint to notify a legacy system of certain events. Because the network is not reliable, we have to handle the case when the network may be down. In this situation, it means to try again a few times, after which the processing request goes into an error queue, where it can be handled manually. So, I started out with something like this:

This calls the HTTP endpoint up to five times. If one of those times succeeds, it returns the result and stops trying. If it gets to the sixth time, it gives up.

Now, in my project, I have several of these types of calls to make. Much of the above code, namely the exception handling and flow control stuff, is common to all of them. So, using some functional .NET and an extension method, we can do this:

This will attempt to execute and return the value of func up to times times, and give up after that. With this extension method, we can now put our endpoint-calling code in a Func<int> and tell it to try to call the endpoint up to five times, like this: Now, is this the best way to do this? Maybe; maybe not. It's just something I've been toying around with in my attempts to eliminate duplication of the aforementioned ugly flow control code. I'll have to walk around in these shoes for a while and see whether I like them.

IE Doesn't Support the trim() Method(!)

Here's yet another shocker from the half-baked world of Internet Explorer. Start up IE 8. Press F12 or start the Developer Tools. Then, click the Script tab and then the Console tab on the right pane. At the command line at the bottom, type
[sourcecode language="javascript"]
" this has padded whitespace ".trim();
[/sourcecode]
press Enter, and behold:



Insane! Thankfully, the folks at jQuery have taken care of this.

Java as DSL

I love it:

http://twitter.com/#!/avalanche123/status/7062890318143488

Generate a Version 4 UUID With Javascript

[sourcecode language="javascript"]
function uuid4() {
return "xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx"
.replace(/[xy]/g, function (c) {
var r = Math.random() * 16 | 0, v = c == "x" ? r : r & 0x3 | 0x8;
return v.toString(16);
});
}
[/sourcecode]

From Mvc2.TaskUI by Jonathan Oliver.

Roll Your Own Map/Reduce in Javascript

I’ve been working on a very Javascript-heavy UI that allows the user to manipulate collections of objects. To ease the task of manipulation, I created a few methods on Array.prototype, which I rolled into a file I call iterable.js:

[sourcecode language="javascript"]
var Iterable = {
func: {
predicate: {
TRUE: function (x) { return true; }
}
}
};

Array.prototype.forEach = function (fn) {
for (var i = 0; i < this.length; i++)
fn(this[i]);
};

Array.prototype.filter = function (pred) {
var result = [];
this.forEach(function (x) {
if (pred(x))
result.push(x);
});

return result;
};

Array.prototype.distinct = function () {
var result = [];
this.forEach(function (x) {
if (!result.any(function (y) { return y == x; }))
result.push(x);
});

return result;
};

Array.prototype.any = function (pred) {
pred = pred || Iterable.func.predicate.TRUE;

for (var i = 0; i < this.length; i++)
if (pred(this[i]))
return true;

return false;
};

Array.prototype.indexOf = function (expr) {
if (!(expr instanceof Function))
expr = function (x) { return x == expr; };

for (var i = 0; i < this.length; i++)
if (expr(this[i]))
return i;

return -1;
};

Array.prototype.singleOrNull = function (pred) {
var filtered = this.filter(pred);
if (filtered.length == 0)
return null;
if (filtered.length > 1)
throw "More than one element returned.";

return filtered[0];
};

Array.prototype.map = function (fn) {
var mapped = [];
this.forEach(function (x) { mapped.push(fn(x)); });
return mapped;
};

Array.prototype.groupBy = function (sel) {
var groups = [];

this.forEach(function (x) {
var group = groups.singleOrNull(function (y) { return y.key == sel(x); });
if (!group)
groups.push({ key: sel(x), members: [x] });
else
group.members.push(x);
});

return groups;
};
[/sourcecode]

Note that this not particularly complete; for example, you’ll see that there is no implementation of a reduce function. It’s not here because I have not needed it in my project yet, nor am I likely to. But it would be easy to implement:

[sourcecode language="javascript"]
Array.prototype.reduce = function (fn) {
    if (this.length == 1)
        return this[0];
    return fn(this[0], this.slice(1).reduce(fn));
};
[/sourcecode]

Now, I’m aware of Underscore and others, so why did I do this? For two reasons, mainly: I only needed a subset of the functions that those libraries offer, and besides, it was fun.

The .Net HashSet

I’m relatively new to .Net, coming from the world of Java. Now, the documentation of the HashSet class says, “The HashSet(Of T) class provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order.” Fair enough, except that the HashSet class preserves insertion order. Furthermore, set1.Equals(set2) will return false even when the two sets contain the same elements but in a different insertion order.

This doesn’t sound like set semantics to me. Fortunately, you can remedy this with a simple extension method and LINQ:

[sourcecode language="csharp"]
public static bool SetEquals<T>(this HashSet<T> me, HashSet<T> other)
{
return me.All(other.Contains) && other.All(me.Contains);
}
[/sourcecode]

As you can see, the LINQ expression on line 3 is equivalent to the definition of set equality. Of course, the parameters to this method could be of type ICollection<T> or something for more genericity.