Recursion Program finding root of equation

Discussion in 'Java' started by michalik.ireneusz@gmail.com, Oct 22, 2008.

  1. Guest

    I need help writing a program when given two variables, a high and a
    low, and given an equation, that will find the zero of the equation
    based on using the sign change on either side of the zero, if you
    could help me out it would be greatly appreciated
     
    , Oct 22, 2008
    #1
    1. Advertising

  2. wrote:
    > I need help writing a program when given two variables, a high and a
    > low, and given an equation, that will find the zero of the equation
    > based on using the sign change on either side of the zero, if you
    > could help me out it would be greatly appreciated


    Note that you cannot count on there being a zero unless the function is
    continuous.

    Can you describe what sort of help you need? Do you understand the
    objective, and the underlying mathematical idea? Do you understand
    recursion?

    Assuming you understand both recursion and the objective, you should
    begin by doing the task with pencil and paper for some very simple function.

    Patricia
     
    Patricia Shanahan, Oct 22, 2008
    #2
    1. Advertising

  3. Eric Sosman wrote:
    ....
    > I'm not sure why you're interested in a recursive framework,
    > though. ...


    I think this may relate to one of the more difficult problems in
    computer science education - finding good example problems for teaching
    recursion and making sure students have understood it.

    Patricia
     
    Patricia Shanahan, Oct 22, 2008
    #3
  4. Re: [OT] Re: Recursion Program finding root of equation

    On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:

    > Could be. At least the teacher has not dragged out the Fibonacci
    > numbers, which are a *terrible* use of recursion but are for some reason
    > *always* used to illustrate it ...
    >

    I've always liked code to create and walk a binary tree to illustrate
    recursion.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Oct 22, 2008
    #4
  5. Daniel Pitts Guest

    Re: [OT] Re: Recursion Program finding root of equation

    Martin Gregorie wrote:
    > On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:
    >
    >> Could be. At least the teacher has not dragged out the Fibonacci
    >> numbers, which are a *terrible* use of recursion but are for some reason
    >> *always* used to illustrate it ...
    >>

    > I've always liked code to create and walk a binary tree to illustrate
    > recursion.
    >
    >

    Walk, sure. Create, no.

    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
     
    Daniel Pitts, Oct 22, 2008
    #5
  6. Re: [OT] Re: Recursion Program finding root of equation

    On Wed, 22 Oct 2008 14:09:13 -0700, Daniel Pitts wrote:

    > Martin Gregorie wrote:
    >> On Wed, 22 Oct 2008 14:36:00 -0400, Eric Sosman wrote:
    >>
    >>> Could be. At least the teacher has not dragged out the Fibonacci
    >>> numbers, which are a *terrible* use of recursion but are for some
    >>> reason *always* used to illustrate it ...
    >>>

    >> I've always liked code to create and walk a binary tree to illustrate
    >> recursion.
    >>
    >>

    > Walk, sure. Create, no.


    I should clarify here that I mean a plain (non-balanced) binary tree with
    a single key value in every node. You walk the tree to find the insertion
    point, slap your new node in to replace the existing left or right link
    and attach the rest of that branch to it.

    Of course you can't remove a node from such a tree or (usually) change
    the key value in a node, but its plenty good enough for a small to medium
    one-time tree that will be grown, walked and scrapped. Yes, it may be
    slow if its gets very degenerate, but OTOH its fast to build and to
    traverse.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Oct 23, 2008
    #6
  7. Mark Space Guest

    Re: [OT] Re: Recursion Program finding root of equation

    Martin Gregorie wrote:

    > I should clarify here that I mean a plain (non-balanced) binary tree with
    > a single key value in every node. You walk the tree to find the insertion


    I think recursive walks are bad too. Most moder CPUs have a relatively
    small cache with will negatively impact performance if they are written
    to gratuitously. This include stack, which is cached locally too.

    Recursive algorithms tend to eat up stack space quickly, and will thrash
    the local cache. AMD recommends that no recursive algorithms be employ
    on its CPUs as the performance hit is too great. I can't find that
    quote right now, but I'm sure that's accurate.
     
    Mark Space, Oct 23, 2008
    #7
  8. Re: [OT] Re: Recursion Program finding root of equation

    On Wed, 22 Oct 2008 20:05:36 -0700, Mark Space wrote:

    > I think recursive walks are bad too.
    >

    I won't argue with that.

    Just remember we've been talking about recursion examples for teaching
    about recursion.

    When I had to implement a fast, in-memory lookup of a non-static tree I
    used the red-black balanced tree algorithm in Sedgwick's "Algorithms".
    This is iterative, not recursive and inserts aren't particularly
    expensive.

    The tree was, err, quite large - last time I saw it there were 3 million
    nodes and growing. The process was running at around 20,000 lookups a
    second on an Alphaserver EV6 cpu in case you're interested. The main
    reason for the speed was that the maximum search depth was about 23 since
    the tree was balanced.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Oct 23, 2008
    #8
  9. Re: [OT] Re: Recursion Program finding root of equation

    bugbear <bugbear@trim_papermule.co.uk_trim> wrote:
    > Here's a recursive version of fib that will beat the usual iterative
    > version out of sight:
    > http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/


    cool. Thanks for the link.

    Btw, there is also a (theoretically) constant time
    algorithm: namely the closed formula, which involves
    a sum of each n-powered golden-cut and one-minus-
    golden-cut, iirc. It requires a hell of an exact
    floating point library, though :)
     
    Andreas Leitgeb, Oct 23, 2008
    #9
  10. Re: [OT] Re: Recursion Program finding root of equation

    bugbear wrote:
    > Here's a recursive version of fib that will beat the usual iterative
    > version out of sight:
    >
    > http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/
    >
    > (search down for fastest)


    That, of course, has an iterative version of its own.
     
    Harold Yarmouth, Oct 23, 2008
    #10
  11. Re: [OT] Re: Recursion Program finding root of equation

    bugbear wrote:
    > Harold Yarmouth wrote:
    >> bugbear wrote:
    >>> Here's a recursive version of fib that will beat the usual iterative
    >>> version out of sight:
    >>>
    >>> http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/
    >>>
    >>> (search down for fastest)

    >>
    >> That, of course, has an iterative version of its own.

    >
    > Of course; converting between recursive and iterative
    > implementations of the same basic algorithms
    > is a common comp-sci exercise.
    >
    > I was careful to say "usual iterative version".


    My point is that there is an iterative version that seems to beat all
    recursive versions, even if it is NOT the "usual" iterative version.

    (I expect an iterative version with no explicit stack to beat a
    recursive version that's otherwise essentially the same, except for a
    tail-recursive version on a system like lisp that aggressively optimizes
    those. Which I understand they do by turning them into iterations, by
    the by.)
     
    Harold Yarmouth, Oct 23, 2008
    #11
  12. Guest

    On Oct 23, 10:07 am, Harold Yarmouth <>
    wrote:
    > bugbear wrote:
    > > Harold Yarmouth wrote:
    > >> bugbear wrote:
    > >>> Here's a recursive version of fib that will beat the usual iterative
    > >>> version out of sight:

    >
    > >>>http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/Binary/

    >
    > >>> (search down for fastest)

    >
    > >> That, of course, has an iterative version of its own.

    >
    > > Of course; converting between recursive and iterative
    > > implementations of the same basic algorithms
    > > is a common comp-sci exercise.

    >
    > > I was careful to say "usual iterative version".

    >
    > My point is that there is an iterative version that seems to beat all
    > recursive versions, even if it is NOT the "usual" iterative version.
    >
    > (I expect an iterative version with no explicit stack to beat a
    > recursive version that's otherwise essentially the same, except for a
    > tail-recursive version on a system like lisp that aggressively optimizes
    > those. Which I understand they do by turning them into iterations, by
    > the by.)- Hide quoted text -
    >
    > - Show quoted text -


    Would anyone know how to write this program?????
     
    , Oct 23, 2008
    #12
  13. Re: [OT] Re: Recursion Program finding root of equation

    Tim Smith <> wrote:
    >> Btw, there is also a (theoretically) constant time
    >> algorithm: namely the closed formula, ...

    > The normal Java double is good enough to go out to F70:


    The way you did it, it's not really constant time.

    I meant: do the exponentiation as exp(log(phi)*n)
    and see up to which n this will work out precise
    when rounded to long.

    I didn't try it myself, so maybe it's even more
    precise than repeated multiplication, afterall :)
     
    Andreas Leitgeb, Oct 23, 2008
    #13
  14. Re: [OT] Re: Recursion Program finding root of equation

    Andreas Leitgeb wrote:
    > Tim Smith <> wrote:
    >>> Btw, there is also a (theoretically) constant time
    >>> algorithm: namely the closed formula, ...

    >> The normal Java double is good enough to go out to F70:

    >
    > The way you did it, it's not really constant time.
    >
    > I meant: do the exponentiation as exp(log(phi)*n)
    > and see up to which n this will work out precise
    > when rounded to long.


    Why "exp(log(phi))*n)" rather than Math.pow(phi,n)?

    I tested the closed form method using Math.pow and it is exact through n=70.

    Patricia
     
    Patricia Shanahan, Oct 23, 2008
    #14
  15. Re: [OT] Re: Recursion Program finding root of equation

    Patricia Shanahan <> wrote:
    > Andreas Leitgeb wrote:
    >> Tim Smith <> wrote:
    >>>> Btw, there is also a (theoretically) constant time
    >>>> algorithm: namely the closed formula, ...
    >>> The normal Java double is good enough to go out to F70:

    >>
    >> The way you did it, it's not really constant time.
    >>
    >> I meant: do the exponentiation as exp(log(phi)*n)
    >> and see up to which n this will work out precise
    >> when rounded to long.

    > Why "exp(log(phi))*n)" rather than Math.pow(phi,n)?
    > I tested the closed form method using Math.pow and it is exact through n=70.


    I don't know Math.pow()'s implementation. With integer exponents
    it may just do some clever repeated multiplication and squaring
    based on binary representation of "n". Maybe it does, then it's
    not a O(1) but O(log n)). Or it does not, then it more or less *is*
    just exp(log(phi)*n), anyway (except for corner cases not relevant
    to phi and n).

    Math.pow() takes two doubles, but it's javadoc does mention
    cases where the exponent may be an odd or even integer,
    so any integer-based "optimisations" are not infeasible.

    Iow, Math.pow() might possibly maximize precision at cost
    of performance, which often is just fine, but destroys the
    O(1)-claim. That this O(1)-claim is actually bogus, anyway,
    is a different story and beyond the fields of my/our theorizing :)
     
    Andreas Leitgeb, Oct 23, 2008
    #15
  16. Roedy Green Guest

    On Wed, 22 Oct 2008 09:36:24 -0700 (PDT),
    wrote, quoted or indirectly quoted someone who said :

    >I need help writing a program when given two variables, a high and a
    >low, and given an equation, that will find the zero of the equation
    >based on using the sign change on either side of the zero, if you
    >could help me out it would be greatly appreciated


    You don't typically solve such a problem with recursion, unless you
    are a mathematician. You use iteration (a loop) then terminates after
    so much time or once the answer gets close enough.

    This is the subject of a year's course in numerical analysis at
    university. You might check your local university to see what text
    book they recommend for the numerical analysis course.

    If your equation is well behaved without multiple roots,
    discontinuities etc, you can use Newton Raphson. Google.

    You can do an even simpler version with a binary search.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    A vote for McCain is fearful clinging to McSame.
    A vote for Obama is a shot at Obamalot.
     
    Roedy Green, Oct 30, 2008
    #16
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,255
  2. Aaron Prohaska
    Replies:
    0
    Views:
    364
    Aaron Prohaska
    Jan 9, 2004
  3. Rick Osborn
    Replies:
    10
    Views:
    3,976
    Jon A. Cruz
    Feb 8, 2004
  4. hector
    Replies:
    5
    Views:
    421
    CBFalconer
    Dec 5, 2006
  5. Replies:
    8
    Views:
    761
    John Reye
    Apr 26, 2012
Loading...

Share This Page