9 Replies - 927 Views - Last Post: 16 April 2012 - 09:17 AM Rate Topic: -----

#1 Mobuis1995  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 15-February 12

Stack Overflow

Posted 15 April 2012 - 09:16 PM

I have a method which is supposed to return the Sum of it's Divisors. I need this for rather large numbers, so it uses and returns a BigInteger. Here's my method:
private static BigInteger divSum (BigInteger bigInt, BigInteger test)
    {
    	if (test.equals(new BigInteger("1")))
    	{
    		return new BigInteger("1");
    	}
    	else if (bigInt.mod(test) == BigInteger.ZERO)
    	{
    		return test.add(divSum(bigInt, test.subtract(BigInteger.ONE)));
    	}
    	else
    	{
    			return divSum(bigInt, test.subtract(BigInteger.ONE));
    	}
    }

It works fine for small numbers, however when I call
divSum (new BigInteger("10"), new BigInteger("10"))
JCreator sends a ton of error messages, and Stack Overflow being at the top. Other than being a website, I do not know much about it, besides also meaning that too much memory is used on the call stack. What options do I have to fix the situation?

Is This A Good Question/Topic? 0
  • +

Replies To: Stack Overflow

#2 Casper1  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 13
  • Joined: 12-April 12

Re: Stack Overflow

Posted 15 April 2012 - 10:24 PM

10 is not a big integer. Instead of using the data type BigInteger, you can safely use int. The type int has a pretty wide range itself for most daily-use purposes. BigInteger is used to very big numbers like those involved in science.
Was This Post Helpful? 0
  • +
  • -

#3 Mobuis1995  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 15-February 12

Re: Stack Overflow

Posted 16 April 2012 - 04:08 AM

Well, I need to use this method to find the sum of the divisors of !1000, so I believe an int would be too small, and so would a long.
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2134
  • View blog
  • Posts: 3,274
  • Joined: 21-June 11

Re: Stack Overflow

Posted 16 April 2012 - 04:53 AM

In line 7 you're using == to compare big integers. This has nothing to do with the stack overflow, but it's wrong nonetheless.

A stack overflow happens if your recursion depth is too high. In this case, it should be 10, which shouldn't be too high (and in fact your code runs fine on my PC). Are you sure that the stack overflow happens already with 10 and 10 as the arguments?

For large numbers the method will overflow the stack simply because it uses stack space linear in the size of the second argument. You can rewrite the method to just use loops and no recursion. Then it will only consume constant stack space and no stack overflows will occur.

That being said, 1000! is a freaking huge number and there's no way your method will finish in a reasonable time with that number as its arguments (even if you rewrite it using loops). You need to find a smarter algorithm to find the divisors of 1000! than simply checking for every number whether it divides 1000!.

This post has been edited by sepp2k: 16 April 2012 - 04:53 AM

Was This Post Helpful? 2
  • +
  • -

#5 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7891
  • View blog
  • Posts: 13,418
  • Joined: 19-March 11

Re: Stack Overflow

Posted 16 April 2012 - 08:06 AM

Given tail recursion, you could do this. Java doesn't do tail recursion, though. Try scheme or some other civilized language if you want to do this recursively. Java is too blunt an instrument for your purpose.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2134
  • View blog
  • Posts: 3,274
  • Joined: 21-June 11

Re: Stack Overflow

Posted 16 April 2012 - 08:11 AM

View Postjon.kiparsky, on 16 April 2012 - 05:06 PM, said:

Given tail recursion, you could do this. Java doesn't do tail recursion, though. Try scheme or some other civilized language if you want to do this recursively. Java is too blunt an instrument for your purpose.


Well, as I said, even without any stack space consumption the algorithm won't run in sufficient time for the given input size. So rewriting in scheme won't help him there.
Was This Post Helpful? 0
  • +
  • -

#7 Ryano121  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1362
  • View blog
  • Posts: 3,002
  • Joined: 30-January 11

Re: Stack Overflow

Posted 16 April 2012 - 08:13 AM

Just to run up on sepp2k's point, 1000! has 2568 digits meaning that even in a loop you would have to go around 4E2567 times, it's going to take a VERY long time.

This post has been edited by Ryano121: 16 April 2012 - 08:18 AM

Was This Post Helpful? 2
  • +
  • -

#8 Mobuis1995  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 15-February 12

Re: Stack Overflow

Posted 16 April 2012 - 08:38 AM

Thanks for all your help, everyone. I've decided that I will either solve it in Haskell, and after I submit the right answer, find a smarter algorithm in Java, or if I'm unable to solve this in Haskell, I'll just think of a smarter way in Java.
Was This Post Helpful? 0
  • +
  • -

#9 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7891
  • View blog
  • Posts: 13,418
  • Joined: 19-March 11

Re: Stack Overflow

Posted 16 April 2012 - 08:39 AM

View Postsepp2k, on 16 April 2012 - 10:11 AM, said:

View Postjon.kiparsky, on 16 April 2012 - 05:06 PM, said:

Given tail recursion, you could do this. Java doesn't do tail recursion, though. Try scheme or some other civilized language if you want to do this recursively. Java is too blunt an instrument for your purpose.


Well, as I said, even without any stack space consumption the algorithm won't run in sufficient time for the given input size. So rewriting in scheme won't help him there.



True, not at n=1000!. And clearly when someone says "do this calculation for n=1000!" they mean "don't do this by brute force". But tail recursion allows you to write this recursive function for any input size that you've got the patience to wait for, where a java recursion will bottom out at relatively low numbers.

@OP: consider the definition of factorial...
Was This Post Helpful? 0
  • +
  • -

#10 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: Stack Overflow

Posted 16 April 2012 - 09:17 AM

Here
        if (test.equals(new BigInteger("1")))  
        {  
             return new BigInteger("1");  
        }  



you create 2 big new BigInteger for nothing
        BigInteger one = new BigInteger("1");
        if (test.equals(one))  
        {  
             return one;  
        }  


Would be better, and using the constant one (defined as BigInteger.ZERO) would be even better
        if (test.equals(BigInteger.ONE))  
        {  
             return BigInteger.ONE;  
        }  




As already mentionned your == is wrong and will always return false
So if the number is big, and it should be as you use BigInteger your method will call itself back as many times as your BigInteger is, that can be too much
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1