# Factoring

• June 1st, 2012, 02:04 PM
aesguitar
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?
• June 2nd, 2012, 09:20 PM
stdunbar
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.
• June 2nd, 2012, 11:26 PM
aesguitar
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:

Code java:

```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.
• June 3rd, 2012, 10:01 AM
copeg
Re: Factoring
Quote:

I was more wondering how good this may stack up to a more researched algorithm.
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.
• June 3rd, 2012, 02:44 PM
aesguitar
Re: Factoring
Alright, run it against an algorithm that you use, if you have one, and see which one is faster.
• June 3rd, 2012, 03:29 PM
copeg
Re: Factoring
Quote:

Originally Posted by aesguitar
Alright, run it against an algorithm that you use, if you have one, and see which one is faster.

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 days ;) ). 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.