home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 3 / PDCD_3.iso / languages / scheme / GNU / jacalrc / jacal / DOC / algdenom next >
Encoding:
Text File  |  1991-01-06  |  1.3 KB  |  33 lines
  1.         Algorithm to Remove Radicals From Denominators
  2.  
  3. Based on the denominator s(y) generate a factor which when multiplied
  4. times the ratio will remove y from the denominator s(y).
  5.  
  6. Let y be defined by a polynomial p(y)=0.
  7. Let s(y) be a polynomial in y with deg(s(y)) < deg(p(y)).
  8. Psuedo-dividing p(y) by s(y), the psuedo-quotient q1(y) and the
  9. psuedo-remainder r1(y) satisfy
  10. lc^(n-m+1)*p(y) = q1(y)*s(y) + r1(y) ; deg(r1(y)) < deg(s(y))
  11. If deg(r1(y))=0
  12.   then q1(y)*s(y) = -r1
  13.   else psuedo-divide p(y) by r1(y)
  14.     lc^(n-m+1)*p(y) = q2(y)*r1(y) + r2(y) ; deg(r2(y)) < deg(r1(y))
  15. This is repeated until deg(rk(y)) = 0.
  16. Thus q1(y)*q2(y)*...*qk(y)*s(y) = (-1)^k * rk.
  17.  
  18. The product q1(y)*q2(y)*...*qk(y) is a factor which when multiplied
  19. times a ratio will remove y from the denominator s(y).
  20.  
  21. Ira Gessel suggests instead using the extended Euclidean Algorithm.
  22. Given p(y) and s(y) as above, it produces polynomials
  23. a(y) and b(y) such that
  24. a(y)*p(y) + b(y)*s(y) = gcd(p(y),s(y)) = r1.
  25. Because p(y)=0 the product b(y)*s(y) = r1.
  26.  
  27. If rk=0 then p(y) and s(y) have a common factor and hence we are
  28. dividing by zero.  An example of this is 1/(y+2) where y is defined by
  29. y^2 - 4 = 0.
  30.  
  31. If deg(s(y))=1 the first algorithm terminates after the first
  32. division;  The second algorithm will require more divisions.
  33.