Polynomial long division: Difference between revisions

Content added Content deleted
(Updated D entry)
(→‎{{header|Ruby}}: reform of the display)
Line 1,464: Line 1,464:


def degree(ary)
def degree(ary)
idx = ary.rindex {|x| x.nonzero?}
idx = ary.rindex(&:nonzero?)
idx.nil? ? -1 : idx
idx ? idx : -1
end
end


Line 1,483: Line 1,483:
g = [-3, 1, 0, 0]
g = [-3, 1, 0, 0]
q, r = polynomial_long_division(f, g)
q, r = polynomial_long_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[-42, 0, -12, 1], [-3, 1, 0, 0], [-27, -9, 1, 0, 0], [-123, 0, 0, 0, 0]]
# => [-42, 0, -12, 1] / [-3, 1, 0, 0] => [-27, -9, 1, 0] remainder [-123, 0, 0, 0]


g = [-3, 1, 1, 0]
g = [-3, 1, 1, 0]
q, r = polynomial_long_division(f, g)
q, r = polynomial_long_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[-42, 0, -12, 1], [-3, 1, 0, 0], [-13, 1, 0, 0, 0], [-81, 16, 0, 0, 0]]</lang>
# => [-42, 0, -12, 1] / [-3, 1, 1, 0] => [-13, 1, 0, 0] remainder [-81, 16, 0, 0]</lang>


Implementing the algorithms on the [[wp:Polynomial long division|wikipedia page]] -- uglier code but nicer user interface
Implementing the algorithms on the [[wp:Polynomial long division|wikipedia page]] -- uglier code but nicer user interface
Line 1,553: Line 1,553:
g = [1, -3]
g = [1, -3]
q, r = polynomial_division(f, g)
q, r = polynomial_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[1, -12, 0, -42], [1, -3], [1, -9, -27], [-123]]
# => [1, -12, 0, -42] / [1, -3] => [1, -9, -27] remainder [-123]


g = [1, 1, -3]
g = [1, 1, -3]
q, r = polynomial_division(f, g)
q, r = polynomial_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[1, -12, 0, -42], [1, 1, -3], [1, -13], [16, -81]]</lang>
# => [1, -12, 0, -42] / [1, 1, -3] => [1, -13] remainder [16, -81]</lang>


Best of both worlds: {{trans|Tcl}}
Best of both worlds: {{trans|Tcl}}
<lang ruby>def tcl_polynomial_division(f, g)
<lang ruby>def polynomial_division(f, g)
if g.length == 0 or (g.length == 1 and g[0] == 0)
if g.length == 0 or (g.length == 1 and g[0] == 0)
raise ArgumentError, "denominator is zero"
raise ArgumentError, "denominator is zero"
Line 1,568: Line 1,568:
return [[0], f] if f.length < g.length
return [[0], f] if f.length < g.length
q = []
q, n = [], f.dup
⚫
while n.length >= g.length
n, d = f.dup, g
⚫
q << Float(n[0]) / g[0]
⚫
while n.length >= d.length
n[0, g.length].zip(g).each_with_index do |pair, i|
⚫
q << Float(n[0]) / d[0]
n[0, d.length].zip(d).each_with_index do |pair, i|
n[i] = pair[0] - q[-1] * pair[1]
n[i] = Float(pair[0]) - q[-1] * pair[1]
end
end
n.shift
n.shift
Line 1,585: Line 1,584:
g = [1, -3]
g = [1, -3]
q, r = polynomial_division(f, g)
q, r = polynomial_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[1, -12, 0, -42], [1, -3], [1, -9, -27], [-123]]
# => [1, -12, 0, -42] / [1, -3] => [1.0, -9.0, -27.0] remainder [-123.0]


g = [1, 1, -3]
g = [1, 1, -3]
q, r = polynomial_division(f, g)
q, r = polynomial_division(f, g)
puts "#{f} / #{g} => #{q} remainder #{r}"
p [f, g, q, r]
# => [[1, -12, 0, -42], [1, 1, -3], [1, -13], [16, -81]]</lang>
# => [1, -12, 0, -42] / [1, 1, -3] => [1.0, -13.0] remainder [16.0, -81.0]</lang>


=={{header|Slate}}==
=={{header|Slate}}==
Retrieved from "https://rosettacode.org/wiki/Polynomial_long_division"