mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-03-03, 14:19   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·5·23 Posts
Default 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 1059+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.
alpertron is offline   Reply With Quote
Old 2013-03-06, 21:43   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by alpertron View Post
The main problem, as expected, is the speed. For example, when factoring 1059+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. :-)
cheesehead is offline   Reply With Quote
Old 2013-03-19, 11:28   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

138010 Posts
Default

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.
alpertron is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 06:56.


Sat Oct 16 06:56:32 UTC 2021 up 85 days, 1:25, 0 users, load averages: 1.20, 1.15, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.