#### Archived

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

This topic is 5201 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
What is this for?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

##### 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 on other sites
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 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 on other sites
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 on other sites
Oh, of course. I wasn''t thinking that through. So how would your algorithm work?

##### Share on other sites
I don''t know it was a guess.

##### 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 on other sites
BTW, you''re not really simplifying radicals in general - you''re only doing square roots. Perhaps there is a way to optimize it for square roots...

##### Share on other sites
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).

##### Share on other sites
essentially you want to find any square factors of your input number.i'd do something like this,
// 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

Obviously the better that nextPrime is the more numbers you skip, so get it working, then re-write nextPrime.

hope it helps,
fatray

[edited by - fatray on October 28, 2003 8:26:31 AM]

##### 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 on other sites
Heres what i thought of off the top of my head (untested). All commands should work for the TI-83

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

##### 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 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 on other sites
sofsenit: yes, you''re right on both counts. this is more like it
// 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.

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