Demystifying the doubling rule of 72

As a kid I heard about the Banker’s rule of 72 for determining the doubling period for investments. Divide 72 by whatever your interest rate is, and that’s how many years (compounding periods) it will take for your investment to double. But despite having the tools to understand it for years, I only discovered in the past couple of years why it works.

Trying the Rule of 72

4% should take 18 years to double, at 8% it should take 9 years to double, at 12% it should take 6 years to double, and at 18% it predicts 4 years to double. (All decimal numbers below are approximate)

1.04^18 = 2.0258
1.08^9 = 1.999
1.12^6 = 1.973
1.18^4 = 1.939

What you may notice is that it’s an approximation. It overestimates for lower percentages and underestimates for larger percentages. We could fudge the number 72 one way or the other to skew the error, but the fact is that it’s pretty close. 72 was likely chosen because of the large number of small prime factors – 2*2*2*3*3. Thus, 72 is evenly divisible by 2, 3, 4, 6, 8, 12, 18 and of course 1 (1.01 ^ 72 = 2.047).

As a high-school kid, I understood a little about logarithms, and I wanted to understand where this rule came from, so I started scratching some math out. The equation that I was looking for was this:

(1 + percent) ^ x = 2

…or perhaps more succinctly:
(1.p) ^ x = 2

So taking the log of both sides, simplifying and solving for x:
log(1.p^x) = log(2)
x * log(1.p) = log(2)
x = log(2)/log(1.p)

Of course I knew that log(2) was a constant and that the percentage ( p ) was the variable, but there it stayed because of that pesky log function. I never revisited this until years later when Wikipedia turned the light on (actually, it completed it by giving me the answer to my burning “why?” question.) Mind you, I had numerical analysis in college, so I had possessed what I needed all along.

The big reveal

A good approximation for the natural-log of small numbers is the number itself. As the input numbers get bigger, this approximation gets worse, but for small numbers it’s pretty good. This was revealed by the first term of the Taylor series expansion for approximating functions given the value of their derivatives. This sounds scary, but it’s really not bad at all. It’s one of the earliest things taught in numerical analysis.

Instead of showing the Taylor Series for the natural log function, let’s just test it out:

p = 0, ln 1.00 = 0, difference = 1.00
p = 1, ln 1.01 = 0.00995, difference = 1.00005
p = 5, ln 1.05 = 0.0488, difference = 1.0012
p = 8, ln 1.08 = 0.0770, difference = 1.003
p = 18, ln 1.18 = 0.1655, difference = 1.0145

The next step toward the rule

Let’s plug in the constant for the ln(2) and our rule for ln(1+p) = p, defining p as p/100 (that is p as a percent) we get:

x = ln(2)/(p/100)

(multiplying numerator and denominator by 100 to get the (p/100) part out of the denominator)
x = 100 * ln(2) / p

100*ln(2) = 69.31472 (approx)

The “rule of 69.3” isn’t as easy to use (remember the number of prime factors 72 has) and has an error that underestimates the doubling period for 1 percent and continues to underestimate the larger percentages by more and more – so shifting 69.3 a little larger gets us to the point where we overestimate some (by a small margin), moving the point where we underestimate to the larger percentages (that is, the error is in the interest rates nobody wants to pay but everyone would like to earn.)

Factorization of numbers from 69 to 76

69 = 23*3
70 = 2*5*7
71 = 71 is prime
72 = 2*2*2*3*3
73 = 73 is prime
74 = 2*37
75 = 3*5*5
76 = 2*2*19

So, 72 fits the bill for both shifting the error a little to the right – marginally underestimating some and marginally overestimating others while also being easy to use for lots of whole-number percentage interest rates.

The Sweet Spot

What we might notice is that shifting the “rule number” upward shifts the point where the rule goes from overestimating to underestimating the doubling period. There should be a percentage where the rule is exactly right. I’ve looked at the math and decided against working the formula out or using an algorithm like bisection or newton’s method and opted for a more trial-and-error approach.

The sweet spot for 72

We saw the numbers for 4 and 8 rendered results that were under for 4 and over for 8. So 6 is halfway between, the prediction for 6 is going to be 72/6 = 12 years. 1.06^12 = 2.012. That’s still a little high, so let’s go between 6 and 8, opting for 7% (this gets ugly since 72/7 = roughly 10.29), which renders 2.006. Let’s try 7.2% which we predict should double in 10 years – 1.072^10 = 2.004, closer but still a little high, so choose a little bigger 7.5? Skipping a few, the sweet spot for 72 is between 7.8 and 7.9 percent – the prediction for 7.8 is too high and the prediction for 7.9 is too low – the prediction for 7.85 which renders is too short a doubling period, so it’s between 7.8 and 7.85, we could try 7.825 which is is too long, so the answer is between 7.825 and 7.85, we could try the midpoint 7.8375 which renders too high a doubling period, so the answer is between 7.8375 and 7.85… I’m tempted to just say 7.84 is close enough, but the true sweet spot for the 72 rule is almost certainly an irrational number.

Advertisements

LINQ: using Any() to avoid iterating…

If I had a nickel every time I saw code like this:

// don’t do this…

if (query.Any()) { foreach(var item in query) { // ... } }

This is a pet-peeve of mine – for some reason the check seems to be reasonable to new LINQ users. While this is not my primary beef with this anti-pattern, the first item is iterated twice when there is one – once in the Any and once in the foreach-loop. My problem is multi-fold: the Any-check is completely unnecessary, the Any-check is more code to read and the Any-check indents the foreach-loop. I’d rather just have the foreach-loop – a loop whose loop-body only executes when there are elements in query. The “if” did not prevent unnecessary work – if anything, it caused unnecessary work and complicated the code at the same time.

LINQ: The care and feeding of LINQ operators (part 2–Any & All)

My last post was an intro to Any and All – with this post I will weave Where into the mix. I’ll warn that some of this may seem personal preference, but this post is really about what constitutes effective and idiomatic LINQ. IMHO, without having some of these ideas about good LINQ and bad LINQ is a bit like a craftsman that doesn’t care about using a chisel when a screwdriver is appropriate.

Filtered input feeding a LINQ operator

I wish I had a nickel for every time I’ve seen:

// ugh! don't do this:
items.Where(x => pred(x)).Any())

I like to think of LINQ as a pipeline that includes a Where like this as “filtered input feeding a LINQ operator.” If the no-argument LINQ operator fed by the Where also has an an overload with a single-argument predicate, then you can always use that rather than the more complex Where…Op, like so:

// do this!
items.Any(x => pred(x))

Besides being less code, it’s closer to the predicate-logic (there exists an x such that predicate) kind of language, it’s more declarative and it has a shorter pipeline chain. I think there are plenty of reasons to claim this is idiomatic & effective.

The operator doesn’t have to be just Any that is fed by Where – all of the LINQ operators that have predicate and no-predicate overloads work here: First, Last, Single, Count and of course Any.

Don’t do this: Do this:
items.Where(x=>p(x).Any() items.Any(x=>p(x))
items.Where(x=>p(x).First() items.First(x=>p(x))
items.Where(x=>p(x).Count() items.Count(x=>p(x))
items.Where(x=>p(x).Last() items.Last(x=>p(x))
items.Where(x=>p(x).Single() items.Single(x=>p(x))

…and of course their “OrDefault” overloads where they exist.

Where Feeding a LINQ Operator That Has A Predicate

Similar to Where feeding a non-predicated operator, Where feeding a predicated operator is another case where I generally like to get rid of the Where and roll its predicate into the other operator – we’ll cover rolling Where into All separately because All is special.

Illustrating with Where…Any:

items.Where(x => p1(x)).Any(x => p2(x))

Rolling Where…Any into just Any:

items.Any(x => p1(x) && p2(x))

..but of course it works for First, Last, Count and Single. It doesn’t work for SkipWhile or TakeWhile because they will end up yielding values from  the filtered sequence. Since Any and All are related, it may come as a surprise that in regard to combining Where with All, that…

All is special!

But why is All special? Consider this:

items.Where(i => i != null).All(x => x.IsFoo)

What happens if all of the items are null? The above expression will be vacuously true. However, if we combined it like this:

// NOT EQUIVALENT! Don't do this!
items.All(x => x != null && x.IsFoo)

If you have an inkling about what the right thing to do is, hold off just a second. We will derive an equivalent expression using the relationship between Any and All from the previous post and the above to arrive at an elegant solution that is correct for all predicates. We can do this by adding a not to the entire expression, changing All to Any and negating All’s predicate, like so:

General form of Where feeding All

items.Where(x => p1(x)).All(x => p2(x))

Let’s first convert this to an equivalent expression with Any instead of All :

!items.Where(x => p1(x)).Any(x => !p2(x))

From the previous section of this post, we know how to combine Where and Any; we delete Where and modify Any‘s predicate, combining the original Where predicate with Any‘s predicate by ANDing them like so:

!items.Any(x => p1(x) && !p2(x))

Now we’re ready to convert Any back to All – we do so exactly the same way we converted All to Any in our first step – we’ll also apply De Morgan’s Laws for negating Any’s predicate. In applying that we end up with the replacement rule we sat out to write (and now we know why All is special):

 // yay! We have derived our replacement rule for Where..All
items.All(x => !p1(x) || p2(x))

So let’s go back to example that threw things off:

// the original
items.Where(x => x != null).All(x => x.IsFoo)

// transform for Where..All
items.All(x => x == null || x.IsFoo)

If items is empty – this is vacuously true. If items contains only nulls, this returns true. In fact, nulls won’t cause this construct to return false – it’s the nonnull values – if any of them is not an IsFoo, then this construct will return false. Woot! It checks out!

Conclusion

With the exception of the positional predicates that Where supports, Where can always be rolled into Single, First, Last, Any, All, Count and the OrDefault overloads for first three operators (no love for TakeWhile and SkipWhile, they operate on and provide items from the filtered output of Where.) While I’m not dogmatic about this, it’s good to have this under your belt if you want to write the simplest LINQ possible.

LINQ: Any and All–part 1

LINQ’s Any and All seem simple enough in concept that one might dismiss them as common knowledge. Simple though they may be, there is still much that confuses people. With this post, I intend to start a short series on these two LINQ operators.

Relationships can be hard!

These operators are so similar that I think of them as essentially the same operation – they just use the predicate in reverse ways – to illustrate, here are the implementations, direct from MS’s reference source site (note the highlighted differences):

image

If you need a hint, the relation between the yellow highlights and the green highlights is that they’re negated. This makes it relatively easy to see the primary relationship between any and all and how they’re related:

items.Any(x => pred(x)) == !items.All(x => !pred(x))

I call this their primary relationship, but let’s also illustrate it with All on the left and the negations in the Any expression on the right:

items.All(x => pred(x)) == !items.Any(x => !pred(x))

Two more variations can be generated by negating the above expressions on each side of the above two relationship statements. Doing so effectively puts one negation in the predicate and one negation on the operator of the other side of the equals. This is why ReSharper suggests changing a !Any(x => pred(x)) to an equivalent All(x => !pred(x)) or a !All(x => pred(x)) to an Any(x => !pred(x)) in order to move the negation inside the predicate for readability purposes.

The No-Predicate-Any overload

The no-predicate Any can be thought of as being functionally identical to using a predicate that always returns true: items.Any(x => true)

One might ask, “if the predicate always answers true, why have it?” This is precisely why this no-predicate overload exists. But the dualist wonders why don’t we have a no-predicate All – we’ll get to this shortly, but first…

Vacuous Truth?”

Imagine you have a sequence of several items and you want to know whether every item satisfies a particular predicate – by definition this is the “All” operation. What happens if you ask the same All question on an empty-sequence? Should the response be true or false?

A friend says, “All of his purses are coach purses!” This is vacuously-true because he owns NO purses. Without conflict, he can also say, “All of my purses are made of cheese.” Intuitively, we want to say that “All” only makes sense when there is one or more items that we’re talking about – but this is incorrect from a predicate logic perspective. We’re tempted to think that it’s only when he gets one or more purses (or should we say ‘murses’?) that our normal intuitive language sense for “All” applies – we think, “okay, now that he actually owns a purse, we can determine whether it is a coach purse and if it’s made of cheese.” The truth at least with formal logic is that given an empty sequence, the predicate doesn’t matter – all of them satisfy the predicate – all zero of them.

If we want to write LINQ that supports our intuition we might write it like so:

items.Any() && items.All(x => predicate(x)

Which asks two things – are there any items at all, and do all items satisfy the predicate. We get a true response only when both are true.

…or you could use the one Jon Skeet provided in this Stack Overflow answer. The benefit of Jon’s method being readability and secondarily a single enumeration. The single enumeration benefits the case where .Any() could potentially has to do a lot of work to reaching the first item – the same work iterating that would be duplicated in the All. If you’re working over a standard in-memory collection rather than a query, Any() will always be fast to the point of being negligible. If you are concerned, profile to prove that it’s on the hot path.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.
Donald Knuth

Ordinarily, I don’t worry about things like this since Any and All will both return as soon as the result of their iteration is known – (no-predicate-any stops after iterating the first element, All stops after finding the first that violates the predicate or it reaches the end.)

Why isn’t there a no-predicate All like there is with Any?

What would it mean if there were an All with no predicate? We can imagine that the no-predicate-Any is the same as calling Any with a predicate that always returns true, so imagine an All called with a predicate that always returns false – that would return true only when the sequence was empty.

So we can get that behavior with: !items.Any(). Some like to define an operator “None” that does a !Any – YMMV, but I don’t find it any more readable than !Any.

Conclusion

This isn’t the last word on Any and All. There are other topics that I want to cover involving the effective use of Any/All and other operators. I observe that developers tend to grok Any, but All seems to be more of a mystery – so much so that a report on their frequency of use would far favor Any over All, even though they can be readily translated from one to the other. Next up, rolling Where’s predicate into other LINQ operators and why All is special.