How to test your cell phone warranty

[starrynte]

I instead wrote another LL midlet, the one in the link appears to be down, here are results from my midlet:

M13 | 0.4 sec
M14 | 0.6 sec
M15 | 3.7 sec
M16 | 18.4 sec
M17 | 18.5 sec

the phone's processor is an ARM OMAP 730 (the phone is a smart phone made by Qtek)
possibly my midlet is faster? try it on your phones (I am still speeding up the code but this is good enough for now)
(attached zip contains the JAD and JAR file)


It wouldn't be too hard to change it to LLR (at least for the starting values described at http://en.wikipedia.org/wiki/Lucas-Lehmer-Riesel_test ), so if you want me to add that...
Also speaking of LLR, two questions:
1) Do all LLR tests perform <exponent - 2> iterations?
2) Can you do (mod k * 2^n - 1) after each iteration for
i) only where k=1?
ii) all LLR tests?
iii) something else?

[starrynte]

New and improved version featuring:
- Bar showing how far done it is in the test (for a slight cost of performance, but that's outweighed by
- A bit faster testing overall

Try it!
(I will attempt to test M23 also...)

[starrynte]

M23 finished in 25 minutes 34 seconds :)
on to M24...

[starrynte]

M24 finished in around 2 hours 5 minutes, I didn't get the exact time.

[henryzz]

lots faster
Mersenne | Sony Ericsson W810i
M13 | 1.3 sec
M14 | 1.8 sec
M15 | 13 sec
M16 | 1 min 5 sec
M17 | 1 min 13 sec
M18 | 3 min 25 sec
M19 | 22 min 20 sec

i still think i have a slow phone though

[henryzz]

ignore the timing for M19
when i am inactive on my phone it pauses a program if i has anything graphical(i.e. the progress bar)
just the text output the other program did was fine i think

[starrynte]

ok
expect a much smaller and faster version some time this week

(I found a faster way to do modulus,
a % 2^n - 1 = (a + 2^n - 1 * (a % 2^n)) / 2^n
and of course a % 2^n = a & (2^n - 1), and dividing by 2^n = shift right n bits
)

[starrynte]

need some help
I have no static initializers at all, yet when i try to run it (on the emulator) i get:
java.lang.Error: Static initializer: java/lang/IllegalStateException
Is it the emulator's fault?

[starrynte]

nvm
here is temporary release (is not text-only yet) but much faster and smaller and is threaded (gui isn't locked).
new benchmarks:

Mersenne | New | Old
M13 | 0.4 sec | 0.4 sec
M14 | 0.5 sec | 0.6 sec
M15 | 2.9 sec | 3.7 sec
M16 | 12.4 sec | 18.4 sec
M17 | 13.2 sec | 18.5 sec

Also reposting questions:
1) Do all LLR tests perform <exponent - 2> iterations?
2) Can you do (mod k * 2^n - 1) after each iteration for
i) only where k=1?
ii) all LLR tests?
iii) something else?

[Damian]

It's been a while since I didn't come back to the forum.

I was glad to see that some more tests and even a new midlet has been done.

I tested it and it effectively is faster than my midlet (actualy 12x faster)


I made some test on my new phone (a Sony F305), this are the results:

#    Mersenne  My old midlet     starrynte's midlet ratio
m13 | M521   | 4 sec           | 0.38 sec         | 10.52
m14 | M607   | 6.1 sec         | 0.54 sec         | 11.29
m15 | M1279  | 51.94 sec       | 4.29 sec         | 12.10 
m16 | M2203  | 4 min 19.99 sec | 20.58 sec        | 12.63
m17 | M2281  | 4 min 48.32 sec | 23.11 sec        | 12.47
m18 | M3217  | 13 min 24.66 sec| 1 min 2.57 sec   | 12.86

Also, I compared the benchmarks on the different phones with starrynte's midlet (in seconds)

F305    w810i   ARM730  
0.38  | 1.3   | 0.4
0.54  | 1.8   | 0.6
4.29  | 13    | 3.7 
20.58 | 65    | 18.4
23.11 | 73    | 18.5

So a comparisson matrix would be


where would be how fast is phone i compared to phone j
where
0 = f305
1 = w810i
2 = ARM730

Does this kind of matrix have a name? It has the property that
Does it have other properties? What I can see is that the fastest phone is the ARM730

My LLMidlet code wasn't optimized, in case somebody is interested, this is the main routine I used:

	private int esPrimo(int n) {
		int rq = (int) Math.sqrt(n);
		for (int i = 2; i <= rq; i++) {
			if (n % i == 0)
				return 0;
		}
		return n;
	}

	
	private void esPrimoMersenne(int expo) {
		
		if(expo == 2) {
			this.print("M2 es primo");
			return;
		}
		
		int gap = 10;
		int porcAnt = 0;

		int n = esPrimo(expo);
		
		if(n != 0) {
			
			BigInteger Mp = BigInteger.valueOf(2).pow(n);
			Mp = Mp.add(BigInteger.valueOf(-1));
			BigInteger s = BigInteger.valueOf(4);
			for (int j = 2; j < n; j++) {
				
				int porc = (j*100/n);
				if(porc - porcAnt > gap) {
					this.print("va por: " + (j*100/n) + "%");
					porcAnt = porc;
				}

				s = s.pow(2);
				s = s.add(BigInteger.valueOf(-2));
				s = s.mod(Mp);
				if (s.equals(BigInteger.valueOf(0))) {

					this.print("M" + n + " es primo");
					return;
				}
			}		
			
		}
		
		this.print("M" + expo + " no es primo");


	}

Hope to read responses and more benchmark tests!

[starrynte]

Ah, I totally forgot about the midlet...time to try to implement my hopefully faster version of modulus...
And/or, I can start a TF midlet in the near future :)

Looking at your code, if automatically saying composite exponents isn't "cheating", I'll add that. (I know that the exponent has to be prime, just wasn't sure if that would be "cheating")