• Post Reply Bookmark Topic Watch Topic
  • New Topic

Question on sum of syracuse sequence (memorization question)  RSS feed

 
Krystella Fiasse
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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)



Solution 2# : (Recursion)


 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you calling the same method twice without clearing the Map between calls?
 
Krystella Fiasse
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Get the calculations working, leaving the storing until later. You don’'t want to try doing everything at once.
 
Krystella Fiasse
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?




 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your code is really hard to read, but congrats on getting it working.
 
Campbell Ritchie
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56570
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
. . . and why are you starting with a summated length of 1, rather than 0?
 
Krystella Fiasse
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ^^



 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!