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

Published on 12 May 2024 09:40 PM
#Smalltalk

How to resolve the algorithm Polynomial long division step by step in the Smalltalk 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 Smalltalk programming language

Source code in the smalltalk programming language

Object subclass: Polynomial [
  |coeffs|
  Polynomial class >> new [ ^ super basicNew init ]
  init [ coeffs := OrderedCollection new. ^ self ]
  Polynomial class >> newWithCoefficients: coefficients [
    |r|
    r := super basicNew.
    ^ r initWithCoefficients: coefficients
  ]
  initWithCoefficients: coefficients [ 
    coeffs := coefficients asOrderedCollection.
    ^ self
  ]
  / denominator [ |n q|
    n := self deepCopy.
    self >= denominator
      ifTrue: [
        q := Polynomial new.
        [ n >= denominator ]
          whileTrue: [ |piv|
 	    piv := (n coeff: 0) / (denominator coeff: 0).
	    q addCoefficient: piv.
	    n := n - (denominator * piv).
	    n clean
          ].
        ^ { q . (n degree) > 0 ifTrue: [ n ] ifFalse: [ n addCoefficient: 0. n ] }
      ]
      ifFalse: [
        ^ { Polynomial newWithCoefficients: #( 0 ) . self deepCopy }
      ]
  ]
  * constant [ |r| r := self deepCopy.
    1 to: (coeffs size) do: [ :i |
      r at: i put: ((r at: i) * constant)
    ].
    ^ r
  ]
  at: index [ ^ coeffs at: index ]
  at: index put: obj [ ^ coeffs at: index put: obj ]
  >= anotherPoly [
    ^ (self degree) >= (anotherPoly degree)
  ]
  degree [ ^ coeffs size ]
  - anotherPoly [ "This is not a real subtraction between Polynomial: it is an
                   internal method ..."
    |a|
    a := self deepCopy.
    1 to: ( (coeffs size) min: (anotherPoly degree) ) do: [ :i |
      a at: i put: ( (a at: i) - (anotherPoly at: i) )
    ].
    ^ a
  ]
  coeff: index [ ^ coeffs at: (index + 1) ]
  addCoefficient: coeff [ coeffs add: coeff ]
  clean [
    [ (coeffs size) > 0
        ifTrue: [ (coeffs at: 1) = 0 ] ifFalse: [ false ] ]
      whileTrue: [ coeffs removeFirst ].
  ]
  display [
    1 to: (coeffs size) do: [ :i | 
      (coeffs at: i) display.
      i < (coeffs size)
        ifTrue: [ ('x^%1 + ' % {(coeffs size) - i} ) display ]
    ] 
  ]
  displayNl [ self display. Character nl display ]
].


|res|
res := OrderedCollection new.

res add:  ((Polynomial newWithCoefficients: #( 1 -12 0 -42) ) /
           (Polynomial newWithCoefficients: #( 1 -3 ) )) ;
    add:  ((Polynomial newWithCoefficients: #( 1 -12 0 -42) ) /
           (Polynomial newWithCoefficients: #( 1 1 -3 ) )).

res do: [ :o |
  (o at: 1) display. ' with rest: ' display. (o at: 2) displayNl
]

You may also check:How to resolve the algorithm Find limit of recursion step by step in the Ring programming language
You may also check:How to resolve the algorithm Video display modes step by step in the Groovy programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Sidef programming language
You may also check:How to resolve the algorithm Associative array/Iteration step by step in the Frink programming language
You may also check:How to resolve the algorithm Sum of a series step by step in the Scala programming language