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.

Results 1 to 6 of 6

Thread: Factoring

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Lightbulb 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.


  2. #2
    Member
    Join Date
    Apr 2012
    Location
    Superior, CO, USA
    Posts
    80
    Thanks
    0
    Thanked 14 Times in 14 Posts

    Default 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!

  3. The Following User Says Thank You to stdunbar For This Useful Post:

    copeg (June 2nd, 2012)

  4. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default 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.

  5. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,262
    Thanks
    176
    Thanked 820 Times in 763 Posts
    Blog Entries
    5

    Default Re: Factoring

    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.

  6. #5
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Factoring

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

  7. #6
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,262
    Thanks
    176
    Thanked 820 Times in 763 Posts
    Blog Entries
    5

    Default Re: Factoring

    Quote Originally Posted by aesguitar View Post
    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.

Similar Threads

  1. Trying to write Factoring Numbers Code--Please Help.
    By uks2h in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 11th, 2010, 07:20 PM
  2. Need Help - Factoring & Prime Finding Code
    By prodigytoast in forum Algorithms & Recursion
    Replies: 5
    Last Post: November 5th, 2009, 06:38 AM

Tags for this Thread