Factoring Polynomials

Discussion in 'Python' started by collin.day.0, Dec 18, 2008.

  1. collin.day.0

    collin.day.0 Guest

    I am trying to write a simple application to factor polynomials. I
    wrote (simple) raw_input lines to collect the a, b, and c values from
    the user, but I dont know how to implement the quadratic equation

    x = (-b +or- (b^2 - 4ac)^1/2) / 2a

    into python. Any ideas?
     
    collin.day.0, Dec 18, 2008
    #1
    1. Advertisements

  2. collin.day.0

    eric Guest

    with numpy:
    from numpy import *

    s=[1,-1]
    x = -b+s*sqrt( b**2-4*a*c )/(2*a)

    Eric
    http://codeslash.blogspot.com
     
    eric, Dec 18, 2008
    #2
    1. Advertisements

  3. collin.day.0

    Collin D Guest

    Ahh. Great.. thank you. I didnt know about the sqrt function.. saves
    me from doing "^1/2". Thanks again.
    -CD
     
    Collin D, Dec 18, 2008
    #3
  4. Maybe make that (-b / (2. * a)) to avoid getting funny results
    when a and b are integers. (Or do a from __future__ import
    division, or use Python 3.0, or ....)

    And to make the function more bullet-proof, you might want to
    do something like (untested):

    from math import copysign

    [rest of example as in Scott's post]

    if discriminant: # two results
    root1 = (-b - copysign(discriminant, b))/(2*a)
    root2 = c/(a*root1)
    return (root1, root2)

    to avoid numerical problems when b*b is much larger
    than abs(a*c). Compare with the results of the usual
    formula when a = c = 1, b = 10**9, for example. But
    that still doesn't help you when the computation
    of the discriminant underflows or overflows...

    Isn't floating-point a wonderful thing! :)

    Mark
     
    Mark Dickinson, Dec 18, 2008
    #4
  5. collin.day.0

    eric Guest

    there is a little mistake in your formula :

    def roots_of(a, b, c):
    N = ((b**2 - 4*a*c)**.5)
    return ((-b + N)/(2*a), (-b - N)/(2*a))

    but I stick with numpy, numpy is heavy, but not as much as using a
    computer to solve this problem ! And numpy should be standard module
    for computer science student !

    Eric
    http://codeslash.blogspot.com
     
    eric, Dec 18, 2008
    #5
  6. collin.day.0

    Collin D Guest

    Thanks for all your help! Its good to know how to do it w/ without
    numpy.
    And yes, floating point is the best thing since sliced bread. ^^

    -CD
     
    Collin D, Dec 18, 2008
    #6
  7. Read the section on "Numeric Types" (under "Built-in Types") in the
    Library Reference: http://docs.python.org/library/index.html
    Then you should be able to write two expressions to evaluate your formula
    above.
     
    Gabriel Genellina, Dec 19, 2008
    #7
  8. collin.day.0

    James Mills Guest

    Why is this so hard ? This is simple simple
    expression. Reading through the Python
    tutorial and reading up on how to define
    functions is all you need! :)

    Here goes:
    ... x = (-1 * b) + ((b**2 - (4 * a * c)) / (2 * a))
    ... return (-1 * x), x
    ...
    cheers
    James
     
    James Mills, Dec 19, 2008
    #8
  9. collin.day.0

    Collin D Guest

    Hiya James!

    Just one small problem with your equation above...
    The quadratic formula is:
    x = -b +or- (b**2 - (4 * a * c))^1/2 / 2a

    You just forgot the square root which makes quadratic a bit more
    complicated.
    You would have to download and import sqrt() from numpy or **.5

    Also.. I need to build in functionality so the user does not have to
    directly call the function like:
    f(a,b,c)

    Instead.. they should be able to just raw_input their values.
    Also.. as with some of the examples above its a good idea to analyze
    the discriminant to make sure we have a real solution.
    Of course.. thats all pretty simple to build in. Thanks a lot!
     
    Collin D, Dec 19, 2008
    #9
  10. def quadratic_solution(a, b, c):
    sol1 = (-b + (b**2 - 4*a*c)**0.5)/2*a
    sol2 = (-b - (b**2 - 4*a*c)**0.5)/2*a
    return (sol1, sol2)


    Because this looks like homework, I've deliberately left in two errors in
    the above. One of them is duplicated in the two lines above the return,
    and you must fix it or you'll get radically wrong answers.

    The second is more subtle, and quite frankly if this is homework you
    could probably leave it in and probably not even lose marks. You will
    need to do significant research into numerical methods to learn what it
    is, but you will then get significantly more accurate results.
     
    Steven D'Aprano, Dec 19, 2008
    #10
  11. collin.day.0

    James Mills Guest

    Hi Collin,

    Here you go:

    [email protected]:~/tmp$ cat polycalc.py
    #!/usr/bin/env python

    from math import sqrt

    def f(a, b, c):
    if (b**2 - (4 * a * c)) < 0:
    return None, None # Can't solve
    x = (-1 * b) + (((b**2 - (4 * a * c)) ** 0.5) / (2 * a))
    return (-1 * x), x

    print "Polynomial Solver..."
    print

    while True:
    a = float(raw_input("a: "))
    b = float(raw_input("b: "))
    c = float(raw_input("c: "))

    x = f(a, b, c)
    if None in x:
    print "Can't solve!"
    else:
    print "x = -%0.2f" % x[0]
    print "x = +%0.2f" % x[1]
    [email protected]:~/tmp$

    cheers
    James
     
    James Mills, Dec 19, 2008
    #11
  12. collin.day.0

    James Mills Guest

    UPDATE:

    [email protected]:~/tmp$ cat polycalc.py
    #!/usr/bin/env python

    from math import sqrt

    def f(a, b, c):
    if (b**2 - (4 * a * c)) < 0:
    return None, None # Can't solve
    x1 = -b - (sqrt(b**2 - (4 * a * c)) / (2 * a))
    x2 = -b + (sqrt(b**2 - (4 * a * c)) / (2 * a))
    return x1, x2

    print "Polynomial Solver..."
    print

    while True:
    a = float(raw_input("a: "))
    b = float(raw_input("b: "))
    c = float(raw_input("c: "))

    x = f(a, b, c)
    if None in x:
    print "Can't solve!"
    else:
    print "x = (%0.2f, %0.2f)" % x
    [email protected]:~/tmp$ ./polycalc.py
    Polynomial Solver...

    a: 1
    b: 8
    c: 5
    x = (-11.32, -4.68)
     
    James Mills, Dec 19, 2008
    #12
  13. collin.day.0

    Collin D Guest

    Ahh. Great.. that answers a lot of questions.
    Originally I was using just a = raw_input('a: ')
    And was getting errors because you cant perform mathmatical operations
    on strings. >.<
    Thanks again!
     
    Collin D, Dec 19, 2008
    #13
  14. collin.day.0

    Collin D Guest

    The corrected function is:
    def quadratic_solution(a,b,c)
    sol1 = -1*b + ((b**2 - 4*a*c)**.5)/2*a
    sol1 = -1*b - ((b**2 - 4*a*c)**.5)/2*a
    return (sol1, sol2)

    Squaring the -b would give you some strange solutions.... :D

    -CD
     
    Collin D, Dec 19, 2008
    #14
  15. collin.day.0

    James Mills Guest

    No worries. Please take an hour or two to
    go through the Python Tutorial at
    http://docs.python.org/

    cheers
    James
     
    James Mills, Dec 19, 2008
    #15
  16. Homework or not, of course others have answered it completely, more or
    less error-free.
     
    Steven D'Aprano, Dec 19, 2008
    #16
  17. So it would, but I didn't do that. Try again.

    You have a typo in the above: you've written "sol1" twice and there is no
    sol2.

    There is no difference between -1*b and -b (except that -b is probably a
    smidgen faster).

    In the quadratic formula, the -b must be divided by 2a as well as the
    discriminant. You're only dividing the discriminant.

    The *second* error has already been given away by Mark Dickson, who
    rightly points out that the quadratic equation is subject to round-off
    errors. The first error is still there :)

    (Hint: think about the precedence of operators and the need for brackets.)
     
    Steven D'Aprano, Dec 19, 2008
    #17
  18. collin.day.0

    Collin D Guest

    I completed the code:

    #import
    from math import sqrt

    # collect data
    a = float(raw_input('Type a value: '))
    b = float(raw_input('Type b value: '))
    c = float(raw_input('Type c value: '))

    # create solver
    def solver(a,b,c):
    if b**2 - 4*a*c < 0:
    return 'No real solution.'
    else:
    sol1 = -1 * b + (sqrt(b**2 - 4*a*c)) / 2*a
    sol2 = -1 * b - (sqrt(b**2 - 4*a*c)) / 2*a
    return (sol1, sol2)

    # execute
    print solver(a,b,c)

    Thanks to everyone who helped...
    This really expanded my knowledge on some of the mathematical
    functions in Python.
     
    Collin D, Dec 19, 2008
    #18
  19. collin.day.0

    Collin D Guest

    UPDATE:
    '

    #import
    from math import sqrt

    # collect data
    a = float(raw_input('Type a value: '))
    b = float(raw_input('Type b value: '))
    c = float(raw_input('Type c value: '))

    # create solver
    def solver(a,b,c):
    if b**2 - 4*a*c < 0:
    return 'No real solution.'
    else:
    sol1 = (-1 * b + (sqrt(b**2 - 4*a*c))) / 2*a
    sol2 = (-1 * b - (sqrt(b**2 - 4*a*c))) / 2*a
    return (sol1, sol2)

    # execute
    print solver(a,b,c)
     
    Collin D, Dec 19, 2008
    #19
  20. collin.day.0

    Russ P. Guest

    You need to put your denominator, 2*a, in parens. The way it stands,
    you are dividing by 2, then multiplying by a. That's not what you
    want.

    Also, for better style, I suggest you compute the discriminanat once
    and store it for reuse rather than repeating the expression three
    times.
     
    Russ P., Dec 19, 2008
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.