How to resolve the algorithm Polynomial long division step by step in the Fortran programming language
How to resolve the algorithm Polynomial long division step by step in the Fortran programming language
Table of Contents
Problem Statement
Let us suppose a polynomial is represented by a vector,
x
{\displaystyle x}
(i.e., an ordered collection of coefficients) so that the
i
{\displaystyle i}
th element keeps the coefficient of
x
i
{\displaystyle x^{i}}
, and the multiplication by a monomial is a shift of the vector's elements "towards right" (injecting ones from left) followed by a multiplication of each element by the coefficient of the monomial. Then a pseudocode for the polynomial long division using the conventions described above could be: Note: vector * scalar multiplies each element of the vector by the scalar; vectorA - vectorB subtracts each element of the vectorB from the element of the vectorA with "the same index". The vectors in the pseudocode are zero-based.
Example for clarification
This example is from Wikipedia, but changed to show how the given pseudocode works.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Polynomial long division step by step in the Fortran programming language
Source code in the fortran programming language
module Polynom
implicit none
contains
subroutine poly_long_div(n, d, q, r)
real, dimension(:), intent(in) :: n, d
real, dimension(:), intent(out), allocatable :: q
real, dimension(:), intent(out), allocatable, optional :: r
real, dimension(:), allocatable :: nt, dt, rt
integer :: gn, gt, gd
if ( (size(n) >= size(d)) .and. (size(d) > 0) .and. (size(n) > 0) ) then
allocate(nt(size(n)), dt(size(n)), rt(size(n)))
nt = n
dt = 0
dt(1:size(d)) = d
rt = 0
gn = size(n)-1
gd = size(d)-1
gt = 0
do while ( d(gd+1) == 0 )
gd = gd - 1
end do
do while( gn >= gd )
dt = eoshift(dt, -(gn-gd))
rt(gn-gd+1) = nt(gn+1) / dt(gn+1)
nt = nt - dt * rt(gn-gd+1)
gt = max(gt, gn-gd)
do
gn = gn - 1
if ( nt(gn+1) /= 0 ) exit
end do
dt = 0
dt(1:size(d)) = d
end do
allocate(q(gt+1))
q = rt(1:gt+1)
if ( present(r) ) then
if ( (gn+1) > 0 ) then
allocate(r(gn+1))
r = nt(1:gn+1)
else
allocate(r(1))
r = 0.0
end if
end if
deallocate(nt, dt, rt)
else
allocate(q(1))
q = 0
if ( present(r) ) then
allocate(r(size(n)))
r = n
end if
end if
end subroutine poly_long_div
subroutine poly_print(p)
real, dimension(:), intent(in) :: p
integer :: i
do i = size(p), 1, -1
if ( i > 1 ) then
write(*, '(F0.2,"x^",I0," + ")', advance="no") p(i), i-1
else
write(*, '(F0.2)') p(i)
end if
end do
end subroutine poly_print
end module Polynom
program PolyDivTest
use Polynom
implicit none
real, dimension(:), allocatable :: q
real, dimension(:), allocatable :: r
!! three tests from Wikipedia, plus an extra
!call poly_long_div( (/ -3., 1. /), (/ -42., 0.0, -12., 1. /), q, r)
call poly_long_div( (/ -42., 0.0, -12., 1. /), (/ -3., 1. /), q, r)
!call poly_long_div( (/ -42., 0.0, -12., 1. /), (/ -3., 1., 1. /), q, r)
!call poly_long_div( (/ 2., 3., 1. /), (/ 1., 1. /), q, r)
call poly_print(q)
call poly_print(r)
deallocate(q, r)
end program PolyDivTest
You may also check:How to resolve the algorithm Fixed length records step by step in the J programming language
You may also check:How to resolve the algorithm Solve a Holy Knight's tour step by step in the J programming language
You may also check:How to resolve the algorithm Letter frequency step by step in the SIMPOL programming language
You may also check:How to resolve the algorithm Arithmetic evaluation step by step in the Delphi programming language
You may also check:How to resolve the algorithm Index finite lists of positive integers step by step in the Ruby programming language