How to resolve the algorithm Polynomial long division step by step in the Fortran programming language

Published on 12 May 2024 09:40 PM

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