PDA

View Full Version : Catching an "impossible" stack overflow?



Robert Kosek
06-06-2007, 07:40 PM
System: Win XP SP2 (all updates), AMD X2 4800.
Compiler/IDE: Turbo Delphi.
Libraries/API: Standard SysUtils & Math.

-----

Basically what I'm doing is factorization. I figured that it would be a fun experiment in recursion and wouldn't take long, but boy I was wrong! Basically I have a dynamic array of words and a function that (can) recursively factor numbers. In fact, it'll factor 37,777 sum the factors and factor those without a hitch. But, try factoring 456 and I get a stack overflow!

How?

456 = 2 x 2 x 2 x 57;

That shouldn't be hard to test or factor, but I seem to have done something incorrectly here.

Edit: factorizing 456 by 57 works, but not the automatic way around.

Part of the trouble is in preventing factorable numbers being in the output when they aren't wanted. I have a way that you can call the same function looking for a specific factor, and if that factor is 0 it just does some standard factorization. Anything that isn't prime gets factorized, and so on recursively. At the end is a quick bubblesort to order things numerically.

How do I go about catching something like this in my code? I've never dealt with a stack overflow, honestly, so I have no clue how to do it. Should I go into a larger number for my iterator in factorization? I figured at 65k limit on factors was safe for the maximum factor of ~65k.

I'll give the code if it helps, but I want to learn to catch this guy without 100% specific pointers to an area of my code. Thank you in advance.

Robert Kosek
06-06-2007, 07:56 PM
Nevermind, it appears that stack overflow in my case is the same as infinite recursion. The only problem is how to avoid infinite recursion in this case, therefore I'll just request this topic be deleted.

jdarling
06-06-2007, 08:50 PM
Hey Robert, looks like you get to learn about private stacks and recursion reduction :). Basically you have to remove the recursion from your function completely and implement your own stack. Arrays work nice and allow for more flexibility. If you want to work on REALLY LARGE hunks of data then its time to look at the hard drive and streams to implement your process stack.

Its not too bad to implement a very basic private stack. Here is a simple example:
Recursive:procedure DoSomething(HowManyTimes : Integer);
begin
while HowManyTimes > 0 do
begin
WriteLn(HowManyTimes);
dec(HowManyTimes);
DoSomething(HowManyTimes);
end;
end;

Now, revised with a private stack:procedure DoSomething2(HowManyTimes : Integer);
const
AllocBy = 10;
var
myStack : Array of Integer;
dispVal, i,
stackSize : Integer;
procedure Push(AVal : Integer);
begin
if stackSize+1>length(myStack) then
SetLength(myStack, stackSize + AllocBy);
myStack[stackSize] := AVal;
inc(stackSize);
end;
function Pop : Integer;
begin
if stackSize > 0 then
result := myStack[stackSize-1]
else
begin
Writeln('Stack underflow');
Halt(255);
end;
dec(stackSize);
end;
begin
stackSize := 0;
for i := 1 to HowManyTimes do
Push(i);
while stackSize > 0 do
begin
dispVal := Pop;
Writeln(dispVal);
for i := 1 to dispVal-1 do
Push(i);
end;
end;

Basically I've taken the original code and unwrapped it a bit. First pushing our starting values onto the stack. Then while the stack isn't empty processing the last item on the stack. This coincidently may add new items to the end of the stack. And away we go :)

This type of private stack processing works very well in things like flood fill and mathematics as it can be done in a local variable (as shown above) or it can be done on the disk itself and using jumps to move/size the stack.

Anyways, hope it helps. In case your curious, here is a version that uses a file stream to perform the exact same thing as above:procedure DoSomething(HowManyTimes : Integer);
var
myStack : TFileStream;
dispVal, i: Integer;
stackSize : Integer;
procedure Push(AVal : Integer);
begin
myStack.Seek((stackSize)*sizeof(AVal), soBeginning);
myStack.Write(AVal, sizeof(AVal));
inc(stackSize);
end;
function Pop : Integer;
begin
result := 0;
if stackSize > 0 then
begin
myStack.Seek((stackSize-1)*sizeof(result), soBeginning);
myStack.Read(result, sizeof(result));
end
else
begin
Writeln('Stack underflow');
Halt(255);
end;
dec(stackSize);
end;
begin
stackSize := 0;
myStack := TFileStream.Create('temp.stack', fmCreate);
try
for i := 1 to HowManyTimes do
Push(i);
while stackSize > 0 do
begin
dispVal := Pop;
Writeln(dispVal);
for i := 1 to dispVal-1 do
Push(i);
end;
finally
myStack.Free;
end;
if fileExists('temp.stack') then
DeleteFile('temp.stack');
end;

Granted that the last one is slower due to disk access, but it can process ANY size of number as long as you have the disk space for the stack :)

Finally, yes there are optimizations that could be put in place, but I left that for you to figure out :)

jdarling
06-06-2007, 08:54 PM
Nevermind, it appears that stack overflow in my case is the same as infinite recursion. The only problem is how to avoid infinite recursion in this case, therefore I'll just request this topic be deleted.


N N OOO !!
NN N O O !!
N N N O O !!
N NN O O
N N OOO !!


I spent too much time answering that damned thing for it to be delete :)

Robert Kosek
06-06-2007, 09:33 PM
ROFL. Thanks for the answer. I ended up rewriting the whole function so that it wasn't recursive. I kept refactoring farther than necessary due to a problem with the if statement controlling my recursion. :roll:

Basically the first problem was how to stop non-prime factors from appearing in the results, so I tried it recursively. Now what I do is use a boolean check to ensure the resulting array consists of completely prime numbers and simply re-process the non-primes each pass. It's pretty quick. But since I'm doing manipulation to the array I can't really pop/push them except for appending values (or at least in safety).

But hey, it now works in a pretty efficient manner and gives accurate results.

(Nevermind the delete bit now. :P)

jdarling
07-06-2007, 01:21 PM
Good to hear Robert. True, that its hard to push and pop in your scenario (not impossible though). It sounds like you have still achieved the same thing in the end. I might suggest removing your array and converting it to a doubly linked list. This should help with memory re-allocations that occur every time you re-size an array. In fact you could make a field to pull you list items from so that you can re-use them and not loose speed on re-calcs at all.

Robert Kosek
07-06-2007, 01:49 PM
Actually, I did it a bit more intelligently than that. ;) Instead of a for-loop the main loop is a while loop runs so long as the temporary number is greater than 0. I then find the factor of that number (n) and push the factor, then divide the number. At the end if there is a leftover 2 in the number I just push it to the end and make n 0.

So in the end my loop looks like this: while n > 0 do
if (n = 2) or (IsPrimeRM(n)) then begin
pushValue(Result,n);
n := 0;
end else begin
for i := (n div 2) downto 2 do
if IsPrimeRM(i) then
if n mod i = 0 then begin
pushValue(Result,i);
if n <> i then
n := n div i
else
n := 0;
end;
end;

The 'if n <> i then' part came into play because I was getting an end duplicate factor because it would then decrement the remainder to 1 and loop infinitely. So that helps bust the loop.

In the end, my results are accurate and it was a good learning experience at figuring out better function design (ha! What a stack overflow won't teach you...).

If someone wants the code I'll post it, otherwise you're better off writing it yourself. ;)


Enter a number from 4 to 65535 and one number in specific to look for separated
by a space. Looking for 0 means just factor the number. Two zero's exits.

x = 45670 5
factors&#58; 5 x 9134
sum of parts&#58; 9139
factors of sum of parts&#58; 2 x 3 x 5 x 7 x 11 x 13 x 19 x 37

x = 45670 0
factors&#58; 2 x 5 x 4567
sum of parts&#58; 4574
factors of sum of parts&#58; 2 x 2287

x = 65470
0
factors&#58; 2 x 5 x 6547
sum of parts&#58; 6554
factors of sum of parts&#58; 2 x 29 x 113

x =

wodzu
10-06-2007, 10:30 AM
Hey Robert, looks like you get to learn about private stacks and recursion reduction :). Basically you have to remove the recursion from your function completely and implement your own stack. Arrays work nice and allow for more flexibility. If you want to work on REALLY LARGE hunks of data then its time to look at the hard drive and streams to implement your process stack.


Wow thanks jdarling for posting this. I would never figure it out this by myself. :D Great idea!