Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Recursion Program finding root of equation

Reply
Thread Tools

Recursion Program finding root of equation

 
 
michalik.ireneusz@gmail.com
Guest
Posts: n/a
 
      10-22-2008
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
 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      10-22-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      10-22-2008
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
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      10-22-2008
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 |
 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      10-22-2008
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/>
 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      10-22-2008
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 |
 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      10-23-2008
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.

 
Reply With Quote
 
Martin Gregorie
Guest
Posts: n/a
 
      10-23-2008
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 |
 
Reply With Quote
 
Andreas Leitgeb
Guest
Posts: n/a
 
      10-23-2008
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...S/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

 
Reply With Quote
 
Harold Yarmouth
Guest
Posts: n/a
 
      10-23-2008
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...S/Recn/Binary/
>
> (search down for fastest)


That, of course, has an iterative version of its own.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
va_arg... recursion: changing arguments and the using recursion jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM
Disable Recursion vs. Root Zone RogueIT MCSA 1 05-18-2009 08:14 PM
while executing my client program i get the exception javax.naming.LinkException: [Root exception is javax.naming.LinkException: [Root exception is javax.naming.NameNotFoundException: remaining if plz anybody know how to solve this problem then mahesh Java 0 03-08-2007 12:26 PM
SRT DIvision, Square root and reciprocal square root alghazo@siu.edu VHDL 0 05-27-2004 06:23 AM
Tertiary Conditional: what does this evaluate to ("docRoot == null ? this.root : doc root")? Rick Osborn Java 10 02-08-2004 02:25 AM



Advertisments