Long-haired programmer; loves cats and dogs but doesn't have any.

- Trailing zeroes of falling factorials
- Game Mechanics from Shadowrift
- my new filing technique is unstoppable
- Establishing a market for ideas
- Production rules for search (and lex ordering)
- Analogy problems
- Estimating debugging
- Paper and pencil collaborators
- Trying to work
- Linkdump
- Empowerment
- Understanding Ceu using Shenzhen I/O
- Pólya urn
- Little interpreters
- No Man's Sky
- The Secretary Problem
- Newsvendor problem
- Survival games
- Ego lens
- Elm Architecture in C++
- Mission and Space
- A little story engine
- Yet another coupon collector's problem blog post
- Reification
- Spreadsheets
- Underdrawing
- Linkdump
- Race games
- Links that I thought were interesting
- Links that I thought were interesting
- Modeling Shmups in Machinations and Ceu
- Modeling Pipe Dream in Machinations and Ceu
- Context Free Grammars for Learning
- SPSC.py howto
- Viva Pajaro and Wardley Mapping
- Where do objects come from? III
- Where do objects come from? II
- Stardew Valley and figure ground reversal
- Meta II by Val Schorre
- Citations, Elisions, and Arguments
- Where do objects come from?
- Protocol Buffers
- Dataflow Bench in Java
- Abstract nonsense continued
- Abstract nonsense
- A Douche-Free bio
- Wiring Idiom in C++
- Dataflow Bench in C
- Visitor Pattern Generator in C++
- First Post
- Elm Architecture in C++

```
def exp_of_b_in(b, n):
if n < b:
return 0
elif n % b != 0:
return 0
else:
return 1 + exp_of_b_in(b, n / b)
print [exp_of_b_in(2, i) for i in range(1, 20)]
def falling_factorial(x, n):
if n == 0:
return 1
else:
return x * falling_factorial(x - 1, n - 1)
print [[falling_factorial(x, n) for n in range(2, 4)] for x in range(3, 6)]
def trailing_zeroes_of_falling_factorial(x, n):
return exp_of_b_in(10, falling_factorial(x, n))
print [[trailing_zeroes_of_falling_factorial(x, n) for n in range(2, 4)] for x in range(3, 6)]
```

Is there a systematic way to transform `trailing_zeroes_of_falling_factorial`

to avoid creating very large intermediate values?

Let’s try a standard refactoring, recursion into iteration, on the recursive function `exp_of_b_in`

. For safety, let’s take the existing code as a specification, and use it to generate some clamp tests. To create a clamp test, you just generate
some characteristic output of the thing, and then copy and paste the output back into the source code, and assert that the same input should generate the same output, even after refactoring.

I’m not certain this will work, but I have to try something.

```
def exp_of_b_in(b, n):
if n < b:
return 0
elif n % b != 0:
return 0
else:
return 1 + exp_of_b_in(b, n / b)
assert [exp_of_b_in(2, i) for i in range(1, 100)] == [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0]
assert [exp_of_b_in(3, i) for i in range(1, 100)] == [0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2]
```

Getting it to work took some trial and error (I forgot that the opposite of `<`

is `>=`

not `>`

), but the clamp tests caught my bugs, and they are extensive enough that I am now convinced that this is right.

```
def exp_of_b_in(b, n):
accumulator = 0
while n >= b and n % b == 0:
accumulator += 1
n = n / b
return accumulator
assert [exp_of_b_in(2, i) for i in range(1, 100)] == [0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0]
assert [exp_of_b_in(3, i) for i in range(1, 100)] == [0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2]
```

That worked. What if we did the same transformation to the `falling_factorial`

function?

```
def falling_factorial(x, n):
if n == 0:
return 1
else:
return x * falling_factorial(x - 1, n - 1)
print [[falling_factorial(x, n) for n in range(1, 10)] for x in range(1, 20)]
assert [[falling_factorial(x, n) for n in range(1, 10)] for x in range(1, 20)] == [
[1, 0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 0, 0, 0, 0, 0, 0, 0],
[3, 6, 6, 0, 0, 0, 0, 0, 0],
[4, 12, 24, 24, 0, 0, 0, 0, 0]
[5, 20, 60, 120, 120, 0, 0, 0, 0],
[6, 30, 120, 360, 720, 720, 0, 0, 0],
[7, 42, 210, 840, 2520, 5040, 5040, 0, 0],
[8, 56, 336, 1680, 6720, 20160, 40320, 40320, 0],
[9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880],
[10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800],
[11, 110, 990, 7920, 55440, 332640, 1663200, 6652800, 19958400],
[12, 132, 1320, 11880, 95040, 665280, 3991680, 19958400, 79833600],
[13, 156, 1716, 17160, 154440, 1235520, 8648640, 51891840, 259459200],
[14, 182, 2184, 24024, 240240, 2162160, 17297280, 121080960, 726485760],
[15, 210, 2730, 32760, 360360, 3603600, 32432400, 259459200, 1816214400],
[16, 240, 3360, 43680, 524160, 5765760, 57657600, 518918400, 4151347200],
[17, 272, 4080, 57120, 742560, 8910720, 98017920, 980179200, 8821612800],
[18, 306, 4896, 73440, 1028160, 13366080, 160392960, 1764322560, 17643225600],
[19, 342, 5814, 93024, 1395360, 19535040, 253955520, 3047466240, 33522128640]]
```

OK, so we get something like this:

```
def falling_factorial(x, n):
accumulator = 1
while n > 0:
accumulator *= x
x -= 1
n -= 1
return accumulator
```

What next? Well, we could inline the two refactored functions into the `trailing_zeroes_of_falling_factorial`

function.

First we get some clamp tests around it:

```
def exp_of_b_in(b, n):
accumulator = 0
while n >= b and n % b == 0:
accumulator += 1
n = n / b
return accumulator
def falling_factorial(x, n):
accumulator = 1
while n > 0:
accumulator *= x
x -= 1
n -= 1
return accumulator
def trailing_zeroes_of_falling_factorial(x, n):
return exp_of_b_in(10, falling_factorial(x, n))
print [[trailing_zeroes_of_falling_factorial(x, n) for n in range(1, 20)] for x in range(1, 20)]
assert [[trailing_zeroes_of_falling_factorial(x, n) for n in range(1, 20)] for x in range(1, 20)] == [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 0, 0, 0],
[0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 0],
[0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]]
```

Then we might get something like this (renaming apart the two accumulators):

```
def trailing_zeroes_of_falling_factorial(x, n):
falling_factorial_accumulator = 1
while n > 0:
falling_factorial_accumulator *= x
x -= 1
n -= 1
exp_of_b_in_accumulator = 0
while falling_factorial_accumulator >= 10 and falling_factorial_accumulator % 10 == 0:
exp_of_b_in_accumulator += 1
falling_factorial_accumulator /= 10
return exp_of_b_in_accumulator
```

So now I want to fuse the two loops. I know that loop fusion is a thing, but I’m not very practiced at it, I don’t know all the rules, and so I will just have to muddle through (with clamp tests to make sure I don’t mess anything up).

My idea was would like to do something like this:

```
def trailing_zeroes_of_falling_factorial(x, n):
falling_factorial_accumulator = 1
exp_of_b_in_accumulator = 0
while n > 0:
falling_factorial_accumulator *= x
x -= 1
n -= 1
while falling_factorial_accumulator > 0 and falling_factorial_accumulator % 10 == 0:
exp_of_b_in_accumulator += 1
falling_factorial_accumulator /= 10
return exp_of_b_in_accumulator
```

My reasoning was that if we know we’re going to divide by ten out eventually, and we want to avoid big intermediate results, maybe we could divide by ten immediately? But my clamp tests alerted me that I had messed something up. After a bit of debugging, I figured out that there is a case falling_factorial_accumulator doesn’t just keep getting bigger and bigger - when we multiply by zero.

So, special casing that possibility out of the way, we end up with this:

```
def trailing_zeroes_of_falling_factorial(x, n):
falling_factorial_accumulator = 1
exp_of_b_in_accumulator = 0
if n > x:
return 0
while n > 0:
falling_factorial_accumulator *= x
x -= 1
n -= 1
while falling_factorial_accumulator > 0 and falling_factorial_accumulator % 10 == 0:
exp_of_b_in_accumulator += 1
falling_factorial_accumulator /= 10
return exp_of_b_in_accumulator
```

That while loop looks annoying. Do we really need that first part of the test?

```
def trailing_zeroes_of_falling_factorial(x, n):
falling_factorial_accumulator = 1
exp_of_b_in_accumulator = 0
if n > x:
return 0
while n > 0:
falling_factorial_accumulator *= x
x -= 1
n -= 1
while falling_factorial_accumulator % 10 == 0:
exp_of_b_in_accumulator += 1
falling_factorial_accumulator /= 10
return exp_of_b_in_accumulator
```

Tried it, apparently not. What about moving those x and n changes away, so that we can get the multiplication closer to the modulus?

```
def trailing_zeroes_of_falling_factorial(x, n):
falling_factorial_accumulator = 1
exp_of_b_in_accumulator = 0
if n > x:
return 0
while n > 0:
falling_factorial_accumulator *= x
while falling_factorial_accumulator % 10 == 0:
exp_of_b_in_accumulator += 1
falling_factorial_accumulator /= 10
x -= 1
n -= 1
return exp_of_b_in_accumulator
```

What if we renamed this long falling_factorial_accumulator just `f`

? And while we’re at it, the other accumulator `a`

?

```
def trailing_zeroes_of_falling_factorial(x, n):
f = 1
a = 0
if n > x:
return 0
while n > 0:
f *= x
while f % 10 == 0:
a += 1
f /= 10
x -= 1
n -= 1
return a
```

What can we say about multiplication followed by testing whether something divides 10? Intuitively, the output is round if the input (of the multiplication `f * x`

) is round. For example, 100 * 100 (round times round) is 10000 (very round).

This situation reminds me of an idea I’ve heard of: “all numbers can be expressed as products of prime powers”, or
“the fundamental theorem of arithmetic”. So `f`

can be expressed as `2^x*3^y*5^z*...`

and x can too.
And then when we multiply them together, the answer will be zero mod 10 if x (the exponent of 2 in f * x),
is greater than zero AND z (the exponent of 5 in `f * x`

) is greater than zero.

So if we just tracked the exponent of 2 in `f`

, and the exponent of 5 in `f`

, then we could
sortof directly track the roundness of `f`

, rather than the value of `f`

, which would cut down
on the size of those intermediate numbers.

```
def trailing_zeroes_of_falling_factorial(x, n):
f2 = 0
f5 = 0
a = 0
if n > x:
return 0
while n > 0:
f2 += exp_of_b_in(2, x)
f5 += exp_of_b_in(5, x)
while f2 > 0 and f5 > 0:
a += 1
f2 -= 1
f5 -= 1
x -= 1
n -= 1
return a
```

Now that loop, counting out 2s and 5s into the accumulator `a`

looks a little silly. Why go step
by step, when we know that the number of times round the loop will be whichever is smaller, `f2`

or
`f5`

?

```
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = 0
f5 = 0
while n > 0:
f2 += exp_of_b_in(2, x)
f5 += exp_of_b_in(5, x)
x -= 1
n -= 1
m = min(f2, f5)
a = m
f2 -= m
f5 -= m
return a
```

We don’t really need to compute those last updates to a, f2, and f5. Eliminating dead code is such a simple refactoring, that it often doesn’t get mentioned as a refactoring.

```
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = 0
f5 = 0
while n > 0:
f2 += exp_of_b_in(2, x)
f5 += exp_of_b_in(5, x)
x -= 1
n -= 1
return min(f2, f5)
```

There’s some Python syntactic sugar that might express this more tersely.

```
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = sum(exp_of_b_in(2, x) for x in range(x, x - n, -1))
f5 = sum(exp_of_b_in(5, x) for x in range(x, x - n, -1))
return min(f2, f5)
```

That’s a bit elegant, but maybe we could save a few characters by flipping the direction of the range? This is not exactly because we care about saving characters, and more that we want to make changes, and sometimes we use the excuse of saving characters to motivate making changes.

```
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = sum(exp_of_b_in(2, x) for x in range(x - n + 1, x + 1))
f5 = sum(exp_of_b_in(5, x) for x in range(x - n + 1, x + 1))
return min(f2, f5)
```

Getting the bounds on those ranges was annoying. Maybe using the python list comprehension wasn’t such a good idea.

```
def exp_of_b_in(b, n):
accumulator = 0
while n >= b and n % b == 0:
accumulator += 1
n = n / b
return accumulator
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = 0
for y in range(x - n + 1, x + 1):
f2 += exp_of_b_in(2, y)
f5 = 0
for z in range(x - n + 1, x + 1):
f5 += exp_of_b_in(5, z)
return min(f2, f5)
```

Should we inline these two calls to the helper function?

```
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = 0
for y in range(x - n + 1, x + 1):
while y >= 2 and y % 2 == 0:
f2 += 1
y /= 2
f5 = 0
for z in range(x - n + 1, x + 1):
while z >= 5 and z % 5 == 0:
f5 += 1
z /= 5
return min(f2, f5)
```

Huh. I think this is might be “going too far”. Let’s go back a couple refactorings, and call it good?

```
def exp_of_b_in(b, n):
accumulator = 0
while n >= b and n % b == 0:
accumulator += 1
n = n / b
return accumulator
def trailing_zeroes_of_falling_factorial(x, n):
if n > x:
return 0
f2 = sum(exp_of_b_in(2, x) for x in range(x - n + 1, x + 1))
f5 = sum(exp_of_b_in(5, x) for x in range(x - n + 1, x + 1))
return min(f2, f5)
```

Opinions expressed are solely my own and do not express the views or opinions of my employer.