Porting my factorization applet to Android

alpertron · 2013-03-03, 14:19

Since tablets and smartphones which use the Android operating system cannot access Java applets, I decided to port my factorization applet to be an Android application as an exercise.

At this moment the application can factor numbers, but the batch mode is not ready yet.

The main problem, as expected, is the speed. For example, when factoring 10⁵⁹+213 which is the product of two 30-digit prime numbers, my computer (a 2,53 GHz Core Quad) requires 17 seconds in 32-bit mode and 12 seconds in 64-bits mode when using a single thread. The Coby Kyros MID8048-4 (Cortex A5, 1 GHz) requires 3 minutes and a half to perform the same factorization.

Of course, using the Android NDK I will be able to optimize a lot the code, but I wanted first to use the same Java code in order to compare the execution times.

cheesehead · 2013-03-06, 21:43

Quote:

Originally Posted by alpertron

The main problem, as expected, is the speed. For example, when factoring 10⁵⁹+213 which is the product of two 30-digit prime numbers, my computer (a 2,53 GHz Core Quad) requires 17 seconds in 32-bit mode and 12 seconds in 64-bits mode when using a single thread. The Coby Kyros MID8048-4 (Cortex A5, 1 GHz) requires 3 minutes and a half to perform the same factorization.

There is some famous quotation about an animal trick (IIRC): that the surprise is not how well it can do it, but that it can do it at all. :-)

alpertron · 2013-03-19, 11:28

I found that the main problem in most ARM processors is that they do not include division instruction, so these are simulated by software. This means that a division is equivalent to about 100 multiplications (360 clocks vs 3 clocks for 32-bit operands).

I'm starting to replace division and remainder calculation with multiplications where possible (for example, using Montgomery multiplication). Up to this moment I only used Montgomery multiplication for multiword operands. But it is clear that the algorithm will be needed even for 32-bit operands.

2013-03-03, 14:19	#1
alpertron Aug 2002 Buenos Aires, Argentina 1,447 Posts	Porting my factorization applet to Android Since tablets and smartphones which use the Android operating system cannot access Java applets, I decided to port my factorization applet to be an Android application as an exercise. At this moment the application can factor numbers, but the batch mode is not ready yet. The main problem, as expected, is the speed. For example, when factoring 10⁵⁹+213 which is the product of two 30-digit prime numbers, my computer (a 2,53 GHz Core Quad) requires 17 seconds in 32-bit mode and 12 seconds in 64-bits mode when using a single thread. The Coby Kyros MID8048-4 (Cortex A5, 1 GHz) requires 3 minutes and a half to perform the same factorization. Of course, using the Android NDK I will be able to optimize a lot the code, but I wanted first to use the same Java code in order to compare the execution times.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New online applet for factorization	ET_	Lone Mersenne Hunters	69	2014-06-01 17:34
Porting pari/gp routines into a C program??	EdH	Programming	17	2012-10-30 03:41
porting Prime95 to GTK+?	ixfd64	Software	13	2012-02-21 07:36
Possibly stupid question about porting games to Linux.	jasong	Linux	4	2006-12-23 21:24
Faster factorization applet	alpertron	Factoring	14	2006-01-01 04:00

2013-03-19, 11:28	#3
alpertron Aug 2002 Buenos Aires, Argentina 1,447 Posts	I found that the main problem in most ARM processors is that they do not include division instruction, so these are simulated by software. This means that a division is equivalent to about 100 multiplications (360 clocks vs 3 clocks for 32-bit operands). I'm starting to replace division and remainder calculation with multiplications where possible (for example, using Montgomery multiplication). Up to this moment I only used Montgomery multiplication for multiword operands. But it is clear that the algorithm will be needed even for 32-bit operands.