Square root algorithm?

duh!!! deadllime on teusday!

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 10037 Views - Last Post: 31 July 2009 - 08:59 PM Rate Topic: -----

#1 lhena_sg1720  Icon User is offline

  • New D.I.C Head

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

Square root algorithm?

Posted 31 July 2009 - 06:38 PM

:ph34r:



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!!! :pirate:

:blink:
:blink:
:blink:

Is This A Good Question/Topic? 0
  • +

Replies To: Square root algorithm?

#2 Locke  Icon User is offline

  • Sarcasm Extraordinaire!
  • member icon

Reputation: 521
  • View blog
  • Posts: 5,596
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 syfran  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 83
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

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

Re: Square root algorithm?

Posted 31 July 2009 - 07:14 PM

View Postsyfran, 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

Was This Post Helpful? 0
  • +
  • -

#5 Guest_Neumann*


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

Was This Post Helpful? 0

#6 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • 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.. :blink:
Was This Post Helpful? 0
  • +
  • -

#7 Guest_Neumann*


Reputation:

Re: Square root algorithm?

Posted 31 July 2009 - 07:57 PM

What number did you input? I hope it wasn't negative :)
Was This Post Helpful? 0

#8 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

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

Re: Square root algorithm?

Posted 31 July 2009 - 07:58 PM

:^:
Was This Post Helpful? 0
  • +
  • -

#9 Guest_Neumann*


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.
Was This Post Helpful? 0

#10 Guest_Neumann*


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

Was This Post Helpful? 0

#11 BetaWar  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1167
  • View blog
  • Posts: 7,213
  • 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.
Was This Post Helpful? 0
  • +
  • -

#12 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • 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;
}


Was This Post Helpful? 0
  • +
  • -

#13 Guest_Neumann*


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!
Was This Post Helpful? 0

#14 Locke  Icon User is offline

  • Sarcasm Extraordinaire!
  • member icon

Reputation: 521
  • View blog
  • Posts: 5,596
  • Joined: 20-March 08

Re: Square root algorithm?

Posted 31 July 2009 - 08:45 PM

Indeed.
Was This Post Helpful? 0
  • +
  • -

#15 Atspulgs  Icon User is offline

  • D.I.C Regular

Reputation: 68
  • View blog
  • Posts: 380
  • 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.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2