simplifying radicals
This page makes me thing this problem basically reduces to factorization, which means it will be one of those "hard" problems (i.e. non-polynomial).
essentially you want to find any square factors of your input number.i'd do something like this,
Your nextprime function doesn't need to be brilliant, it can be as simple as
if (n is even) add one, else add two.
Obviously the better that nextPrime is the more numbers you skip, so get it working, then re-write nextPrime.
google primorial, "wheel factorization"
hope it helps,
fatray
[edited by - fatray on October 28, 2003 8:26:31 AM]
// pre-loopa = input numberb = 1 p = 2r = root(a)repeat temp1 = floor(a/p) if ( temp1*p==a ) then temp2 = floor(temp1/p) if ( temp2*p==temp1 ) then a = temp1 b = b * p r = root(a) endif else p = nextPrime(p) endifuntil ( p>r )now you have the answer:input = b*sqr(a) Your nextprime function doesn't need to be brilliant, it can be as simple as
if (n is even) add one, else add two.
Obviously the better that nextPrime is the more numbers you skip, so get it working, then re-write nextPrime.
google primorial, "wheel factorization"
hope it helps,
fatray
[edited by - fatray on October 28, 2003 8:26:31 AM]
Author
The reason I didn''t start at the bottom was that, if you did, you need to find multiple factors. For example, factoring 200, you would factor out four, then 25. If you started at the top, though, as soon as you get to 100 and find it to be a factor, you know you''re done.
-----------------------------
Weeks of programming can save you hours of planning.
There are 10 kinds of people in this world-- those who understand binary and those who don''t.
-----------------------------
Weeks of programming can save you hours of planning.
There are 10 kinds of people in this world-- those who understand binary and those who don''t.
Heres what i thought of off the top of my head (untested). All commands should work for the TI-83
I think that should work. Tell me how it does
input Aroot(A)->BIf fpart(B) = 0 goto QElseIpart(B)->B (not sure if thats the name of the function) (Its the one that takes the non-decimal part)While B > 1(B - 1)->B(A / (B^2))->CIf fpart(C) = 0 goto QLoopdisp "Cannot be simplified"Exitlbl Q:disp Bdisp "root"disp C I think that should work. Tell me how it does
Author
boxdot3- Ya, that code works. That's pretty much what I had originally, but now I'm trying to optimize it.
FatRay- I think there's a couple of things wrong with that. First, doesn't a = temp1 need to be a = temp1/P? Second, if the second if statement doesn't test true, won't the program go into an infinite loop?
[edited by - sofsenint on October 22, 2003 10:26:34 PM]
FatRay- I think there's a couple of things wrong with that. First, doesn't a = temp1 need to be a = temp1/P? Second, if the second if statement doesn't test true, won't the program go into an infinite loop?
[edited by - sofsenint on October 22, 2003 10:26:34 PM]
quote:Original post by sofsenint
boxdot3- Ya, that code works. That''s pretty much what I had originally, but now I''m trying to optimize it.
Heh, cool. Yea it''s not optimized at all really. I guess thats what you get when you code in your head
sofsenit: yes, you''re right on both counts. this is more like it
i dont think thats very pretty, but hey.
// pre-loopa = input numberb = 1 p = 2r = root(a)repeat temp1 = floor(a/p) if ( temp1*p==a ) then // if(p divides a) temp2 = floor(temp1/p) if ( temp2*p==temp1 ) then // if(p divides (a/p) ) a = temp2 // a=a/(p^2) b = b * p r = root(a) else p = nextprime(p) endif else p = nextPrime(p) endifuntil ( p>r )now you have the answer: input = b*sqr(a) i dont think thats very pretty, but hey.
just a thought, but you can change what i posted before so that every factor found is moved out of the number you are cracking, maybe something like this:
hopefully
// pre-loopa = input number, r = root(a)b = 1, c = 1, p = 2repeat temp1 = floor(a/p) if ( temp1*p==a ) then // if(p divides a) temp2 = floor(temp1/p) if ( temp2*p==temp1 ) then // if(p divides (a/p) ) a = temp2 // a=a/(p^2) b = b * p r = root(a) else // p divs a, but only once c = c * p a = temp1 // a = a/p r = root(a) p = nextprime(p) endif else p = nextPrime(p) endifuntil ( p>r )c = c * aanswer: input = b*sqr(c) hopefully
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
