Welcome to the Java Programming Forums
The professional, friendly Java community. 21,500 members and growing!
The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.
>> REGISTER NOW TO START POSTING
Members have full access to the forums. Advertisements are removed for registered users.
LinkBack URL
About LinkBacks
Factoring
How fast is a good time to factor the highest number for a long: 9,223,372,036,854,775,807? Using my algorithm on my laptop with a core i5 @ 2.79 gHz, I got the factors (not just primes) and sorted them from least to greatest in 25.270 seconds; 25.611 seconds without sorting... It's usually faster when it has to order the number, why is that?
Is this a good time or could it be faster?
Last edited by aesguitar; June 1st, 2012 at 02:08 PM.
Related threads:
Re: Factoring
It all depends. Is this fast enough for your application? It could take 10 minutes but if the method is only called once a day it may not matter to your application. If it is being called every 15 seconds then your algorithm isn't fast enough.
I'm afraid that these questions are not really useful in the abstract. There are too many other variables. If you've got a fixed number then the absolute fastest algorithm will be a pre-calculated fixed array of factors that will take basically zero seconds. But is that the "right" algorithm? I don't know - it's up to your application.
Need Java help? Check out the HotJoe Java Help forums!
copeg (June 2nd, 2012)
Re: Factoring
It's just a method for pumping out the factors of a number, ie 12 would give 1 2 3 4 6 12. I tweaked it a little more and got it down to 21 seconds. 20.95 to factor and .05 to sort, estimate. I was more wondering how good this may stack up to a more researched algorithm. Here it is if you want to take a look at it:
public static ArrayList<Long> sortedFactor(long num) { long start = System.currentTimeMillis(); factors.removeAll(factors); int inc = 1; if(num%2!=0) { inc=2; } for(long i = 1; i<=Math.sqrt(num);i+=inc) { if(num%i==0) { long factor = num/i; factors.add(i); if(factors.contains(factor)==false) factors.add(factor); } } long stop = System.currentTimeMillis(); System.out.println(stop-start); return sort(factors); } private static ArrayList<Long> sort(ArrayList<Long> a) { long start = System.currentTimeMillis(); int size = a.size(); ArrayList<Long> sort = new ArrayList<Long>(); for(long l : a) { sort.add(l); } a.removeAll(a); for(int i = size; i > 0; i--) { a.add((long) 0); } int index = 0; while(a.contains((long) 0)) { for( long c : sort) { index = 0; for(long b : sort) { if( c > b) { index++; } } a.set(index, c); } } long stop = System.currentTimeMillis(); System.out.println(stop-start); return a; }
there is an arraylist named factors that holds the values.
Re: Factoring
Researched algorithms are typically reported using time complexity using Big-O notation - it is a much better way to compare algorithms in a hardware independent manner. Saying something took x number of seconds is quite dependent upon so many factors, saying something runs in log time gives a much better description of how well it works relative to other algorithms.I was more wondering how good this may stack up to a more researched algorithm.
Re: Factoring
Alright, run it against an algorithm that you use, if you have one, and see which one is faster.
Re: Factoring
I have never implemented a factoring algorithm (at least not in the last ten years, and that's about as far back as my memory goes these daysOriginally Posted by aesguitar
). Why not find some algorithm implementation online somewhere, and run it against yours? I understand your desire to profile the algorithm, but I would point you to point stdunbar's post, which nicely sums up my thoughts on the subject.
Reply With Quote