Lovin and learnin js and ruby

Yay! Javascript and ruby are amazing! Different but both are great! Let’s take some time to look at a fun programming problem and figure it out with both languages.

I’m going to tackle Project Euler’s problem 25:

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

The best way to solve this problem is to right a single procedural set of code to spit out the answer. I don’t like doing that. It’s not practical. Let’s right a few methods/functions so we could use numbers other than 1000 if we wanted to.

First, let’s right a method/function to figure out Fibonacci numbers. We don’t need to return an array of Fibonacci numbers, we just return the Fibonacci number and the index it would be inside of the pretend array of all Fibonacci numbers.

Current goal:
Return a two element array with the first element being the Fibonacci number and the second the which Fibonacci it is. Something like [55, 10]. Because of the size of the number we’re searching for, the recursive solution is much too slow.

# Take in a number. Return that number and 
# return it's Fibonacci number.
def fib(num)
  previous_fib = 0
  current_fib = 1
  num.times do |num|
  	previous_fib, current_fib = current_fib, current_fib + previous_fib
  end
  [previous_fib, num]
end

fib(5)
=> [5, 5]
fib(10)
=> [55, 10]
fib(20)
=> [6765, 20]

Sweet. That works. We’re going to be using that array when finding Fibonacci numbers by number of digits. Let’s do it with javascript:


function fib(num) {
  var previousFib = 0;
  var currentFib = 1; 
  for (var i = 0; i < num; i++) {
    var temp = previousFib;
    previousFib = currentFib;
    currentFib = currentFib + temp
  };
  return [previousFib, num];
}

> fib(5);
[ 5, 5 ]
> fib(10);
[ 55, 10 ]
> fib(20);
[ 6765, 20 ]

Alright! We’ve got our Fibonacci calculators. The only real difference between the two versions is on line 7 of the ruby code. That allows us to avoid using a temporary value when doing assignments that have some dependence on each other. It kind of says previous_fib is equal the current value of current_fib and current_fib is equal to previous_fib’s previous value plus current value’s current value.

The next part is a pretty to write but much, much harder on the computer. Here we’ll write a function that returns the index of the Fibonacci number that has a total number of digits equal to a given number. Let’s start with some ruby:


def fib_digit_length(num)
  answers = [0,0]
  index = 1
  while answers[0].to_s.length < num
    index += 1
    answers = fib(index)
  end
  answers
end

fib_digit_length(2)
=> [13, 7]
fib_digit_length(3)
=> [144, 12]
fib_digit_length(4)
=> [1597, 17]
fib_digit_length(5)
=> [10946, 21]

# That all works and helps for testing, but a 1000 digit number is going to be brutal
# in console, so I'm going to just return the index.

fib_digit_length(1000)
=> 4782

Sweet. Problem done and the computer didn’t explode. If it had been done recursively, given the increase in time per digit calculated, and that my computer wouldn’t run out of memory(it would have), my computer would have taken over a week to compute the first 1000 digit number.

Let’s get the same thing going with javascript:

function fibDigitLength(num) {
  var answers = [0,0];
  for (var i = 0; answers[0].toString().length < num; i++) 
     answers = fib(i);
  };
  return answers;
}

> fibDigitLength(2)
[ 13, 7 ]
> fibDigitLength(3)
[ 144, 12 ]
> fibDigitLength(4)
[ 1597, 17 ]
> fibDigitLength(5)
[ 10946, 21 ]
> fibDigitLength(20)
[ 12200160415121877000, 93 ]
> fibDigitLength(21)
[ 135301852344706760000, 98 ]
> fibDigitLength(22)
[ 1.5005205362068963e+21, 103 ]
> fibDigitLength(23)
[ 1.0221638535413418e+101, 485 ]
> fibDigitLength(24)
.
..
... 4ever

canteven

And then it gets bad. Javascript ‘can’t even’ with numbers that big. I’m having trouble finding good answers on exactly what is going on here. I found a script for using really big numbers but will try to implement it another time. The function works well but the language has some limitations on what it can deal with. To be fair, I can’t even imagine when you’d really need to manipulate a number that is 1k digits long. For funsies, here’s that number:

1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816

Going back and forth between languages is a little challenging, but like everything else, it gets better and smoother with practice.

Thanks,
superandrew

Advertisements

2 thoughts on “Lovin and learnin js and ruby

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s