# Square root algorithm?

• (2 Pages)
• 1
• 2

## 15 Replies - 12748 Views - Last Post: 31 July 2009 - 08:59 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=117899&amp;s=fd613266871b1de9eed5c551b4c88830&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 lhena_sg1720

Reputation: 0
• Posts: 1
• Joined: 31-July 09

# Square root algorithm?

Posted 31 July 2009 - 06:38 PM

how to get the square root of a number... without the calcu... and implement
on java with just ten lines..

haha!!!

impossible i guess.

blame my crazy prof!!!

Is This A Good Question/Topic? 0

## Replies To: Square root algorithm?

### #2 Locke

• Sarcasm Extraordinaire!

Reputation: 526
• Posts: 5,604
• Joined: 20-March 08

## Re: Square root algorithm?

Posted 31 July 2009 - 06:38 PM

If I knew the algorithm off the top of my head, I'd probably code it myself. Unfortunately, I don't know the method. You could use Newton's method, for instance, and there are many other ways...but...

[rules][/rules]

This post has been edited by Locke: 31 July 2009 - 08:04 PM

### #3 syfran

• D.I.C Lover

Reputation: 83
• Posts: 1,103
• Joined: 12-July 09

## Re: Square root algorithm?

Posted 31 July 2009 - 07:05 PM

How exact? Will it be an whole number?

Locke - I don't really beleive this is in violation of the rules as it is more of a theoretical and an is this even possible question. You can't create code when you don't know what you are trying to create.

This post has been edited by syfran: 31 July 2009 - 07:07 PM

### #4 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Square root algorithm?

Posted 31 July 2009 - 07:14 PM

syfran, on 1 Aug, 2009 - 02:05 AM, said:

How exact? Will it be an whole number?

Locke - I don't really beleive this is in violation of the rules as it is more of a theoretical and an is this even possible question. You can't create code when you don't know what you are trying to create.

Trust Locke on this one.. Anyways, of course it should be a whole number.. What would anyone want half a number for?

The algorithm is similar to Newtons algorithm (or more like binarysearch), you start from the input value / 2 and go from there.
But then it's possible that the teacher expects the students to use the Math class, who knows?!

You can't decide an exact solution since sometimes there is none. You have to interrupt the algorithm once you're close enough.

This post has been edited by Gloin: 31 July 2009 - 07:18 PM

Reputation:

## Re: Square root algorithm?

Posted 31 July 2009 - 07:31 PM

Usually I'd tell you to do your own homework, but this is an interesting program to write.

I used an elementary school algorithm for this. It's actually a very simple program. Try to do this yourself first.

```double num = 29, precision = 0.00001, guess = num/2, change = num/4;
while ((guess*guess - num > precision) || (num - guess*guess > precision)) {
guess += (guess * guess > num) ? -change : change;
change /= 2;
}
System.out.println(guess);

```

Edit: By the way, change the precision variable for better approximation.

This post has been edited by Neumann: 31 July 2009 - 07:35 PM

### #6 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Square root algorithm?

Posted 31 July 2009 - 07:47 PM

Hmmz.. I tried that algorithm but it gets stuck in an endless loop..

Reputation:

## Re: Square root algorithm?

Posted 31 July 2009 - 07:57 PM

What number did you input? I hope it wasn't negative

### #8 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Square root algorithm?

Posted 31 July 2009 - 07:58 PM

Reputation:

## Re: Square root algorithm?

Posted 31 July 2009 - 08:01 PM

Alright, cool

It works for the first 1 million integers, so my guess is that it's correct.

Reputation:

## Re: Square root algorithm?

Posted 31 July 2009 - 08:06 PM

Just to avoid the negative number confusion, here's the function that does the checking.

```public static double root(int num) {
if (num < 0)
throw new IllegalArgumentException("Negative integers don't have (real) square roots");
double precision = 0.00000001, guess = num/2., change = num/4.;
while ((guess*guess - num > precision) || (num - guess*guess > precision)) {
guess += (guess * guess > num) ? -change : change;
change /= 2;
}
return guess;
}

```

First 100 approximations.
```public static void main(String[] args) {
for (int i = 0; i < 100; i++)
System.out.println(root(i)*root(i));
}

```

This post has been edited by Neumann: 31 July 2009 - 08:32 PM

### #11 BetaWar

• #include "soul.h"

Reputation: 1309
• Posts: 7,682
• Joined: 07-September 06

## Re: Square root algorithm?

Posted 31 July 2009 - 08:14 PM

This is a pretty simple problem, I think I posted this a while ago in C++, but here is a quick conversion to Java:

```	public static double nroot(double number, int root){
int endMult = (number < 0)?-1:1;
number *= (number < 0)?-1:1;
double low = 0, high = (number/2)+1, mid = (low+high)/2;
for(;(low < high) && ((Math.pow(mid, root)-number)>0.0001 || (Math.pow(mid, root)-number)<-0.0001); mid = (low+high)/2){
if(Math.pow(mid, root) < number)
low = mid;
else if(Math.pow(mid, root) > number)
high = mid;
else
return endMult*mid;
}
return endMult*(low+high)/2;
}
```

It is 14 lines long and is not limited to square roots (instead it will attempt to find the nth root of any number you enter. I have taken out the error checking and some of the readability I had, but that was mostly just extra lines of code.

It really isn't that difficult, just use a binary search until you are within a certain threshold.

Hope that helps.

### #12 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Square root algorithm?

Posted 31 July 2009 - 08:19 PM

Using recursion and with String as return type, you could easily have returned the roots of negative as well as positive numbers.

```public static String root(int num) {
if (num < 0)
return root(-num) + "i";
double precision = 0.00000001, guess = num/2., change = num/4.;
while ((guess*guess - num > precision) || (num - guess*guess > precision)) {
guess += (guess * guess > num) ? -change : change;
change /= 2;
}
return ""+ guess;
}

```

Reputation:

## Re: Square root algorithm?

Posted 31 July 2009 - 08:31 PM

I'd rather not use complex numbers where they're not needed and I doubt his professor requested them either. But good suggestion!

### #14 Locke

• Sarcasm Extraordinaire!

Reputation: 526
• Posts: 5,604
• Joined: 20-March 08

## Re: Square root algorithm?

Posted 31 July 2009 - 08:45 PM

Indeed.

### #15 Atspulgs

• D.I.C Regular

Reputation: 83
• Posts: 462
• Joined: 29-July 09

## Re: Square root algorithm?

Posted 31 July 2009 - 08:56 PM

I was in understanding that you cant get a root out of a negative number, you can from the modulus of the number - yes.

Correct me if im wrong.