Throw the cat among the pigeons

[Steven D'Aprano]

On Wednesday 06 May 2015 14:05, Steven D'Aprano wrote:

[...]

Here are those anomalous timing results again:

> code = "fact(50000)"
> t1 = Timer(code, setup="from __main__ import factorial_while as fact")
> t2 = Timer(code, setup="from __main__ import factorial_reduce as fact")
> t3 = Timer(code, setup="from __main__ import factorial_forloop1 as fact")
> t4 = Timer(code, setup="from __main__ import factorial_forloop2 as fact")
> for t in (t1, t2, t3, t4):
>     print(min(t.repeat(repeat=3, number=2)))
> 
> 
> which takes about two minutes on my computer, and prints:
> 
> 8.604736926034093  # while loop
> 10.786483339965343  # reduce
> 10.91099695302546  # for loop
> 10.821452282369137  # silly version of the for loop
[...]
> What is surprising is that for very large input like this, the while loop
> is significantly faster than reduce or either of the for-loops. I cannot
> explain that result.

I re-ran the results on a different computer, and got similar results:

7.364120149984956
9.26512472704053
9.141491871327162
9.16900822892785

The while loop is surprisingly faster for calculating fact(50000). A thought 
came to mind: the while loop is different from the other three versions, in 
that it performs the multiplications from n down to 2, rather than 2 up to 
n. Maybe that has something to do with it?

Introducing version five of the factorial:

def factorial_reduce2(n):
    assert n >= 0
    return reduce(mul, range(n, 1, -1), 1)

t5 = Timer(code, setup="from __main__ import factorial_reduce2 as fact")
for t in (t1, t2, t3, t4, t5):
    print(min(t.repeat(repeat=3, number=2)))



And results:

7.36792928725481  # while loop
9.271950023248792  # reduce, counting up
9.14769447594881  # for loop
9.154150342568755  # silly for loop
7.430811045691371  # reduce, counting down


My interpretation of this is that the difference has something to do with 
the cost of multiplications. Multiplying upwards seems to be more expensive 
than multiplying downwards, a result I never would have predicted, but 
that's what I'm seeing. I can only guess that it has something to do with 
the way multiplication is implemented, or perhaps the memory management 
involved, or something. Who the hell knows?


Just to be sure:

def factorial_forloop3(n):
    assert n >= 0
    result = 1
    for i in range(n, 1, -1):
        result *= i
    return result

t6 = Timer(code, setup="from __main__ import factorial_forloop3 as fact")
print(min(t6.repeat(repeat=3, number=2)))


which prints 7.36256698705256.


Lesson to be learned: what you think is important may not be, and what you 
think is irrelevant may be.



Historical fact: for a period of about 60 years, long after the trick to 
curing and preventing scurvy was known, the British navy suffered greatly 
from scurvy again (although not to the same degree as they had been in the 
17th and 18th centuries). The problem was due to confusion between *lemons* 
and *limes*. The navy started by using the term "lime" for both lemons and 
sweet limes from the Mediterranean, as well as West Indian limes: three 
different citrus fruit. To cut costs and encourage British commerce, the 
navy gradually stopping buying lemons from Spain and swapped over almost 
entirely to West Indian limes. Unfortunately limes, and especially West 
Indian limes, have significantly less Vitamin C than lemons, and the 
sailors' daily allowance was about 75% less effective on ships that used 
limes than for those that used Spanish lemons. Scurvy, which had practically 
be eradicated in the 1850s and 60s, returned, and was a significant factor 
in World War One. (Especially for the French and Russian armies.)

This simple confusion wasn't sorted out until the 1920s, long after Vitamin 
C was isolated and named. Apparently nobody noticed, or cared, that the two 
different fruit tasted different and looked different, or concluded that 
perhaps they had different medicinal properties.

But then, for many decades, vinegar and dilute sulphuric acid were 
recommended as cures for scurvy *solely* on the basis that they were acidic 
just like proven cures oranges, lemons and sauerkraut.



-- 
Steven