Sequence processing problems

Question

Problem 1:

Sum the even numbers for the first n fibonacci numbers

Solution:

def fib(k):
 """Compute kth fibonacci number.
 >>> fib(1)
 0
 >>> fib(2)
 1
 >>> fib(11)
 55
 """
 def recursive_fib(prev, curr, k):
 if k - 1 == 0:
 return curr
 else:
 return recursive_fib(curr, prev + curr, k - 1)
 return recursive_fib(1, 0, k)
def iseven(n):
 if n % 2 == 0:
 return True
def sum_even_fibs(n):
 """Sum the first even fibonacci numbers
 >>> sum_even_fibs(11)
 44
 """
 return sum(filter(iseven, map(fib, range(1, n + 1))))
def sum_even_fibs_gen(n):
 """Sum the first even fibonacci numbers
 >>> sum_even_fibs_gen(11)
 44
 """
 return sum(fib(k) for k in range(1, n+1) if fib(k) % 2 == 0)

---

Problem 2:

List the letters in the acronym for a name, which includes the first letter of each capitalized word.

Solution:

def first(s):
 return s[0]
def iscap(s):
 return len(s) > 0 and s[0].isupper()
def acronym(name):
 """Return a tuple of the letters that form the acronym for name.
 >>> acronym('University of California Berkeley')
 ('U', 'C', 'B')
 """
 return tuple(map(first, filter(iscap,name.split())))
def acronym_gen(name):
 """Return a tuple of the letters that form the acronym for name.
 >>> acronym_gen('University of California Berkeley')
 ('U', 'C', 'B')
 """
 return tuple(w[0] for w in name.split() if iscap(w))

---

Functions fib, acronym and sum_even_fibs are written in functional paradigm and tested.

Functions acronym_gen and sum_even_fibs_gen are written in imperative paradigm and tested.

My question:

After using predefined functions split filter map in above 5 user defined functions, are the aforementioned paradigms being implemented correctly? If no, please let me know of the improvements.

• 200_success: Your sum_even_fibs_gen() and acronym_gen() are both perfectly valid functional programming, as each consists of a single expression with no side effects. I would consider them to be syntactically clearer expressions of the same goal as sum_even_fibs() and acronym().
• overexchange: @200_success state of w in acronym_gen is changing within an activation record. similarly k in sum_even_fibs_gen.
• 200_success: w refers to each of the words "simultaneously", but no mutation is occurring. That's allowable in FP. The generator is just map() with a different syntax.
• overexchange: @200_success As per python mechanics, yes, w would be pointing to new object every time. But if this programming style is moved to 'C' then w would be a memory area where the state of memory would change.
• 200_success: What's your point? At some point, all code, including FP code, gets translated into machine language, which is procedural. That doesn't make the original source code any less FP.

Answer 1

Your fib function would benefit strongly from memoization, as currently you don't reuse the values you've already calculated to save on computations, resulting in O(n^2) computation time, as each fib(k) takes O(n) on average and you do O(n) calls.

By storing the results of previous calls, you can bring total complexity down to O(n) as each consecutive call will take O(1) and you do O(n) calls.

An easy way to do this with Python 3 is to use functools lru_cache decorator as so:

from functools import lru_cache
@lru_cache(maxsize=None)
def function_to_memoize(n):

As a side note, there is a fun fact about fibonacci numbers that every 3rd one is even and the rest are odd, so you can use that to avoid checking parity. See my answer for more details.

---

As for your other answer, while you seem to have the correct code, I just would like to present an alternative solution for the sake of completeness which first extracts the first letter of every word and then filters by capitalization. I also made use of lambdas for such simple functions.

def acronym(name):
 return tuple(filter(lambda x: x.isupper(), map(lambda x: x[0], name.split())))

I would warrant that your code runs faster though as it does a map on a filtered result rather than a filter on a mapped result, as filter usually reduces the search space while map does not

• overexchange: In addition, I tried implementing range() with representation as tuple as shown in this code, but fib fails with an error: TypeError: unsupported operand type(s) for -: 'tuple' and 'int'.

Answer 2

You should convert your recursive_fib into a loop, since that is the canonical Python style

def fib(k):
 """..."""
 prev = 1
 curr = 0
 for _ in range(k, 1, -1):
 prev, curr = curr, prev + curr
 return curr

Functional style is valid, but it's not advisable unless you actually want to traverse a branching structure.

Then switch the loop around to the more idiomatic style

def fib(k):
 """..."""
 prev = 1
 curr = 0
 for _ in range(k-1):
 prev, curr = curr, prev + curr
 return curr

This removes recursion limits, but it still involves a ton of redundant work.

You actually want a stream, so I suggest instead yielding the results to make an iterator. This prevents pointless recomputation.

def fibs(k):
 """..."""
 prev = 1
 curr = 0
 for _ in range(k):
 yield curr
 prev, curr = curr, prev + curr
list(fib(10))
#>>> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

I far prefer sum_even_fibs_gen, which would now become

def sum_even_fibs_gen(n):
 """..."""
 return sum(n for n in fibs(n+1) if n % 2 == 0)

Now, note that

$$ \sum_{i=1}^n F_i = F_{n+2} - 1 $$

and that, as mleyfman points out, exactly every third Fibonacci number is even. This acts on the "real" fibonacci sequence; yours is shifted by 1.

Note that every other non-third Fibonacci number sums to the same as every third, since the sequence is

a b a+b c d c+d e f e+f

Thus, if we have fibonacci number \$F_{3n+2}\,ドル we know

$$ \sum_{i=1}^{3n} F_i = F_{3n+2} - 1 $$

and thus

$$ \sum_{i=1}^n F_{3i} = \frac{F_{3n+2} - 1}{2} $$

Therefore we can go back to the non-yielding fib and do

def fib(k):
 """..."""
 prev = 1
 curr = 0
 for _ in range(k):
 prev, curr = curr, prev + curr
 return curr
def sum_even_fibs(n):
 n -= n % 3
 return (fib(n + 2) - 1) // 2

This is way faster than before (again). But we can do better; there is a squaring version. Stealing from http://www.nayuki.io/page/fast-fibonacci-algorithms means that the whole summation takes only \$\mathcal{O}(\log n)\$ operations.

Here's a table of the maximum sum computable with a budget of 1 second to one significant figure.

original: 1000 (recursion limit)
non-recursive: 4000
iterator: 70000
formula: 300000
squaring: 5000000

Neat, eh?