Polynomial synthetic division: Difference between revisions
Added 11l
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix link: Perl 6 --> Raku) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 5:
:<cite>In algebra, [[wp:Synthetic division|polynomial synthetic division]] is an algorithm for dividing a polynomial by another polynomial of the same or lower degree in an efficient way using a trick involving clever manipulations of coefficients, which results in a lower time complexity than [[polynomial long division]].</cite>
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F extended_synthetic_division(dividend, divisor)
‘Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.’
V out = copy(dividend)
V normalizer = divisor[0]
L(i) 0 .< dividend.len - (divisor.len - 1)
out[i] /= normalizer
V coef = out[i]
I coef != 0
L(j) 1 .< divisor.len
out[i + j] += -divisor[j] * coef
V separator = divisor.len - 1
R (out[0 .< (len)-separator], out[(len)-separator..])
print(‘POLYNOMIAL SYNTHETIC DIVISION’)
V n = [1, -12, 0, -42]
V D = [1, -3]
print(‘ #. / #. =’.format(n, D), end' ‘ ’)
V (a, b) = extended_synthetic_division(n, D)
print(‘#. remainder #.’.format(a, b))</lang>
{{out}}
<pre>
POLYNOMIAL SYNTHETIC DIVISION
[1, -12, 0, -42] / [1, -3] = [1, -9, -27] remainder [-123]
</pre>
=={{header|C sharp|C#}}==
| |||