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. |
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:
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. |
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:
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. |
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. |
Free forum by Nabble | Edit this page |