Bug in recursive implementation of Pascal's Triangle algorithm

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Bug in recursive implementation of Pascal's Triangle algorithm

Will Clardy
I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:

pascal(c: Int, r: Int): Int

I should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):

function pascal(c, r) {
    function loop(c, r) {
        return (c == 0) ? 1 : (loop(c - 1, r) * ((r + 1 - c) / c))
    }

    return (c * 2 > r) ? loop(r - c, r) : loop(c, r)
}

// A few tests; All pass
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 6

However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).

def pascal(c: Int, r: Int): Int = {
  def loop(c: Int, r: Int): Int = {
    if (c == 0) 1
    else loop(c - 1, r) * ((r + 1 - c) / c)
  }

  if (c * 2 > r) loop(r - c, r)
  else loop(c, r)
}

// Same tests; The last fails
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 4 !!! <-- WHY NOT 6?!

Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks!

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Bug in recursive implementation of Pascal's Triangle algorithm

Brian Smith
Hi Will

It boils down to this:

In Scala, Int / Int = Int

In ECMAScript, the result of dividing is always a Double.

Kind regards

Brian

On 12 January 2017 at 06:02, Will Clardy <[hidden email]> wrote:
I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:

pascal(c: Int, r: Int): Int

I should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):

function pascal(c, r) {
    function loop(c, r) {
        return (c == 0) ? 1 : (loop(c - 1, r) * ((r + 1 - c) / c))
    }

    return (c * 2 > r) ? loop(r - c, r) : loop(c, r)
}

// A few tests; All pass
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 6

However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).

def pascal(c: Int, r: Int): Int = {
  def loop(c: Int, r: Int): Int = {
    if (c == 0) 1
    else loop(c - 1, r) * ((r + 1 - c) / c)
  }

  if (c * 2 > r) loop(r - c, r)
  else loop(c, r)
}

// Same tests; The last fails
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 4 !!! <-- WHY NOT 6?!

Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks!

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Bug in recursive implementation of Pascal's Triangle algorithm

Will Clardy
Brian,

Thanks for the reply! I realized this morning that the problem was truncating 
integer division. I was able to fix my implementation easily in this case by moving 
parentheses around. 

def pascal(c: Int, r: Int): Int = {
  def loop(c: Int, r: Int): Int = {
    if (c == 0) 1
    else (loop(c - 1, r) * (r + 1 - c)) / c
  }

  if (c * 2 > r) loop(r - c, r)
  else loop(c, r)
}

As a follow-up question, what strategies are helpful for avoiding lurking bugs 
from precision killing integer division? I come from a background in mostly 
dynamically typed languages where division operators typically do the expected 
thing with more/less safety.

On Thursday, January 12, 2017 at 3:54:08 PM UTC-5, BrianS wrote:
Hi Will

It boils down to this:

In Scala, Int / Int = Int

In ECMAScript, the result of dividing is always a Double.

Kind regards

Brian

On 12 January 2017 at 06:02, Will Clardy <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="PQmtJxwKAAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">que...@...> wrote:
I'm working through the Functional Programming in Scala track on Coursera; one of the early exercises consists of writing a recursive algorithm to calculate an element in Pascal's Triangle for a given row and column. The function should have the following signature:

pascal(c: Int, r: Int): Int

I should say upfront that I'm not looking for help with the exercise. It was fairly easy to solve:

def pascal(c: Int, r: Int): Int = {
  if (c == 0 || c == r) 1
  else pascal(c - 1, r - 1) + pascal(c, r - 1)
}

This is simple and works, but is inefficient. I uncovered a bug while working at a (less readable) more efficient implementation, and I'm at my wit's end trying to understand it. The revised algorithm is simple enough. Here's a working version in JavaScript (written to prove that the algorithm works, and to preserve my sanity):

function pascal(c, r) {
    function loop(c, r) {
        return (c == 0) ? 1 : (loop(c - 1, r) * ((r + 1 - c) / c))
    }

    return (c * 2 > r) ? loop(r - c, r) : loop(c, r)
}

// A few tests; All pass
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 6

However, an apparently identical implementation in Scala yields unexpected results, and I can't see why. I've even resulted to manual execution with pen and paper (haven't managed to get the IntelliJ debugger working yet).

def pascal(c: Int, r: Int): Int = {
  def loop(c: Int, r: Int): Int = {
    if (c == 0) 1
    else loop(c - 1, r) * ((r + 1 - c) / c)
  }

  if (c * 2 > r) loop(r - c, r)
  else loop(c, r)
}

// Same tests; The last fails
pascal(0, 0) == 1
pascal(1, 2) == 2
pascal(0, 4) == 1
pascal(1, 4) == 4
pascal(2, 4) == 4 !!! <-- WHY NOT 6?!

Any light that can be shed would be greatly appreciated. I've only just started digging into Scala, and have been quite pleasantly surprised so far. This has been the first unpleasant surprise. I feel sure it's just a gap in my early Scala knowledge and someone more experienced will spot the issue quickly. Thanks!

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="javascript:" target="_blank" gdf-obfuscated-mailto="PQmtJxwKAAAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">scala-user+...@googlegroups.com.
For more options, visit <a href="https://groups.google.com/d/optout" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;" onclick="this.href=&#39;https://groups.google.com/d/optout&#39;;return true;">https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Bug in recursive implementation of Pascal's Triangle algorithm

Will Clardy
In reply to this post by Brian Smith
I'm deleting the original post since it included an answer to the exercise. There are plenty of places
online to look up information about integer division so it's not helpful to have this around.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.