# Thread: Big numbers and speed

1. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Oct 2012
Posts
176
Rep Power
6

## 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

3. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Oct 2012
Posts
176
Rep Power
6

## Re: Big numbers and speed

Originally Posted by AlexGraal
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?

5. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

## 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. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,174
Rep Power
12

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

7. Señor Member
Join Date
Jan 2014
Posts
184
Rep Power
0

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

#### Posting Permissions

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