Results 1 to 7 of 7
Like Tree1Likes
  • 1 Post By jim829

Thread: Big numbers and speed

  1. #1
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Big numbers and speed

    Java Code:
    class Hmwk1 {
      public static void main ( String[] args ) {
        long counter = 0L;
        long max = 1000000000000L;
        for(long y = 1L; y <= max; y++) {
          for(long x = 1L; x < y; x++) {
            if((x * y) % (x + y) == 0) {
              counter++;
              if(counter % 10000 == 0) {
                System.out.println("Counter: " + counter + ". y = " + y + ".");
              }
            }
          }
        }
        System.out.println("Counter: " + counter);
      }
    }
    This program begins running EXTREMELY slowly once y gets up to around 400000 - I want to know how I could speed this up. y needs to go all the way up to 1000000000000...

    Thanks

    EDIT: I'll clarify, for anyone who isn't clear on what the problem is. I've been running this program for nearly 45 minutes now, and y = 550,000. y will need to go all the way up to 10^12...and since x has to count up all the way to y, the bigger the y value, the more xs need to be generated - the speed is going to get exponentially slower.
    Last edited by AlexGraal; 01-17-2014 at 03:43 AM.

  2. #2
    Daryn is offline Senior Member
    Join Date
    Oct 2012
    Posts
    176
    Rep Power
    3

    Default Re: Big numbers and speed

    you could try using a timer and when ever it ticks add to x until it reaches a certain number then add to the y and then back to the x
    With the right know how, anything is possible

  3. #3
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Big numbers and speed

    Ok maybe this is just my lack of experience with java, but I fail to see how that is going to speed anything up.

    Does a forloop run slower than a timer can tick? I don't really see how that helps me program to run faster...

  4. #4
    Daryn is offline Senior Member
    Join Date
    Oct 2012
    Posts
    176
    Rep Power
    3

    Default Re: Big numbers and speed

    Quote Originally Posted by AlexGraal View Post
    Ok maybe this is just my lack of experience with java, but I fail to see how that is going to speed anything up.

    Does a forloop run slower than a timer can tick? I don't really see how that helps me program to run faster...
    I really don't know. Im just brainstorming. Maybe I can help more if you tell me whats the purpose of this program?
    With the right know how, anything is possible

  5. #5
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Big numbers and speed

    Explaining the purpose fully takes an unnecessary amount of typing for me to explain. Long story short, I need to check that x + y will divide evenly into x*y, where x < y <= max, which for this problem, happens to be 10^12, or 1000000000000. That is the problem. I see no other way to approach this...

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,777
    Rep Power
    5

    Default Re: Big numbers and speed

    You will never see your program run to completion. The inner loop goes 1 time, then 2 times, then 3 times, up to 10^12 times. So it will run n(n+1)/2 times where n is 10^12. So that's about (10^24)/2 or 5 x 10^23. Assuming a trillion iterations per second (to simplify the math cause it ain't gonna happen), that would be .5 trillion seconds or about 15,000 years. I suggest you get a book on algebra and perhaps number theory and start reading. In the meantime, I will think about this. Of course, my above analysis could be off.

    Note: Since an odd number is not divisible by an even number you may be able to speed up your loops by changing the increment. But that alone is not sufficient. You simply need a better algorithm (it's possible the solutions could be derived too). And one more tidbit while I'm thinking of it. A long holds a 63 bit positive number. Multiplying by .30103 (log 2 base 10) you get 18.9 or 19 digits. So your counter will increment into oblivion long before your loops finish.

    Regards,
    Jim
    Last edited by jim829; 01-17-2014 at 10:31 PM.
    AlexGraal likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  7. #7
    AlexGraal is offline Señor Member
    Join Date
    Jan 2014
    Posts
    184
    Rep Power
    0

    Default Re: Big numbers and speed

    Thank you for the great answer. If you think of anything, I'd love to hear about it - preferably just a hint - through a private message! I shall be thinking as well.

Similar Threads

  1. Ftp Transfer speed
    By kuriozal in forum Networking
    Replies: 0
    Last Post: 08-22-2012, 10:10 PM
  2. how to change numbers into word numbers?
    By akeni in forum New To Java
    Replies: 13
    Last Post: 11-18-2011, 08:46 AM
  3. Replies: 11
    Last Post: 01-14-2011, 06:36 PM
  4. printing two smallest numbers from a series of numbers
    By trofyscarz in forum New To Java
    Replies: 2
    Last Post: 10-14-2008, 11:46 PM
  5. compare speed
    By bbq in forum JDBC
    Replies: 1
    Last Post: 06-28-2007, 05:34 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •