Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Stack Overflow and Recursion Depth
Index -> Programming, Java -> Java Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
np_123




PostPosted: Sun May 03, 2015 6:16 pm   Post subject: Stack Overflow and Recursion Depth

I tried writing a program that would calculate the value of 'e' (Euler's number) to a large number of decimal places using a formula for rapidly converging infinite series.
The specific formula I used is e = sum of series: (2n +2)/(2n + 1)!

I wanted to see how far I could get with the calculation (within a reasonably short amount of running time) but I keep running into Exception in thread "main" java.lang.StackOverflowError. It seems that it is unable to do factorials for numbers greater than ~12000 and I'm not sure why because as far as I know java.math.BigDecimal has arbitrary(and if unspecified, unlimited I'm pretty sure) precision.

So what I'm wondering can I get rid of this limitation?problem? and have the program run continuously until either it reaches some form of maximum memory consumption or I decide to terminate it?

In case it's relevant, I'm using 64-bit Eclipse IDE, and the below code (though with minor modification) ran for 12500-12600 iterations of the while loop before ending with java.lang.StackOverflowError pointing to this line in the code " out = factorial(rec); ".

Java:

import java.math.*;
import java.io.*;

public class Calculation {
 
  public static void main(String[]args) throws IOException{
   
    MathContext mc = new MathContext(1001000);
    BigDecimal count;
    BigDecimal e;
    e = BigDecimal.ZERO;   
    count = BigDecimal.ZERO;     
   
    BigDecimal num;
    BigDecimal two;
    BigDecimal cent = new BigDecimal(100);
    BigDecimal grand = cent.multiply(BigDecimal.TEN);
    BigDecimal fact;
    BigDecimal recurse;

    two = new BigDecimal (2);

   
    while (1 > 0){
     
     
        //recurse = two;
        recurse = two.multiply(count);
        recurse = recurse.add (BigDecimal.ONE);
     
        fact = (factorial(recurse));
     
        //num = two;
        num = two.multiply(count);
        num = num.add(two);
        num = num.divide(fact,mc);
        //number = new BigDecimal((2*count + 2)/Factorial(2*count + 1));             
     
        e = e.add(num)
     
        count = count.add(BigDecimal.ONE);
        if (count.remainder(grand) == BigDecimal.ZERO){
            System.out.println(count);
        }
        if (count.remainder(cent) == BigDecimal.ZERO){
            String result;
            result = e.toPlainString();         
            FileWriter out = null;
            out = new FileWriter("Calculation.txt");
            out.write(result);
            out.close();
        }
     
    }
  }
   
    public static BigDecimal factorial(BigDecimal x){     
        BigDecimal rec;
        BigDecimal out;     
        //one = new BigDecimal (1);
        rec = x;     
        rec = rec.subtract(BigDecimal.ONE);
     
        if (x.compareTo(BigDecimal.ONE) > 0){
            out = factorial(rec);
            out = out.multiply(x);
            return out;
        } else {
            return BigDecimal.ONE;
        }
     
    }
   
}
Sponsor
Sponsor
Sponsor
sponsor
Zren




PostPosted: Sun May 03, 2015 8:28 pm   Post subject: Re: Stack Overflow and Recursion Depth

Eh, I'm not sure it's the best idea to give more memory to the stack. Usually when you run into stack overflow errors when doing recursion, it's time to think of solving the problem iteratively.

From what I understand of the calculation of e, you could calculate the factorial iteratively as well.

Eg:
Python:

n = 0
fact = 1
e = 1

while True:
    n += 1
    fact *= n
    e += 1 / fact


Though your algorithm is a bit different than what I see on wikipedia:

Posted Image, might have been reduced in size. Click Image to view fullscreen.

Python:

e = 0
count = 0

while True:
    recurse = 2 * count + 1
    fact = factorial(recurse)

    num = (2 * count + 2) / fact
    e += num
    count += 1
   


Your's seems to be skipping even numbers? And the numerator is 2 * (count+1) instead of 1? Is there a source for this algorithm?
np_123




PostPosted: Sun May 03, 2015 9:30 pm   Post subject: Re: Stack Overflow and Recursion Depth

Yeah, I do have a source for this algorithm: http://m.intmath.com/exponential-logarithmic-functions/calculating-e.php
The website calls it the Brothers' Formulae. I've used it to calculate e to almost 100000 digits before getting stack overflow so in that sense I can somewhat attest to its correctness.

It never actually occurred to me to calculate the factorial like that - multiplying by the term as the program iterates through the loop. I can see how that would probably be much more efficient than recursion with such large numbers as I'd be dealing with.
And so calculating the factorial iteratively instead of using recursion should avoid the stack overflow error then? If that's the case, then I should be able to get it working without too much extra effort by the sounds of it.
wtd




PostPosted: Thu May 07, 2015 10:14 am   Post subject: RE:Stack Overflow and Recursion Depth

You're not wrong to sue recursion to solve this problem, or Java, but...

You are wrong to use both at the same time.

Java does not implement tail call optimization.

The way the stack works is that every function/method call tacks it's requisite information onto the stack. The deeper you go in the recursion, the larger the stack gets. Enough levels of recursion and BOOM! Stack overflow.

Tail call optimization involves compilers determining that if a function call is the last call in a function, it can eliminate the stack presence of the calling function. Properly designed, a recursive function never uses more stack space than is required for one function call.

A simple example would be calculating factorials recursively.

code:
let factorial x =
   let rec factorial' x acc =
      if x = 1 then
         acc
      else
         factorial' (x - 1) (acc * x)
   in
      factorial' x 1
in
   factorial 5


And we can sketch out how execution of this would look:

code:
factorial 5
factorial' 5 1
factorial' 4 5
factorial' 3 20
factorial' 2 60
factorial' 1 120
120


Now, a version which doesn't use tail calls and we can see the difference.

code:
let factorial x =
   if x = 0 then
      1
   else
      x * factorial (x - 1)
in
   factorial 5


Now to look at the execution:

code:
factorial 5
5 * factorial 4
5 * 4 * factorial 3
5 * 4 * 3 * factorial 2
5 * 4 * 3 * 2 * factorial 1
5 * 4 * 3 * 2 * 1 * factorial 0
5 * 4 * 3 * 2 * 1 * 1
120


Obviously that won't overflow the stack, but imagine if we'd used a much larger number, or had a more complex recursive function.

In short, if you wish to continue using Java, find a way to iteratively calculate, rather than relying on recursion.

Or learn another language. It's fun!
np_123




PostPosted: Thu May 07, 2015 7:02 pm   Post subject: Re: Stack Overflow and Recursion Depth

I changed it to calculate the factorial iteratively using a while loop and repeated multiplication and I must say its quite very extremely slow once it starts reaching numbers in the several thousands. Still, I wasn't expecting it to run fast, and I learned fair amount along the way, so it served its purpose.

Now I'm thinking to see if I can write code to do the same job(but hopefully a lot better) in C++. And in place of Java's BigDecimal, likely going to use 'GNU multiple precision arithmetic library'(gmp) to get the higher precision.
wtd




PostPosted: Fri May 08, 2015 12:48 am   Post subject: RE:Stack Overflow and Recursion Depth

For fun, I rewrote my function to handle 64-bit integers.

code:
open Big_int;;
include Big_int;;

let factorial x =
   let rec factorial' x acc =
      if eq_big_int x 0I then
         acc
      else
         factorial' (sub_big_int x 1I) (mult_big_int x acc)
   in
      factorial' (big_int_of_int x) 1I;;
Display posts from previous:   
   Index -> Programming, Java -> Java Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 6 Posts ]
Jump to:   


Style:  
Search: