Thursday, September 26, 2013

The Sum of Even Fibonacci Numbers

A co-worker showed me the following problem last night:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
If you jump too fast to your early CS101 knowledge you might bang out a recursive fibonacci function to get yourself started (using Ruby as an example):

def fib(n)
  return 0 if n==1
  return 1 if n==2
  return fib(n-1)+fib(n-2)

But that's not terribly efficient in this problem, where you'll end up calculating and recalculating the fibs all the way up to 4 million.

If you spot that the recursion will just do an absolute number on your stack management and want to get it out of there you can write the function without it:

def fib(n)

  prev = 0
  curr = 1
  (n - 1).times do
    curr, prev = prev+curr, curr

But you're still going to calculate too many numbers and end up with a solution that is O(N^2) because every time you move to position N your function is going to recalculate everything from 1 to N-1.

Instead, don't abstract the function.  Treat it like the formula that it is, and write it in a single loop.  You are going to be calculating your variable N using the N(x) = N(x-1)+N(x-2) formula, until N>4000000.  Along the way, if N is even, add it to your growing sum:

first = 0
second = 1
sum = 0
while (second < 4000000) do
  sum += second if second.even?
  temp = second
  second = first + second
  first = temp
puts sum

Did you get 4613732?  You could clean up that code a bit and there's tricks to avoid that temp variable but I want to get to a better solution.  The one above calculates all the Fibonacci numbers less than 4 million, which means it goes through the loop 33 times.

We can do better.  If you look closely at the fibonacci sequence you may spot a pattern in the even numbers.  Did you notice that every 3rd number is the even one?  Which makes sense because once you bring even a single odd number into the pattern it's going to go the same way -- even plus odd equals odd, odd plus odd equals even.  So the Fibonacci sequence goes odd even odd odd even odd odd even odd where each even number is wrapped with odd numbers.

How can we use this?  Well this means if we know that fib(N) is even, we want to jump to fib(N+3) without worrying about the two in the middle.  So instead of looping over them why not just calculate them while we're here?  I'm going to use the sequence 5,8,13,21,34 as an example.  If I'm on 8, I want to calculate 34:

Given fib(x)=8
Given fib(x-1)=5
Calculate fib(x+1) = (8+5)
Calculate fib(x+2) = fib(x+1)+fib(x) = (8+5)+8  = (8*2 + 5) = fib(x)*2 + fib(x-1)
Calculate fib(x+3) = fib(x+2)+fib(x+1) = ((8+5)+8)+(8+5) = (3*8 + 2*5) = fib(x)*3 + fib(x-1)*2

Still with me?  So as long as I have fib(x) and fib(x-1) I can jump to fib(x+3) with some multiplication.

So now I can go through the loop like this:

x1 = 1

x  = 2
sum = 0
while (x < 4000000) do
      sum += x
      n = 3*x+2*x1
      x1 = 2*x+x1
      x = n
print "Your total is #{sum}"

Same result, only this time we bounced up to 4 million in just 10 hops.

Again, we could probably make it even more efficient than that by considering the actual cost of each math operation - I added some multiplications but now I'm also no longer testing for even numbers, so maybe it's a wash. I was mostly interested in showing that whole "even numbers every third so only jump by 3s and don't test for even" pattern.

I wanted to document this approach since I haven't seen it yet as one of the standard answers.  Enjoy.

Tuesday, September 17, 2013

Copy And Paste Between Two Devices

If you're a developer, this has probably happened more than once. You're working on two devices that are physically right next to each other, yes? Maybe, like me, you've got your iPad next to your laptop.  And inevitably you find a link on your laptop that you want on your iPad.  Blah.  What's the fastest way to get it from one to the other?

Sure you could mail it to yourself, or drop it in DropBox, or even maybe type it directly into the secondary device.  All too much bother.

Run an instant messaging program of some sort on both devices (like AIM).  IM the message to an understanding friend.  Now go over to your secondary device and fire up the conversation.  Your message, link included, will be there.  

Totally hacky but it's the fastest way I've yet found!

Friday, February 22, 2013

Array Sampling Without Repeating [Ruby]

I've often come across the problem of random sampling in situations where you don't want repeats.  For instance say you've got a list of the user's MP3 files and you are playing them randomly.  You've just played a song and you choose another random one.  It's easy to say "Don't pick the same one that you just picked."  And with a little work you could pick an N and say, "Don't repeat a song in the last N songs."

But you also don't want to say "Don't repeat any songs until all the songs are played", because if the user's got 500 songs in their library it'll be a long time before they hear their favorite song again.  What you really want is just something that says "Make it less likely to pick this song too too frequently."

So, here's the idea I finally came up with.  Say that you've got an array of files to work with, regardless of what is in them.  In Ruby you can just ask for file  = files.sample to get a random element out of the array.

Now what?  We go and do what we want with file, but now we want to assure that this is less likely to be called in the near future (and, preferably, absolutely guarantee that it is not called within the next N samples).

Start by snipping file out of filenames and moving it to the end of the array:

files <<= files.delete(file)

Try it:

(main)> files=["foo", "bar", "baz", "quux"]
=> ["foo", "bar", "baz", "quux"]
(main)> file = files.sample
=> "bar"
(main)> files <<= files.delete(file)
=> ["foo", "baz", "quux", "bar"]

So what?  The sample method is equally likely to pick any item in the array, right?

What if we tell it not to?  What if we tell it to only sample a portion of the array?

file = files[0..files.size>>2].sample

Here, we're saying to only get samples out of half the array.  So when a sample is chosen and moved to the back, we've established that there's no way this sample can be repeated until at least N/2 samples have been taken.

Depending on your N you might want to do something like N*0.90 or something (if N is a thousand maybe only 100 samples have to go by before it's ok to repeat).  

It's a little trick, but I think it's important.  I've got an app I'm working on that chooses random quotes, placing them on random images.  It bothers me when I know that I've got over 500 quotes in the database, and the user sees a repeated quote after 4 refreshes of the page.  So now they won't, now it'll take hundreds of refreshes before they see a repeat. Truthfully I'll probably switch that over to cap at 100.