Java - rotating int/string

Tar.Aldarion

Was wondering what is the best/efficient way to rotate strings/ints in java.

Say I have a linkedlist of a hundred ints of various lengths and I want to rotate each of them until they are in the position where the next rotate would be the original position again?

so 791 -> 917 -> 179 and stop.



I wrote a program to generate primes, storing them in a list and am messing about rotating the positions of the digits and seeing if they are still prime.

If they are not, remove them and all possible rotations from the list. ie creating a list of rotational primes.

fergalr

Tar.Aldarion wrote: »

Was wondering what is the best/efficient way to rotate strings/ints in java.

Say I have a linkedlist of a hundred ints of various lengths and I want to rotate each of them until they are in the position where the next rotate would be the original position again?

so 791 -> 917 -> 179 and stop.



I wrote a program to generate primes, storing them in a list and am messing about rotating the positions of the digits and seeing if they are still prime.

If they are not, remove them and all possible rotations from the list. ie creating a list of rotational primes.

How efficient do you want to get?

Processors tend to have operations to do Bitwise rotation, which could be used to implement what you want. I'm not sure what java gives access to, but if you need to do a *lot* of these, you probably want to go down that road. (or even look at gpgpu..)

This article describes what you are trying to do, and has (non standard) C code for it:
http://en.wikipedia.org/wiki/Circular_shift

Seeing as there is actual instruction support, it is probably going to be way more efficient than a high level solution in java.

for java: http://stackoverflow.com/questions/5844084/java-circular-shift-using-bitwise-operations

Procasinator

Tar.Aldarion wrote: »

Was wondering what is the best/efficient way to rotate strings/ints in java.

Say I have a linkedlist of a hundred ints of various lengths and I want to rotate each of them until they are in the position where the next rotate would be the original position again?

so 791 -> 917 -> 179 and stop.



I wrote a program to generate primes, storing them in a list and am messing about rotating the positions of the digits and seeing if they are still prime.

If they are not, remove them and all possible rotations from the list. ie creating a list of rotational primes.

You may be wanting to ask what is the most efficient way to detect a circular prime rather than the most efficient way to rotate numbers.

As for the fastest algorithm to simply do all rotations, I don't know. You'd have to analyse the actual steps produced.

One way of doing it (could be pretty inefficient):

int num = 179;
int divisor = 10;
int rotations = 0;
while (num > divisor) {
	divisor *= 10;
	rotations++; // could derive from divisor/10.
}

divisor = divisor / 10;

while (rotations > 0) {
	int firstDigit = num/divisor;
	num = (num - (firstDigit*divisor)) * 10 + firstDigit;
        // num is now rotated
	System.out.println(num);
	rotations--;
}

(May not compile, don't have JDK handy).

Procasinator

fergalr wrote: »

How efficient do you want to get?

Processors tend to have operations to do Bitwise rotation, which could be used to implement what you want. I'm not sure what java gives access to, but if you need to do a *lot* of these, you probably want to go down that road. (or even look at gpgpu..)

This article describes what you are trying to do, and has (non standard) C code for it:
http://en.wikipedia.org/wiki/Circular_shift

Seeing as there is actual instruction support, it is probably going to be way more efficient than a high level solution in java.

for java: http://stackoverflow.com/questions/5844084/java-circular-shift-using-bitwise-operations

A circular shift will work on the bit level, not the digit level, no?

fergalr

I haven't really thought this through, posting in a hurry.

Procasinator wrote: »

A circular shift will work on the bit level, not the digit level, no?

It does, yeah - but lets say you've got your base ten digits, 0-9, you can encode them (slightly wastefully) as 4 bits each, right?

On a 64bit machine, which is typical these days, you can fit 16 such digits into the 64 bits. That gives you numbers between 0 and 10^16.

So,there are CPU instructions that will do the rotational shift for you, in x64. A single rotational shift of the 64bit number, by 4 positions, is equivalent to shifting the 16digit decimal number by one position, right?
And its very fast, as its a single op.


Now, the disadvantage of an encoding scheme is that you've got to pack and unpack your numbers.
I presume that the OP wants to do a primality test on each of the numbers.

But, probably the best way to do this, is to generate the list of prime numbers, in the range desired, before running the algorithm.
These could then be stored, in the same encoding scheme, as the numbers ready for rotation.

With such a list, a test of each cycled number, against the existing list of primes, would be just a bitwise AND. (Presumably you'd store the list of primes sorted in some form that would enable you to hash into, or binary search through; or maybe have a bloom filter first, very simple to implement in this space)


I dunno - is this approach efficient? I think it depends on the relative length of the cycles, vs. encoding, vs storing the list of primes. Obviously, its only good for numbers between 0 and 10^16.

With information on the parameters in which the OP wants to search, we could do some back of the envelope calculations on whether it makes sense.

I guess just do it simply first, and see if that's fast enough.

Unregistered.

Tar.Aldarion wrote: »

so 791 -> 917 -> 179 and stop.

A suggestion using above example, using strings :

/* e.g. String num = 791 */

substr. = num.substring(0,1);          // substring of size 2, of first to chars
                                       // substr = "91";    

num[0] = num[2];                       // swap first and last digit
                                       // num = "797";
num[2] = substr[1];                    // num = "997";
num[1] = substr[0];                    //  num = "917";

I guess at this point you'd need to cast to an int and check if it's a prime before next rotation?

Also note that this example assumes a number of length 3. Can obv. be modified to work in all cases

tehjimmeh

Could you do something like generate primes, rotate the digits in each number to some canonical form, like the largest number possible, for example (my initial thought was sort the digits, but that would destroy ordering), then sort the resulting list of numbers. Once you've done that, do one pass through the list and eliminate any number where the number of occurrences != the number of digits?

Pygmalion

If you have say a 10 digit number, store it twice (i.e. as a 20 digit string), then take 10 digit substrings from each position.

i.e for the number 1234567890
The string is 12345678901234567890.
string[0:10] = 1234567890.
string[1:11] = 2345678901.
...
string[9:19] = 0123456789.
etc.

No need to actually do any rotations each time.
If doing it in a language that uses C strings it might be a bit more convenient to store it once, with the rest of the space filled with nulls, then simply move the start of one string to the terminating null byte and advance pointer, so that the string functions still work.
i.e.

[b]1[/b]2345\0\0\0\0\0
1[b]2[/b]3451\0\0\0\0
12[b]3[/b]4512\0\0\0
123[b]4[/b]5123\0\0
1234[b]5[/b]1234\0

Where bold indicates the start of the string, strlen() at each step returns 5 and strcpy() will copy what you want.

Procasinator

OP, I originally said:

You may be wanting to ask what is the most efficient way to detect a circular prime rather than the most efficient way to rotate numbers.

The reason why is that there might be more efficient manner to detect a circular prime than trying all it's rotations.

For instance, a circular prime can only have the digits 1, 3, 7 and 9. The reason being that if 2, 4, 6, 8 are the last digit, the number is divisible by 2 and when 0 or 5, the number is divisable by 5.

Knowing this fact you can do a quick check to eliminate the number as a circular prime, without doing all the rotations - just check every digit (whether you use string or divisions/modulus to go through each digit is up to you).

After that, you can do the rotations on each number. Check each number is a prime by binary-searching first through your list of already found circular primes then your list of primes (assuming your range takes all of them, which if you are doing Project Eulers Problem 35 it should be). If you find it, append it to the list of circular primes.

That is how I would do it. The rotation method of course is still needed, but you can avoid it when not needed.

Whether or not you use the rotations with strings (like Unregistered or Pygmalion) or maths, or use something like felgalr encoding - you'd have to check what actually is faster. I would imagine there is some penalty with int -> string and back again That, and in Java Strings are immutable so you will be creating them new for each rotation.

The encoding, you could probably do with Java's double (64-bit). Double doesn't have a rotateRight like Integer in Java, but you could implement it yourself like in the StackOverflow article.

tehjimmeh

Procasinator wrote: »

Knowing this fact you can do a quick check to eliminate the number as a circular prime, without doing all the rotations - just check every digit (whether you use string or divisions/modulus to go through each digit is up to you).

Or just take it into account when generating them in the first place. Only check for primality in:

These:
1,3,7,9

These plus each one of the group above:
10,30,70,90

These plus each of the primes generated in the last step:
100,300,700,900

etc.

Tar.Aldarion

thanks guys, nice answers, great to have a think about all the different ways to do it and try them out!