Recursion Program finding root of equation

M

michalik.ireneusz

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
 
P

Patricia Shanahan

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
 
P

Patricia Shanahan

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
 
M

Martin Gregorie

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.
 
M

Martin Gregorie

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.
 
M

Mark Space

Martin said:
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.
 
M

Martin Gregorie

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.
 
H

Harold Yarmouth

bugbear said:
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.)
 
M

michalik.ireneusz

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?????
 
A

Andreas Leitgeb

Tim Smith said:
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 :)
 
P

Patricia Shanahan

Andreas said:
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
 
A

Andreas Leitgeb

Patricia Shanahan said:
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 :)
 
R

Roedy Green

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.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top