File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes factors: i hate math Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "factors: i hate math" Watch "factors: i hate math" New topic
Author

factors: i hate math

Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

this is messed up. someone told me the factors of i dont exceed Math.sqrl(i)
that is wrong the factors can go up to i/2
now i have a problem
here is the code



this works but when i use the real number(600851475143), it hangs up






SCJP
Visit my download page
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2771
    
  10

What is i/2lem? I think you misunderstood the advice. The factors of a number can surely exceed the square root of the number. Take 24 for example. 12 is a factor, and is bigger than the square root of 24. However, let's say you have a number n that can be factored into j * k, where j <= k. Then j <= sqrt(n). So, if you're trying to find the prime factors of n, you can iterate through prime numbers up to sqrt(n). If you find a prime factor, divide n by that number and keep going.

I love the Euler problems. They really get you thinking.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

maybe i need to post more code
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

And it probably isn't hanging, you just haven't given it enough time to do all the calculations.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

that was a typo sorry. i dont understand why the program works when given 100 but hangs up when given that long number

if enough time is over 5 minutes you are right

man: this sucks i am sorry the code should have been i/2 or something.the forum didnt list when i said that
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2771
    
  10

You could print out i if you really think it's hanging. I think you'd see that i would keep going up, but you've given it a lot of i's to run through.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

no it is not. when i use 1oo, the output is perfect
when i use that big number i i get a very short list of factors. the smallest is 71
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

Randall Twede wrote:i dont understand why the program works when given 100 but hangs up when given that long number

if enough time is over 5 minutes you are right


I would guess it's more like months, or perhaps geological eons. But stick some debugging code in there which shows you where it's up to with its dividing to get a better feel for that.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

thats what i di by replacing 600851475143L with 100. it didnt work, but using 100 it did

i think it is a syntax type problem
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:this is messed up. someone told me the factors of i dont exceed Math.sqrl(i)


That's not what I said.

I said when finding the factors--such as testing for primeness--you don't need to go beyond sqrt(i). And that statement was correct.



Once you hit 6, you don't need to look any further, because everything beyond that has already been found as the matching factor of the one you're testing.
Greg Charles
Sheriff

Joined: Oct 01, 2001
Posts: 2771
    
  10

Also, what is prime.isPriime() doing? It might be running through a loop just like this one, which makes the workload that much more enormous. I'd forget that part. Unless you have a list of primes to check against, just see if your i is a factor of n. If you keep dividing n by i as you find factors, then all the factors you find will be prime, even if try out many non-prime i candidates. Whatever n ends up as when n / i < i is your answer.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

Yes, the smallest divisor of a number (other than 1 of course) must always be a prime.

(Proof left as an exercise for students who don't hate math.)
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2



i just dont get it...why does it work fine with 100, bot not with 600851475143L is it because of the L?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18127
    
    8

It probably does work fine with the big number. You just have to wait for it to finish.

However you seem to have implemented one of the slowest possible ways of finding the answer, so you might have to wait quite a long time.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:
i just dont get it...why does it work fine with 100, bot not with 600851475143L is it because of the L?
[/code]


No, it's not because of the L. All that does is tell the compiler "Treat this value as a long instead of an int."

It appears to be what people have been telling you all along: It's taking longer than you're waiting.

Your solve() method is O(n^2).

So 200 will take 4 times as long as 100.
300 will take 9 times as long as 100.
1,000 will take 100 times as long as 100.
And, since is 600851475143L is about 6008514751 times as big as 100, it will take 6008514751^2 = 36,102,249,512,984,592,001 times as long as 100.

So if 100 takes 1 ns, you should expect 600851475143L to take about 1144 years.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

so....any suggestions?
even O(log n) sounds better
i know this can be solved because many people have done it before
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4637
    
    5

O(n^2) algorithms always become impossible for big N. The answer is "don't do that"

Find a better algorithm.

Factoring numbers is a well explored field, the crypto folks do it all the time. Google for a better approach. The naive ones always start as O(n^2) and some are O(n^4)

That something works for 10 and is OK for 100 and dies for a big number menas you are doing it wrong.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:so....any suggestions?


1) When looking for factors, use i * i < target as your loop condition, rather than i < target / 2. This will make your outer loop O(sqrt(n)) instead of O(n), making your overall performance O(n^1.5).

2) Make sure your isPrime() method isn't itself O(n^2).

3) As suggested, print out progress marks and timestamps. For instance, every 1,000,000, or every time you reach the next biggest factor of 10. This way you can get a feel for how it's progressing.

4) Search the web for other implementations and compare their approaches to yours.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

well at least i was only n^2
you are all probably right if i google enough i will probably find something.
i was worried the program was "hung up"
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

use i < target

that is kind of funny because that is where i started
i need to think about what you said though
thanks
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

my original code said while <= Math.sqrt(i)

this worked quickly but gave wrong answer
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

stuck in a love/hate relationship
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:
use i < target

that is kind of funny because that is where i started
i need to think about what you said though
thanks


That's not what I said.

I said use i * i < target . This is equivalent to i < Math.sqrt(target) but lets you stick with integer math.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

i haven't tried it yet, but i have a gut feeling you gave me the answer
it still looks wrong to me though.we are back to sqrt(i) instead of i/2
but i try it. you sound like you have already done it

either that or i just say to hell with it
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4637
    
    5

Jeff Verdegan wrote:lets you stick with integer math.

At least until the numbers get big and integers overflow.

With disk drives so big and cheap, you could calculate the factors of all of the integers and just store them. So with some setup, you have an O(1) solution
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:i haven't tried it yet, but i have a gut feeling you gave me the answer
it still looks wrong to me though.we are back to sqrt(i) instead of i/2


Maybe I'm not understanding your problem correctly, but if you're looking for the factors of i, they will all be covered by the time you get to sqrt(i). Are you still doubting that? If so, I don't know how else to explain it to you. Did you see my "diagram" several posts ago?
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Pat Farrell wrote:
Jeff Verdegan wrote:lets you stick with integer math.

At least until the numbers get big and integers overflow.


That's when I would switch to BigInteger. Since we're doing integer math, I prefer to stick to integers, mostly as a matter of principle, but also because I don't want to take the chance of FP error messing up my calculations. I don't know if it would come into play in this situation, but since double cannot represent every long value, I don't want to take the chance.
Pat Farrell
Rancher

Joined: Aug 11, 2007
Posts: 4637
    
    5

Floating point has no value in any factoring code. You have to use integer, bigint, etc.
for 99% of what we programmers write, Floating Point is evil.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Pat Farrell wrote:Floating point has no value in any factoring code. You have to use integer, bigint, etc.
for 99% of what we programmers write, Floating Point is evil.


Sorry I mis-read your previous post. For some reason I thought you were suggesting using x < sqrt(i) instead of x * x < i. Didn't realize you were talking about something completely different. I don't know where my head was.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 13875
    
  10

Randall Twede wrote:so....any suggestions?
even O(log n) sounds better
i know this can be solved because many people have done it before

Yes, it can be done. My solution (in Scala) just takes a fraction of a second to solve this. But the fun in these problems is thinking about it and finding a solution yourself, so I'm not sure how much I should give away.

With regard to this problem, it's good to keep the fundamental theorem of arithmetic in mind: any integer greater than 1 can be written as a unique product of primes ("unique" means: each number can be factored in exactly one way into prime factors, and no other number has the same set of prime factors).

Consider a composite (non-prime) number N that has just two prime factors p1 and p2, so that N = p1 * p2. It's easy to see that either p1 or p2 (or both) must be smaller than sqrt(N). Think of squares and rectangles: you can have a square, for example N = 25 = 5 * 5. In that case both p1 and p2 are sqrt(25) = 5. You can also have a rectangle, for example N = 21 = 3 * 7. In such a rectangular number you have a short and a long side and the short side is always < sqrt(N).

If you think about composite numbers with 3 prime factors, for example N = p1 * p2 * p3 etc., you can extend the idea of the square to a cube. At least one of the primes must be < N^(1/3) (the cube root of N). The cube root is always smaller than the square root. So for any composite number (with any number of prime factors) the square root is always a safe limit.

So to find a prime factor you only need to check up to sqrt(N). If you don't find a prime factor, then you know that N is a prime itself.

Note that checking up to the square root instead of the number itself makes a huge difference. Checking all numbers from 2 to 600,851,475,143 takes a very long time. But the sqrt of 600,851,475,143 is only about 775,146, a much smaller number.

Now, suppose that you've found a prime factor p1 of N, so you know N = p1 * N'. To find another prime factor, you can just divide N by p1: N' = N / p1 and find a prime factor of N'. And so on, until you end up with a number that is itself prime: N = p1 * N' = p1 * p2 * N'' = p1 * p2 * p3 * N''' ... That way you can find all the prime factors of N in a fairly efficient way: each time you find a prime factor, you can divide it out, and all you have to do to find the next one is factor a smaller number.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

i am still having trouble seeing it. but i am doing no good with my current approach. 7 is a prime factor of 14. how do you find that if you only go to sqrt 14?
here is my latest effort. it is slightly better(because the first prime factor it finds is the answer) but still takes too long.
i will try to figure this out thanks to you all. especially Jesper who must think he is talking to a stump
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:i am still having trouble seeing it. but i am doing no good with my current approach. 7 is a prime factor of 14. how do you find that if you only go to sqrt 14?


Because you'll hit 2 before you get to sqrt(14), and when you hit 2, you'll find that 14 / 2 = 7. Now we've got factors 2 and 7.

This is the same thing I said in my first reply here, where I used the factors of 36 as an example.
me wrote:


Once you hit 6, you don't need to look any further, because everything beyond that has already been found as the matching factor of the one you're testing.




Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4339
    
    2

i think i get it now. the remainer is the last factor and also the answer. if there is a factor bigger than sqrt(i) it will be the remainder
i should probably try something like this
getFactor(bigAssNumber)
if there is a factor
getFactor(bigAssNumber/theLastFactor)
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

Randall Twede wrote:i think i get it now. the remainer is the last factor and also the answer. if there is a factor bigger than sqrt(i) it will be the remainder


Eh? Remainder?

If A*B = C, then C/A = B and C/B = A, and since A and B are factors of C, there's no remainder in either case. By definition

Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 13875
    
  10

Randall Twede wrote:i should probably try something like this
getFactor(bigAssNumber)
if there is a factor
getFactor(bigAssNumber/theLastFactor)

Yes, that's correct!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: factors: i hate math
 
Similar Threads
Problem with Loops: What have I been doing wrong?
prime numbers
Prime Factor Program
Finding the largest Prime Factor
Display the prime factors of a number using sets