Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes forum!

since Jun 14, 2008

Cows and Likes

Cows

Total received

0

In last 30 days

0

Total given

0

Likes

Total received

9

Received in last 30 days

0

Total given

0

Given in last 30 days

0

Forums and Threads

Scavenger Hunt

Ranch Hand Scavenger Hunt

Greenhorn Scavenger Hunt

It is possible.

java.util.Collection contains a retainAll method. Using retainAll prevents you from having to iterate the collection but retainAll will probably be iterating the collection internally.

java.util.Collection contains a retainAll method. Using retainAll prevents you from having to iterate the collection but retainAll will probably be iterating the collection internally.

9 years ago

The main problem is that your is not a constructor definition. That is why the compilation error alludes to the "int i" constructor not being defined.

Hint: constructors do not define a return type. Have a look at the Java Tutorials for more info.

Hint: constructors do not define a return type. Have a look at the Java Tutorials for more info.

11 years ago

I think what Stephan is getting at is that you can replace:

with:

thus improving the readability of your code.

with:

thus improving the readability of your code.

11 years ago

mick lynch wrote:...I need to learn a computer language ...

If you are completely new to Java then I'd recommend keeping away from an IDE to start with. Use a text editor (notepad, notepad++, textpad etc) and compile from the command line to keep it simple to begin with. You can then learn how to use an IDE once you understand the basics of the language.

Java Tutorials

11 years ago

IllegalArgumentException would seem to be a good choice here. You could subclass it if you want to make the exception even more specific.

11 years ago

I don't know of any specific lwjgl tutorials but the NeHe tutorials will give a good grounding in opengl. Most of the lessons have lwjgl source code attached. Not sure about the other components of lwjgl.

If you are not familiar with games programming then I suggest forgetting about lwjgl for now and learning some basic game programming techniques. Developing Games in Java and Killer Game Programming in Java are good starting points.

If you are not familiar with games programming then I suggest forgetting about lwjgl for now and learning some basic game programming techniques. Developing Games in Java and Killer Game Programming in Java are good starting points.

11 years ago

The BitSet is more efficient in terms of memory usage - no argument there. However both BitSet and boolean[] will hit the limit soon enough of being indexed by an int.

Arbitrarily allocating Xmx768m, my boolean[] can handle 1e9 in 15s with the BitSet in 36s. The point being 1e9 is approximately half of Integer.MAX_VALUE. So why did I stop at 1e9 and not go on to Integer.MAX_VALUE? My implementation doesn't contain even numbers in the sieve so requires an i*2 calculation to work out the real number from the index (see earlier posts) so 1e9 is approximately the max value I can handle without recoding. So with recoding then memory requirement would be fulfilled by Xms1536m. I'm not advocating always chucking more memory at a problem but in this instance IMHO the inherent Integer.MAX_VALUE limit is more of a concern than the memory efficiency.

Arbitrarily allocating Xmx768m, my boolean[] can handle 1e9 in 15s with the BitSet in 36s. The point being 1e9 is approximately half of Integer.MAX_VALUE. So why did I stop at 1e9 and not go on to Integer.MAX_VALUE? My implementation doesn't contain even numbers in the sieve so requires an i*2 calculation to work out the real number from the index (see earlier posts) so 1e9 is approximately the max value I can handle without recoding. So with recoding then memory requirement would be fulfilled by Xms1536m. I'm not advocating always chucking more memory at a problem but in this instance IMHO the inherent Integer.MAX_VALUE limit is more of a concern than the memory efficiency.

11 years ago

Paul Beckett wrote:Think about your conditional logic. Hint: You have four conditions, the first two are "equal" and "not equal".

I was trying to give you a nod in the right direction without giving you the full answer so I'll rephrase (from your original code, and assuming "==" is going to work correctly):

Condition 1: myEntry!=myRandom

Condition 2: myEntry==myRandom

Condition 3: myEntry.substring(1,2) == myRandom.substring(1,2)

Condition 4: myEntry.substring(0,1) == myRandom.substring(0,1)

With myEntry=123, myRandom=123 then condition 2 is executed //equal

myEntry=123,myRandom=456 then condition 1 is executed //not equal

myEntry=123,myRandom=124 then condition 1 is executed //not equal (first 2 numbers same)

myEntry=123,myRandom=923 then condition 1 is executed //not equal (second 2 numbers same)

So as you can see, all possible results are covered by conditions 1 and 2. Conditions 3 and 4 cannot be reached. Make sense now?

11 years ago

Campbell Ritchie wrote:Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers

The sieve I posted in my second post is a fully functioning sieve minus the method declarations.

My version of the sieve was for solving the project euler problem 10 and doesn't need a printing method for that purpose. In my third post I did provide the complete summing functionality which shows how to convert an array element to a prime number. Also I provided a "diagram" of the sieve, the array indexes, and the corresponding number the array index represented.

11 years ago

you didn't copy anything incorrectly. The implementation you have used of my version of the sieve is correct I think. It is the printPrimes method that is incorrect. You are printing out the index of any "true" in the array. Whereas in my implementation of the sieve, "false" is a prime. And then instead of the index of the "false" elements you need to use 2i+1 to find the real number and start iterating at index 1.

Obviously you have identified a big flaw in the method I've used - its difficult to understand what is going on!!! However this is a java implementation of the method from Project Euler problem 10 solution pdf (section 10.2.2). I prefer to make code readable as a first priority and then only reduce readability to optimise if absolutely necessary but for project euler execution speed seems to be the priority over all others.

Obviously you have identified a big flaw in the method I've used - its difficult to understand what is going on!!! However this is a java implementation of the method from Project Euler problem 10 solution pdf (section 10.2.2). I prefer to make code readable as a first priority and then only reduce readability to optimise if absolutely necessary but for project euler execution speed seems to be the priority over all others.

11 years ago

Think about your conditional logic. Hint: You have four conditions, the first two are "equal" and "not equal".

11 years ago

Campbell Ritchie wrote:Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?

I seemed to get a different result from yours when I printed the numbers out.

I didn't include it before but my summing is done like so:

So a prime is false, don't think it matters which way round you do it. With prime = false then I don't need to explicitly set every value in the array to true before sieving.

The array doesn't contain even numbers so have to handle 2 as a special case. Other than that the value in the array at index i represents the number 2i+1, so index 3 represents the number 7.

Where maxNumber=12:

sieve: [false, false, false, false, true]

index: [ 0, 1, 2, 3, 4]

numbers: [ 1, 3, 5, 7, 9]

Obviously 1 is not a prime number so notice that when iterating the sieve always start at index 1.

Also my sieveBound should have been limit/2 instead of "(limit-1)/2".

11 years ago

I think the squaring allows for that. But surely it is simpler to use the square root?

ok, I'd missed that bit

Using the square root would be more efficient in this case. So work out the square root of the end number (crosslimit) before the loop and then the termination expression becomes "end<crosslimit".

Using a boolean array you can change your increment expression to increment the loop by the number you are currently removing multiples of (runningPrime in the original code).

My algorithm takes <1.5 seconds to work out all the primes 1e8 but also gets an OutOfMemoryError with 1e9. Obviously the time taken is relative to the performance of the machine.

My version of the sieve:

11 years ago

see problem 10 "Calculate the sum of all the primes below two million" on projecteuler.net. If you can solve the problem then a solution pdf is provided giving hints (including pseudo code) for how to efficiently do a sieve (solves in much less than a second on a modest PC). Your code should be more than sufficient to solve the problem and is way more efficient than my first attempt where I didn't even use a sieve. The solution pdf will explain things much more eloquently than I could here.

Note: Campbell is correct to use a boolean[] but this can be optimized even further thus reducing the size of the array.

(i) no even number other than 2 can be a prime

(ii) can you reduce the max number you need to check for?

Note: Campbell is correct to use a boolean[] but this can be optimized even further thus reducing the size of the array.

(i) no even number other than 2 can be a prime

(ii) can you reduce the max number you need to check for?

11 years ago