Re: grassfire algorithm in java
From: Paul Lutus (nospam_at_nosite.zzz)
Date: 10/04/04
- Next message: Paul Lutus: "Re: System.getProperty("user.dir") cannot rerturn the package directory."
- Previous message: Chris Uppal: "Re: Very newbie question"
- In reply to: Mike Schilling: "Re: grassfire algorithm in java"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 04 Oct 2004 10:32:18 -0700
Mike Schilling wrote:
/ ...
>> Allowing the stack to overflow prevents any kind of analysis or recovery
>> of
>> essential data. All you have is the stack overflow error message, a
>> rather long, uninformative stack trace, and no other options.
>
> Unless you've been gathering data as you go, which is what I'd do in this
> kind of situation, either keeping data in memory, or, if there's likely to
> be too much for that, writing a log file.
Yes, along with the recursion count. But given that, and with any knowledge
of the algorithm, one can use the recursion count to judge that the
algorithm is outside any reasonable bound.
> Especially in a complex
> situation with many mutually recursive methods, the path the program took
> to get to the out-of-control recursion, including methods calls which did
> lead to
> returns, is likely to be interesting. Dumping only what's current at the
> time the recurstion is determined to be excessive loses all of this.
All that is useful, but the final state may uncover a cause for the
recursion going out of bounds. It is common for a specific precipitating
factor to cause a recursion to fall out of control, and that factor may be
present at the maximum allowable recursion count.
If, on the other hand, the stack is allowed to overflow, that opportunity is
lost, because there is no stack to support analysis method calls (or more
to the point, one cannot rely on sufficient stack space).
>> BTW the code posted earlier by Mr. Schilling doesn't even provide a stack
>> trace, because of a badly placed try ... catch clause (the stack has been
>> dumped at the location of the catch clause).
> It wasn't intended to. The point of that program was to demonstrate that
> the stack isn't "destroyed" by an overflow, but rather than the
> StackOverflowError can be caught and the program can continue normally.
In doing this, you discarded the stack, which undermines your claim above
that it was not destroyed (e.g. rendered unusable as a source of either
control or information).
Counting recursions is the preferred approach to a problem of this class. In
this specific case, relying on a stack overflow instead is a misuse of a
try ... catch clause, along with being unnecessary.
On the topic of recursion counting, take a look at this program I wrote for
a Calculus student a few days ago. It generates numerical approximations of
derivatives (the function being processed is y = x^2):
************************************************************
import java.text.*;
public class Difference {
double dx = 1e-2;
int depth = 4;
int tabSize = 12;
String tab(String s,int n,String tabChar) {
StringBuffer sb = new StringBuffer();
while(n-- > s.length()) {
sb.append(tabChar);
}
sb.append(s);
return sb.toString();
}
String tab(double v,int n,String tabChar)
{
String s = new DecimalFormat("#0.000").format(v);
return tab(s,n," ");
}
// the basic function
public double f(double x) {
return x * x;
}
// the difference function
double df(double x,int d)
{
if(d > 0) {
d -= 1;
return (df(x+dx,d) - df(x-dx,d)) / (2 * dx);
}
else {
return f(x);
}
}
void showResult(double x) {
System.out.print(tab(x,tabSize," "));
for(int i = 0; i < depth;i++) {
System.out.print(tab(df(x,i),tabSize," "));
}
System.out.println();
}
void makeTitle()
{
System.out.print(tab("x",tabSize," "));
String apos="";
for(int i = 0;i < depth;i++) {
System.out.print(tab("f" + apos + "(x)",tabSize," "));
apos += "'";
}
System.out.println();
for(int i = 0;i <= depth;i++) {
System.out.print(tab("",tabSize,"-"));
}
System.out.println();
}
void perform()
{
makeTitle();
for(double x = 0;x <= 8;x++) {
showResult(x);
}
}
public static void main(String[] args)
{
new Difference().perform();
}
}
************************************************************
Result:
x f(x) f'(x) f''(x) f'''(x)
------------------------------------------------------------
0.000 0.000 0.000 2.000 0.000
1.000 1.000 2.000 2.000 -0.000
2.000 4.000 4.000 2.000 0.000
3.000 9.000 6.000 2.000 0.000
4.000 16.000 8.000 2.000 0.000
5.000 25.000 10.000 2.000 0.000
6.000 36.000 12.000 2.000 0.000
7.000 49.000 14.000 2.000 0.000
8.000 64.000 16.000 2.000 0.000
This kind of program tends to run out of steam rather quickly because of the
limited resolution of double variables (note the errant "-" sign in the
right-hand column). An effort to squeeze more derivatives out of it, using
a function that might produce something useful (like y = x^4), instead
begins to produce junk.
The point? Recursion counting is the key to its operation.
-- Paul Lutus http://www.arachnoid.com
- Next message: Paul Lutus: "Re: System.getProperty("user.dir") cannot rerturn the package directory."
- Previous message: Chris Uppal: "Re: Very newbie question"
- In reply to: Mike Schilling: "Re: grassfire algorithm in java"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
