[Mobuis1995]

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?

[Casper1]

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.

[Mobuis1995]

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.

[sepp2k]

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

[jon.kiparsky]

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.

[sepp2k]

jon.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.

[Ryano121]

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

[Mobuis1995]

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.

[jon.kiparsky]

sepp2k, on 16 April 2012 - 10:11 AM, said:

jon.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...

[pbl]

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