Question on sum of syracuse sequence (memorization question)

[Krystella Fiasse]

Hi all,
I've spent a lot of time on this question and am getting close to finishing it... only to find out that my code couldn't handle an input that is greater than 500000 causing StackOverFlowException. It makes me sad because my hardwork didn't get me anywhere. Heres the question :

The lengths method from question 2 will usually take a long time to calculate the sum of lengths when its input value n is greater than 500 000. To make it faster we can take advantage of the fact that there is considerable overlap between many sequences. For example: if we have already calculated lengths(3) then we must have computed the sequence:
3 10 5 16 8 4 2 1
and would, threfore, also have had access to answers to lengths(10),lengths(5), lengths(16),lengths(8),lengths(4),lengths(2), and lengths(1). If we can store at least some of these temporary solutions as we go, and then use them, when possible, then the speed of lengths is greatly increased.
In a file called SyraLengthsEfficient.java write a new version of lengths that behaves the same way as the lengths from question two above, but is able to work much faster for large numbers by memorising some partial solutions.

Hint

This new syraLength and it's encapsulating class must contain the code necessary to remember and recall the values of some intermediate lengths.

My Solution #1: (Iterative)

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class SyraLengthsEfficient {

    HashMap<Integer, Integer> memory = new HashMap<Integer, Integer>();

    public long lengths(int n) throws IllegalArgumentException
    {
        long lengthSum=0;
        int length=1; // To count the length of syracuse sequences
        if(n<1) // Exception case (n less than 1)
        {
            throw new IllegalArgumentException();
        }

        for(int i = 1; i<=n; i++) // This loop is used to calculate the previous syracuse sequence till n.
        {
            int x = i; // Let x be i
            
            {
                while(x>1) // While x is not 1
                {
                    if(memory.get(i) == null)
                    {
                    if(x==1)
                    {
                        memory.put(i,length);
                        lengthSum+=length;
                        length=1;
                    }else if(x%2==0) // If x is even, x=x/2. Increment length
                    {
                        length++;
                        x=x/2;
                    }else{ // If x is odd, x=(x*3)+1. Increment length
                        length++;
                        x=(x*3)+1;
                    }
                    }else{
                        memory.get(i).intValue()
                    }
                }
                
            }else{
                lengthSum+=memory.get(i).intValue();
            }

        }

        return lengthSum; // Return the total length of the Syracuse Sequence
    }


}

Solution 2# : (Recursion)

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class SyraLengthsEfficient {

    HashMap<Integer, Integer> memory = new HashMap<Integer, Integer>();

    public long lengths(int n)throws IllegalArgumentException
    {
        long lengthSum = 0;
        // If n is less than 1, throw an IllegalArgumentException
        if(n < 1)
        {
            throw new IllegalArgumentException();
        }else{
        // Otherwise, call the helper method, syra
            for(int i=1;i<=n;i++)
            {
                if(memory.get(i)==null)
                {
                    memory.put(i,syra(i,1));
                    lengthSum+=memory.get(i).intValue();
                }else{
                    lengthSum+=memory.get(i).intValue();
                }
            }
            return lengthSum;
        }

    }

    private int syra(int n, int length)
    {
        // If n becomes 1, return the length of the Syracuse sequence.
        if(n==1)
        {
            return length;
        // If n is even, return syra(n/2, ++length)
        } else if(n%2 == 0){
            return syra(n/2, ++length);
         // If n is odd, return syra(n/2, ++length)
        } else {
            return syra((n*3)+1, ++length);
        }

    }

}

[Campbell Ritchie]

Please write down the algorithm you are using for the Syracuse sequence, because most people here are not familiar with it.
You will have to work out whether you are putting things on the stack and whether you are taking them off, but you can only do that when you know how the algorithm works.

And welcome to the Ranch

[Krystella Fiasse]

Campbell Ritchie wrote:Please write down the algorithm you are using for the Syracuse sequence, because most people here are not familiar with it.
You will have to work out whether you are putting things on the stack and whether you are taking them off, but you can only do that when you know how the algorithm works.

And welcome to the Ranch

.

Thanks Ritchie!

Syracuse number is a special sequence where by if the number (x) is even,the next number generated will be x/2.
When the number (x) is odd, the next number generated will be (x*3)+1
It will, however stop when the number x) reaches 1, the base case.

This is an example of the whole syracuse sequence when x is 3, starting from x:
3 10 5 16 8 4 2 1 (There is 8 numbers here, so length is 8)

My algorithm would need to compute the sum of length in each sequence starting from 1 to n and be able to somehow save the intermediate results (the count length) and finally find a way to add them together to return the correct result.

Eg, if n=3, calculate the sequence and return the total length

1 (n=1)
2 1 (n=2)
3 10 5 16 8 4 2 1 (n=4)
I should return 11 as there are exactly 11 elements from n=1 to n=3.

with the hashmap, what I was doing was to save the sequence if it hasn't been saved before.


I'm able to get the length to add up properly but wasn't able to find a solution to "store" these intermediate results AND/OR my code was unable to withstand the large value of n thrown to me (They are using large values for n like around 500,000 range).

[Campbell Ritchie]

500000 is not really a large number.
Which version throws the Exception? Is it the recursive one? I got such an Exception about 150000 with the recursive version, which suggests there is not enough space on the stack for that many calls. The stack is usually considerably smaller than the
By the way, you should check your code style; you have inconsistent indentation and not used enough spaces (eg around binary operators); the inconsistent indentation means you have got a } out of place in the non-recursive version so it won’t compile. Please always use copy-and-paste to post code; that would have prevented such a mistake.

[Campbell Ritchie]

There is a lot more wrong with the non-recursive version. You have while (n > 1) ... with if (n == 1) nested inside it. You have unbalanced wihle and if-elses. Please copy and paste the real thing. Does that throw any Exceptions?

[Krystella Fiasse]

Sorry, I was trying to edit the code earlier to make it be able to store those results in the hashmap and I think it caused some compilation errors.

This is the code that compiles, able to run but on the second method call onwards it will return 0, also I couldn't figure out the algorithm to store and retrieve them properly.

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class SyraLengthsEfficient {

    HashMap<Integer, Integer> memory = new HashMap<Integer, Integer>();

    public long lengths(int n) throws IllegalArgumentException
    {
        long lengthSum=0;
        int length=1; // To count the length of syracuse sequences
        if(n<1) // Exception case (n less than 1)
        {
            throw new IllegalArgumentException();
        }

        for(int i = 1; i<=n; i++) // This loop is used to calculate the previous syracuse sequence till n.
        {
            int x = i; // Let x be i

                if(memory.get(i) == null)
                {
                    while(x>1) // While x is not 1
                    {
                        if(x%2==0) // If x is even, x=x/2. Increment length
                        {
                            length++;
                            x=x/2;
                        }else{ // If x is odd, x=(x*3)+1. Increment length
                            length++;
                            x=(x*3)+1;
                        }
                    }
                        memory.put(i,length);
                        lengthSum+=length;
                        length=1;
                 }else{
                    memory.get(i).intValue();
                }
        }

        return lengthSum; // Return the total length of the Syracuse Sequence
    }


}

[Campbell Ritchie]

What’s this about 0? Even before looking at the code, I thought, “has she still got the while (n > 1) and if (n == 1) together?”

[Campbell Ritchie]

No, you have got rid of that bit.

I got it to work up to 1000000, but at 10000000 it exhausted my available heap space. You could try to write the values into a text file, database, etc. You could consider whether you need the Map at all. You should also consider whether you need the if (... == null) ... else because the value in the Map is bound to be null at that stage.

[Campbell Ritchie]

Are you calling the same method twice without clearing the Map between calls?

[Krystella Fiasse]

Yes, I am wondering if there is a better way to lookup on the past calculation results, text is definitely out because we aren't supposed to submit additional files other than the .java and .class. Actually this is my first time using hashmap too and I'm confused to what I'm doing, just wanted to get the storing and retrieving correct , tried putting the retrieving and storing code to several different places but couldn't work.

[Campbell Ritchie]

Get the calculations working, leaving the storing until later. You don’'t want to try doing everything at once.

[Krystella Fiasse]

Yes....after discussing with my classmates he shared with me a better idea which I had then formed into code... calling 1+syra(etc....etc...) way more useful than keeping track of the count of length, which I did ... I also did follow the part-by-part basis which you've told me and I actually got it working. Though it's a bit slow I think it took about 15-20 seconds to execute. I wonder if theres anything I could do to optimize the code to make it run faster?

public class SyraLengths {

    public int lengths(int n) throws IllegalArgumentException
    {
        int sumLength=0; // To count the length of syracuse sequences
        if(n<1) // Exception case (n less than 1)
        {
            throw new IllegalArgumentException();
        }else{
            for(int i=1;i<=n;i++)
            {
                sumLength+=syra(i); // Call and add the result of syra(i) to sumLength
            }
        }
        return sumLength; // Return the total length back to the caller
    }

    private int syra(int n)
    {
        if(n==1) // Base case 1: If n becomes 1, return the total length of the Syracuse sequence.
        {
            return 1;
        }else if(n%2==0){ // Recursive case 1: If n is even, return 1+syraLength(n/2L)
            return 1+syra(n/2);
        }else{ // Recursive case 2: If n is odd, return 1+syraLength((n*3L)+1L)
            return 1+syra((n*3)+1);
        }

    }

}

[Joanne Neal]

Just to be clear - you have taken Campbell's advice to just get the calculations working and are leaving the storage part of the problem to later ? This isn't your final solution is it ?

[Campbell Ritchie]

Good grief, Joanne! Are you suggesting anybody ever follows my advice?

Do you have to put all the values into a Map? Can you get away with an int[]? can you use the ?: operator to get rid of the multiple returns? Do you know about replacing the % operator with bitwise &?

[Krystella Fiasse]

I've managed to get the code to work finally on n=500000, campbell !!
But now it's running a bit slow so I probably would need a faster algorithms to do that.
And actually no, we haven't learned ?: and not really sure how & might be able to replace the %2 in my program
http://www.roseindia.net/java/master-java/java-bitwise-and.shtml
I read this and it seems to work on small bits only... really think that this practical is too tough for me to digest o.0

public class SyraLengthsEfficient {

    private long a[];

    public long lengths(int n) throws IllegalArgumentException
    {
        a = new long[n+1];
        long sumLength=1; // To count the length of syracuse sequences
        if(n<1) // Exception case (n less than 1)
        {
            throw new IllegalArgumentException();
        }else{
            for(int i=n;i>1;i--)
            {
                a[i]=syra(i,i); // Call and add the result of syra(i) to sumLength
                sumLength += a[i];
            }
        }
        return sumLength; // Return the total length back to the caller
    }

    private long syra(long n,long largest)
    {
          if(n>=largest || n<1)
          {
              if(n<1L)
              {
                throw new IllegalArgumentException();
              }
              if(n==1L) // Base case 1: If n becomes 1, return the total length of the Syracuse sequence.
              {
                  return 1L;
              }else if(n%2==0){ // Recursive case 1: If n is even, return 1+syraLength(n/2L)
                  return 1L+syra(n/2L, largest);
              }else{ // Recursive case 2: If n is odd, return 1+syraLength((n*3L)+1L)
                  return 1L+syra((n*3L)+1L, largest);
              }
          }else if(a[(int)n]!=0L){
              return 1+a[(int)n];
          }else{
              if(n==1L) // Base case 1: If n becomes 1, return the total length of the Syracuse sequence.
              {
                  return 1;
              }else if(n%2==0L){ // Recursive case 1: If n is even, return 1+syraLength(n/2L)
                  return 1L+syra(n/2L, largest);
              }else{ // Recursive case 2: If n is odd, return 1+syraLength((n*3L)+1L)
                  return 1L+syra((n*3L)+1L, largest);
              }
          }

    }

}

[dennis deems]

Your code is really hard to read, but congrats on getting it working.

[Campbell Ritchie]

That Roseindia link is pretty useless.
I suspect the code will run in quadratic complexity (or if you are lucky nlogn complexity), so you ought not to be surprised about slow execution. It is worth Googling for Syracuse sequence and reading what you find. That gives hints about maximum lengths of the sequences.
Why have you changed from int arithmetic to long arithmetic?
Dennis Deems is right; your code is poorly formatted and that will lose you marks. I have already told you about that myself.

[Campbell Ritchie]

. . . and why are you starting with a summated length of 1, rather than 0?

[Krystella Fiasse]

Because when I look at the results all of them seems to be 1 count lesser. I tried formatting it to look better so now no code repeats like the previous one. I used a specific identing style and put 4 space if I start another branch. Does it still look bad now?

I'll read up on that tomorrow.........12.08AM, 5th continuous day that I receive <6hrs rest doing this assignment...well theres 5 other questions but o well

Night all and thanks for the support ^^

public class SyraLengthsEfficient {

    private long a[];

    public long lengths(int n) throws IllegalArgumentException
    {
        long sumLength=1; // To count the length of syracuse sequences
        if(n<1) // Exception case (n less than 1)
        {
            throw new IllegalArgumentException();
        }else{
            a = new long[n+1];
            for(int i=n;i>1;i--)
            {
                a[i]=syra(i,i); // Call and add the result of syra(i) to sumLength
                sumLength += a[i];
            }
        }
        return sumLength; // Return the total length back to the caller
    }

    private long syra(long n,long largest)
    {
          if(n<=largest)
          {
              if(a[(int)n]!=0L)
              {
              return 1+a[(int)n];
              }
          }

          if(n<1L)
          {
            throw new IllegalArgumentException();
          }
          if(n==1L) // Base case 1: If n becomes 1, return the total length of the Syracuse sequence.
          {
              return 1L;
          }else if(n%2==0){ // Recursive case 1: If n is even, return 1+syraLength(n/2L)
              return 1L+syra(n/2L, largest);
          }else{ // Recursive case 2: If n is odd, return 1+syraLength((n*3L)+1L)
              return 1L+syra((n*3L)+1L, largest);
          }

    }

}