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[SUP]59[/SUP]+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.

[QUOTE=alpertron;331782]The main problem, as expected, is the speed. For example, when factoring 10[SUP]59[/SUP]+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.[/QUOTE]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. :-)

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.