Newton's Method Polynomial solver in Ruby

Question

I am learning Ruby programming from "Learn Ruby the Hard way" and I am doing the "Ruby koans".

I have heard a little bit about "Idiomatic" Ruby but I don't know much about it. How can I make it more idiomatic?

# Program to solve polynomials
def solve(coeff)
 coefficients = []
 coeff.each{ |a|
 coefficients.push a.to_f
 }
 diffrentiate = []
 n = 0
 coefficients.reverse_each { |a| 
 diffrentiate.unshift n*a
 n += 1
 }
 diffrentiate.pop
 return newton(coefficients,diffrentiate,-1)
end
def newton(coefficients,diffrentiate,initialvalue)
 x = initialvalue
 10.times { |n| 
 x -= evaluate_polynomial(coefficients,x)/evaluate_polynomial(diffrentiate,x)
 }
 return x
end
def evaluate_polynomial(coefficients,x)
 n = 0
 value = 0
 coefficients.reverse_each { |a| 
 value += a*x**n
 n+=1
 }
 return value
end
puts solve ([1,0,0,0,-1,1])

• 13aal: There's nothing wrong with your code, an if you're just learning then just make it run and ask for tips on how to make it better. Idiomatic programming can be tricky and chances are with your coding up there, you'll probably get about twelve different answers that are the same written differently, for an example see this: stackoverflow.com/questions/1364113/… Ruby is all about being easy to read and write. Just have fun with it, that's what counts and never let anybody tell you that you're wrong.

Answer 1

1. Use do...end instead of {...} for multi-line blocks.

2. return is implicit at the end of a method.

3. differentiate is a verb. derivatives is the plural noun you're looking for when naming the array.

4. Use Ruby's array methods (map, reduce, and friends) to your advantage.

5. Don't modify external variables from inside a block if you can avoid it. I.e. don't do things like n += 1, or x -= .... A combination of with_index and reduce should do the same trick more neatly.

6. There's some repetition in your handling of the order of coefficients (i.e. the n += 1 in the blocks). It'd be nice to get rid of that.

7. It'd be nice to specify the number of iterations the approximation should use.

Here's a pretty direct translation of your solution:

# Add a method to Array which zips the array with the index
# of each element in reverse order
class Array
 def zip_reverse_index
 zip((0...count).to_a.reverse)
 end
end
# Use a *-splat to make the method variadic
def solve(*coefficients)
 coefficients.map!(&:to_f)
 derivatives = coefficients.zip_reverse_index.map { |n, i| n * i }
 newton(coefficients, derivatives[0...-1])
end
# Added some (optional) arguments
def newton(coefficients, derivatives, iterations = 10, initial = -1)
 iterations.times.reduce(initial) do |x, i|
 x -= evaluate_polynomial(coefficients, x) / evaluate_polynomial(derivatives, x)
 end
end
# A simpler implementation using reduce
def evaluate_polynomial(coefficients, x)
 coefficients.zip_reverse_index.reduce(0) do |sum, (c, n)|
 sum += c * x ** n
 end
end

---

Here's a different version that keeps everything in 1 method:

def newton_raphson(coefficients, intial = -1, iterations = 10)
 evaluate = -> (array, x) do
 array.reduce(0) { |sum, (c, ord)| sum += c * x ** ord }
 end
 coefficients = coefficients
 .map(&:to_f) 
 .zip((0...coefficients.count).to_a.reverse)
 derivatives = coefficients.map { |c, ord| [c * ord, ord - 1] }[0...-1]
 iterations.times.reduce(intial) do |approx, _|
 approx -= evaluate[coefficients, approx] / evaluate[derivatives, approx]
 end
end

It's pretty long for a Ruby method, but some of the methods in the other implementation seemed too specific to keep around in the global scope (and the Array mixin also seemed a little heavy-handed).

---

Edit: as @jQweirdy mentioned in the comments, this could also be solved with a class, but I was hesitant to add a class just for one method. But there are a few things here, that might be generically useful for Polynomial class. So here's an example:

class Polynomial
 attr_reader :coefficients
 def initialize(*coefficients)
 @coefficients = coefficients
 end
 def evaluate(x)
 coefficients.zip(ordinals).reduce(0) do |sum, (n, i)|
 sum += n * x ** i
 end
 end
 def derivative
 @derivative ||= begin
 derivatives = coefficients.zip(ordinals)[0...-1].map { |n, i| n * i }
 self.class.new(*derivatives)
 end
 end
 def order
 coefficients.count - 1
 end
 def ordinals
 (0..order).to_a.reverse
 end
 def newton_raphson_approximation(iterations = 1, initial = -1)
 iterations.times.reduce(initial) do |x, _|
 x -= evaluate(x).fdiv(derivative.evaluate(x))
 end
 end
end

• Jono: isn't ruby 'idiomatically' object oriented? Couldn't you change your code to be more OO (like the first example) without the 'public methods floating about? Maybe a Polynomial class?
• Flambino: @jQwierdy I saw your answer before it was removed. And yes, it could be put into a class. However, here the goal is only to implement the Newton-Raphson approximation, so you're looking at a function rather than a class with methods. It's pure input → output with no state being kept. But yes, it could be a class. I'd just like to add few more polynomial-manipulation methods to "justify" the class. In this case, derivatives could be such a method - the usefulness of something like that is not exclusive to the Newton approximation.
• Jono: I get what you're saying, and I love functional programming but you're going against the "send messages" OO part of ruby - aren't you? Even stateless classes, or a non-instatiatable class would be better than floating methods - wouldn't it?
• Flambino: @jQwierdy Sure, certainly better than methods floating around in global scope. But that's also why I added the alternative that just keeps everything in 1 method, just to contain it. There are many ways to structure all of this. This was a learning project according to OP, not something part of a larger code base, so even keeping things in the global scope would be ok for now. I just looked at micro level (how to produce the desired result with different code) and less at the macro level (how to structure the thing). So you're right - it just seemed out-of-scope for this review.
• Jono: Fair enough! Thanks for the detailed response. :-)