Archived

This topic is now archived and is closed to further replies.

sofsenint

simplifying radicals

Recommended Posts

I have been writing a program for my TI-83 that simplifies radicals. For example, if you enter 512, it tells you that that is 16 * radical(2). I simply take the square root of the number entered and start at the largest integer not more than that square root, and decrease the number by one in each iteration. For each number, I square it, and if the square divides evenly into the original number (ex. 512), you factor that number out, and you are done. However, this is very slow when you start working with large numbers. Does anyone know of an algorithm or equation that is more efficient? Thanks! ----------------------------- 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.

Share this post


Link to post
Share on other sites
This is not homework. I''m trying to make a program on my calculator to do this so I can compare the speed of an algorithm that evaluates, say, the square root of 162 compared to one that evaluates nine times the square root of two. I''m trying a few different approaches to a fast square root- I know that this has been done millions of times before, but I get a lot of satisfaction from figuring these things out myself.

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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I''ve got an idea. Say you have a "large" number like 5,012. First bitshift all the way to the right to isolate digit 5. Now, since this is base 10, you know that 5,000 equals 5 * 10 * 10 * 10. And you know you had to bitshift 3 times (ie 10 ^<b>3</b> by previously taking the length of the integer. So on the outside of the radical you already have 10*radical(10*5). Well, is that a start?

-leinad (my acct has been banned for some reason)

Share this post


Link to post
Share on other sites
That''s an interesting idea. One question, though- if I understand you right, you would end up with an answer like 50 radical(2) + 2 radical(3), correct? This is not actually what I was going for (I meant simplest radical form), but I''ll try it out for efficiency anyway!

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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
no, (a + b) ^ .5 != a^.5 + b^.5. I just didn''t finish the algorithm. That would be a problem. It could even be a bad approach.

Share this post


Link to post
Share on other sites
Perhaps it would be better to start at the bottom - since, for example, it''s very likely to have a sqrt(2) in it. You could go from 2 to sqrt of your number, checking if you get a perfect square when you divide your number by it.

Share this post


Link to post
Share on other sites
essentially you want to find any square factors of your input number.i'd do something like this,

// pre-loop
a = input number
b = 1
p = 2
r = 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)
endif
until ( 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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Heres what i thought of off the top of my head (untested). All commands should work for the TI-83



input A

root(A)->B

If fpart(B) = 0
goto Q
Else
Ipart(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))->C
If fpart(C) = 0
goto Q

Loop
disp "Cannot be simplified"
Exit

lbl Q:
disp B
disp "root"
disp C



I think that should work. Tell me how it does

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
sofsenit: yes, you''re right on both counts. this is more like it

// pre-loop
a = input number
b = 1
p = 2
r = 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)
endif
until ( p>r )

now you have the answer: input = b*sqr(a)

i dont think thats very pretty, but hey.

Share this post


Link to post
Share on other sites
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:

// pre-loop
a = input number, r = root(a)
b = 1, c = 1, p = 2

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 divs a, but only once
c = c * p
a = temp1 // a = a/p
r = root(a)
p = nextprime(p)
endif
else
p = nextPrime(p)
endif
until ( p>r )
c = c * a

answer: input = b*sqr(c)

hopefully

Share this post


Link to post
Share on other sites