0

lol, will check out my local bookstore and amazon. the book i use was required by the professor.

If that's the case, then for the duration of your course, you might as well stick with the style of the book; just be aware of the fact that it's deprecated. It's not like it's a big deal; you should be worried about problem solving and algorithm creation rather than specific details of your language.

-2
#include<stdio.h>
#include<conio.h>
void main()
{
int n,i,mod=0;
clrscr();
printf("\n enter number=");
scanf("%d",&n);
for(i=1;i<n-1;i++)
{
mod=n%i;
if(mod==0)
{
if((i*i)==n)
{
printf("\n square root=%d",i);
}
}
}
getch();
}

meghs

but one limitation in this code is this only find out the integer square root of the given number

thanks

Edited by happygeek: fixed formatting

Votes + Comments
lol yeah
Ran out of people to give +rep to, so you earn a cookie for bumping a long dead thread with untagged "void main" rubbish
0

but one limitation in this code is this only find out the integer square root of the given number

and that it's also broken code that won't compile, and doesn't even work worth a damn if you take the time to fix it.

good job on that. totally worth resurrecting a thread that's been dead for 2 years.

0

Well, the therad is burnt now.
The solution has been pointed by s.o.s ( sorry I am not putting those tildes).
Tylor Theorm will come handy to you for all this 'magical' function.
you could even calculate sin,cos,tan, etc etc.
But this is not the correct way to learn programming. You would be learning 'implementation of mathematical theorems in a computer program".!!

-2

Actually there is a way to do it in C++ and its not hard!

Votes + Comments
And you ressurected the thread to let us know? In future it's maybe wise to also add your not-so-difficult-way to your post, then the ressurect wouldn't be useless.
0

I am not saying its faster than sqrt, but it calculates it without using sqrt.

sqrt(a) = x

x^2 = a

ln(x^2) = ln(a);

2ln(x) = ln(a)

ln(x) = ln(a) / 2

x = e ^ (ln(a)/2)  //same as sqrt(a);

//you can decompose it back to sqrt like so
x = (e^ln(a))^1/2
x = a ^ (1/2) = sqrt(a);
0

With the OP's permission, I would like to make some closing remarks to this hot thread.

1. There appeared to be 4 possible solutions to this square root problem, where pow() and sqrt() functions are not allowed to be used. Solutions which can not handle numbers with decimals, or only integers are excluded.

opt.1 tformed's exp() algorithm
opt.2 Sturm's looping algorithm
opt.3 Salem's suggested common log algorithm
opt.4 firstPerson's natural log algorithm

2. But, since the Power function pow() is not allowed, opt.1, 3, 4 are disqualified for using pow(). The exponential power function pow() in opt.1 was disguised as exp(arg) which is e (2.7182818283) raised to the argth power, and is thus identical with opt.4 and is hereby also disqualified.

3. This leave only opt.2. But the original codes could only handle max. value of 2500. Anything greater entered will return 50. Is this acceptable?

So, there is some truth in Narue's joke. None of the solutions can match C++'s sqrt() function.

I have modified Sturm's codes to handle upto 1 trillion. Greater value, say 10 trillion would produce wrong answers. The way I upgrade the codes to handle 10 trillion (may not be the best way) would slow down the processing speed tremendously, 14 seconds compared to less than 1 second when C++'s Power function pow() or exp() are illegally used in the codes in opt. 1,3 and 4. So, the only code snippet which fulfilled the requirement of the question is still not good enough.

That means what Salem said was correct. Why reinvent the wheel? Some genius had only done that for us.

Salem said the same thing to me in my first ever posting of my codes in a C++ forum, which happened to be daniweb.com. Why roll my own input codes to monitor keyboard input character by character, when C++ already has its time-tested input functions which can read one whole line, followed by the enter key?

I have already explained the reason, which is to preempt error for every character entered before you press the <Enter> button. As I am totally new to C++, i have asked this question, whether there is such a function in C++, but I have not received any answer so far. So I had to roll my own codes.

The codes are used in this square-root computation program.

I have read in the internet that a C veteran programmer had lamented that C++ was the least productive language he had the displeasure to know. This may be true if a programmer has to roll his own codes for something so basic as a data entry routine, where much time and effort had to be put in. However, we can overcome this problem if we learn to share our codes effectively.

Like here in this thread, I am reusing the codes I have written in my first posting, and if someone find it useful he or she may use it, and in the process being more productive than I. That person just need to spend a few minutes to copy and paste the functions to enable control of data type in keyboard entry in his/her own program, with some minor modifications.

Of course, I look forward to constructive criticism and feedbacks as I have just started to learn C++, and written a prototype, which I hope would be useful to somebody in this forum.

regards,

// InputCtrl & sqrt          YBM
#include <windows.h> // WinApi header
#include <iostream>
#include <string>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <stdio.h>

#define maxloop 5
using namespace std;

string spaz(int&,int,string);
string datainp(string,int);
int escx=0;
int curs=0;
int extended=0;
string concate = "";
double weight;
double x;
char *endptr;
string sweight;
void gotoxy( short x, short y ) {
  HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
  COORD position = { x, y };
  SetConsoleCursorPosition( hStdout, position );
}
double sturmsqrt(double num)       //
{
    double mod=1;
    double c=0;

    for(int d=0; d<1000000; c+=mod, d++)
    if(c*c>num)
    {
        c-=mod;
        mod/=10;
    }
    return c;
}
int xcz=0;
int decf=0;
int ctr =0;
int cc=0;
int brk=0;
int len=0;
std::string xcon;
char inpg,xconcate;
int getch(void);
int getche(void);
int xc[maxloop]={5,5,8,5,5};      // xy coordinate   starting from zero
int yc[maxloop]={11,13,11,17,19};
int lgth[maxloop];
int condi=3;
char efld[maxloop][25] = {" "," ","Number : "," "," "};
double e=2.7182818283;
int main() {
    double num;
    num=0;
    double heyyou,whome;
    brk=0;
    system ("color 0a");
    do {
      system ("CLS");
      cout << "\n\n\n\tEsc:Exit   FINDING THE SQUAREROOT OF A NUMBER";
      cout << "\n\tOnly numbers and 1 dec. allowed, (codes may not be bug-free) ";
      cout << "\n\tNumbers upto 1 trillion seem okay for opt.2 ";
      cout << "\n\tNumbers above 1 trillion seem okay for opt.1, 3 and 4";
      cout << "\n\tUse at your own risk.                              ";

      sweight=datainp(efld[condi],condi);
      len=sweight.length();
      concate="";
      if (brk==1) {break;}
      num=weight;
      if (num >0)
      {
      whome=num;
      heyyou= exp((1.0/2.0)*log(whome));
      // double exp(double arg); is the same as e (2.7182818283) raised to the argth power, identical with opt.4.

      cout << "\n\n\t0. (C++ sqrt()                                    Ans.: "<< sqrt(num);
      cout << "\n\n\t1. (tformed)'s exp()sqrt algorithm.               Ans.: "<< heyyou;
      cout << "\n\n\t2. (Sturm)'s Sturmsqrt algorithm.                 Ans.: "<< sturmsqrt(num);
      x = pow(10,log10(num)/2);
      cout << "\n\n\t3. (Salem) Common log - pow(10,log10(num)/2).     Ans.: " << x;
      x = pow(e,log(num)/2);
      cout << "\n\t4. (firstPerson) Natural log - pow(e,log(num)/2). Ans.: " << x;
      }
      else {cout <<"\x7";}
      cout << "\n\n\t<Press Any to cont.> ";
      getch();
    } while ( brk==0);
    cout << "\n\n\tBye. Thanks for trying out Homemade SQRT\n";
    cout << "\n\tand Homemade InputCtrl (Feedback, pls.still under construction>\n\n";
}
//   Data Entry subroutine by YBM
string datainp(string efield,int condi) {
int c;
redo:
extended=0;
curs=0;
decf=0;
//std::string concate = "";
gotoxy(xc[condi-1],yc[condi-1]);
cout << efld[condi-1];
// gotoxy(xc[condi-1]+lgth[condi-1],yc[condi-1]);
  do
  {
    c = getch();
    if (c==27) { brk=1;break; }
    char inp=c;       // assign char from ASCII code Backspace's ASCII code is 8
    inpg==inp;
    extended==0;
//  cout << "ASCII code of " << inpg << "=" << c;
    if (c == 0x00 || c == 0XE0 || c==224 || c==0) {
      extended = getch();
//    cout << "  EXTENDED: " << extended << "XXX";
      cout << "\x7";
      if (extended) {
      c= extended;
      inp=(char)NULL;
      inpg==inp;
     }
    }
    if (condi==3) {  // Only Numbers and decimal ASCII 46 allowed
         if (extended==0 &&  (((decf <=1) && ((c >=48 && c <=57) || c==46)) || ((c >=48 && c <=57) || c==46) && (decf==0) && c !=8)) {
          if ((decf==0) || (decf >=1 && c != 46)) {
             concate += inp; // string concatenation.. The character isn't extended
             cout << inp;
          }
          if (c==46 && decf==0) { ++decf;}
        }
        else { concate=spaz(condi,c,concate);if (curs==1) {}}
      }

  } while (c != 13);        // ascii 13 is <enter> or <carriage return>

  if (c !=27) {
    int len = concate.length();
//    cout << "\n  String length =" << len << " chars" << endl;
    if (condi==3) {
    //  convert string to numeric variable
    char xxc[len];    // intialise array
    concate.copy(xxc,len); // fills in array with characters from the string
//    xxc=concate.c_str();
    weight = strtod(xxc,&endptr);    // weight declared as global double
    }
   }
  return concate;
}  // datainput End
//   SUBROUTINE TO MOVE CURSOR POSITION  Up/Dn/LF/RT/PgUp/PgDn by YBM
string spaz(int& condi,int xcz,string xconcate) {
 if (extended >0) {
    cout << "\x7";
    if (xconcate.length()==0) {
     cout << "\x08";
     cout << " ";}
//   gotoxy(xc[condi]+lgth[condi],yc[condi]);
  if (xcz==72 || xcz==73 || xcz==75 || xcz == 77 || xcz == 80 || xcz==81) {
      cout << "\x7";
      if (xcz==72 || xcz==77 || xcz==73) {
        curs=1;
        if (condi >1) {
         }
       }
      if (xcz==80 || xcz==75 || xcz==81) {
        curs=1;
        if (condi < maxloop) {
        }
       }
       extended=0;
    }
   extended=0;
  }
 else
 {
  if (xcz !=8) {   // not backspace
  }
  else
  {
    len = xconcate.length();
    if (len >0) {
       if (condi==3) {
          if (decf >=1 && xconcate.substr(len-1,1)=="."){
              --decf;
          }
      }
      cout << "\x08";
      cout << " ";
      cout << "\x08";
      xconcate=xconcate.substr(0,len-1);
    }
    else
    {
      cout << "";
      decf=0;
    }
  }
 }
return xconcate;
}   // spaz End
0

"None of the solutions can match C++'s sqrt() function."

Well the solution I provided was derived from sqrt function, thus it
matches the exact output( if thats what you mean by "match").

I wonder if creating your own powerFunction counts as cheating to the
OP, since its not from stl.

Also the solution :

x = e ^ (ln(a)/2)  //same as sqrt(a);

could also be edited so it wont use the power function. Specifically , one can use taylor series of that expression
to create one's own iterative process.

Since :

e^x = SIGMA x^n/n! = 1 + x + x*x/2! + x*x*x/3! + x*x*x*x / 4! .......

one can use this process to determine the sqrt (a), where x = ln(a)/2

And this technically does not use pow or the sqrt function.

Edited by firstPerson: n/a

0

I have just pointed out that answers to the question would be disqualified if pow() was used. Sturm's codes were already posted. I just pointed out some problem with it. I couldn't have initiated any cheating.

0

I noticed this thread and couldn't help wondering why noone used the rather simple algorithm used below.
I program in C++Builder so you may need to adapt the code if you want to use it elsewhere. I have a form with an Edit box for input, a button to start the calculation and three labels to show the output.

Almost any positive number input gives a valid output.

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
double a, b, c, d, e(0.0000000001), count(0);
a = atof(Edit1->Text.c_str());
if(a < 0)
{
   Label1->Caption = "Domain error!";
   return;
}
b = (1.0 + a)/2;
c = (b - a/b)/2;
d = fabs(c);
while(d > e && count < 1000)
{
   b -= c;
   c = (b - a/b)/2;
   d = fabs(c);
   ++count;
}
Label1->Caption = AnsiString(b) + " by algorithm";
Label2->Caption = AnsiString(sqrt(a)) + " by sqrt() function";
Label3->Caption = AnsiString(count) + " itterations";
}
//---------------------------------------------------------------------------

You'll find the number of itterations is quite small and the comparison with sqrt() is very good. You could make e smaller to get a better result.

0

I noticed this thread and couldn't help wondering why noone used the rather simple algorithm used below.
I program in C++Builder so you may need to adapt the code if you want to use it elsewhere. I have a form with an Edit box for input, a button to start the calculation and three labels to show the output.

Almost any positive number input gives a valid output.

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
double a, b, c, d, e(0.0000000001), count(0);
a = atof(Edit1->Text.c_str());
if(a < 0)
{
   Label1->Caption = "Domain error!";
   return;
}
b = (1.0 + a)/2;
c = (b - a/b)/2;
d = fabs(c);
while(d > e && count < 1000)
{
   b -= c;
   c = (b - a/b)/2;
   d = fabs(c);
   ++count;
}
Label1->Caption = AnsiString(b) + " by algorithm";
Label2->Caption = AnsiString(sqrt(a)) + " by sqrt() function";
Label3->Caption = AnsiString(count) + " itterations";
}
//---------------------------------------------------------------------------

You'll find the number of itterations is quite small and the comparison with sqrt() is very good. You could make e smaller to get a better result.

Please correct me if I am wrong.

I would like to hazard a guess. You could be using MS Visual C++. I believe that your codes rely on some other external files, such as Win API, dynamic link library files, etc., and you make use of them to effect GUI, like 3-d buttons, etc. without the need to code them. I know that even simple MS Foxprow executable program can not run without huge foxprow.esl library files, exceeding 1.2 MB.

What I have written was based on the context of a stand-alone C++ program compiled using non-commercial/ non-proprietary C++ compiler, such as CODE::BLOCK, Dev-C++, and Borland C++; and users can use the codes without other overheads, for which they have to pay a price. The executable C++ file can be very small, like 16K. I think users, perhaps including the OP, who use such compilers, -- which I use myself -- can not use your much simplified codes.

I think the freedom of choice of compilers is important. We need not be dependent on a proprietary C++. owned by a ruthless behemoth bent on monopolizing PC based software. We need to be able to breathe freely.

Regards,

0

There is always brute force :

float SquareRootOf(int num)
{
	int i = 0;
	//Check for perfect square root
	for(i = 0; ; i++)
	{
		if(i * i > num) break;
		else if(i * i == num) return float(i);
	}

	i-=2;
	float j = i;
	float precision = 0.00001f;
	while(j * j < num - precision )
		j+=precision;
	
	return j;
}

Edited by firstPerson: n/a

0

ooh, sqrt(4)=4^(1/2)=2
might help :D

where sqrt = Square root
^ = to the power of

oh, hang on...
no to the pwr of...

well if 4x4x4 = 4^3 = 64
and then 4^1/2 = .... urrgh - im screwed.

Edited by maxicube: n/a

0

May I add another algorithm that does not use log and power function; yet still run relatively fast. This function makes use of fast inverse square root algorithm which works only with 32-bits unsigned float number as input.

float sqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    return 1/(x*(1.5f - xhalf*x*x));
}

Or to increase of precision:

float sqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    for(int k=0; k<5; k++)
        x*=(1.5f - xhalf*x*x);
    return 1.0f/x;
}

Edited by invisal: n/a

0

>Please correct me if I am wrong.
You're wrong, and in a most amusing way.

>I think the freedom of choice of compilers is important. We need not
>be dependent on a proprietary C++. owned by a ruthless behemoth
>bent on monopolizing PC based software. We need to be able to breathe freely.

You think freedom of choice is important, but only when those choices conform to your personal biases. Yep, that makes perfect sense. :icon_rolleyes: Unfortunately, this type of religious fanatic non-logic is also quite typical of Microsoft haters.

>What I have written was based on the context of a stand-alone
>C++ program compiled using non-commercial/ non-proprietary
>C++ compiler, such as CODE::BLOCK, Dev-C++, and Borland C++

Borland, huh? :D

0

here is a simple brute force way of doing the nth root of a number.

#include <iostream>
using namespace std;

double NthRoot(double, int);

double RaisedTo(double, int);

double NthRoot(double number, int nthRoot )
{
	bool done = false;
	unsigned short int digits = 0;
	double temp = number / 2;
	double sqrt = 0;
	double plusplus = 1;
	if (number == 1)
		return 1;
	for (;;)
	{
		if (digits > 0)
			plusplus /= 10.0;
		if (digits == 12)
			return sqrt;
		for ( double i = sqrt; i <= (temp + 1); i += plusplus)
		{
			if (RaisedTo(i, nthRoot) > number)
			{
				sqrt = i - plusplus;
				digits++;
				break;
			}
		}
	}
}

double RaisedTo(double base, int power)
{
       double temp;
	for (int i = 1; i < power; i++)
	{
		base *= temp;
	}
	return base;
}

int main()
{
	double number = 0;
	double answer;
	int root;
	cout << "Please enter a number to find the nth root: ";
	cin >> number;
	cout << "Please enter the root you wish to find: ";
	cin >> root;
	answer = NthRoot(number, root);
	cout << "The " << root << "th root is: " << answer << endl;
	cin.get();
	cin.get();
	return 0;
}

i haven't attempted to clock it but does return pretty quick with most numbers. also on line 20 is where you can set the precision you desire. i used 12 for a default

0

<Please correct me if I'm wrong.

A couple of points here. I mentioned in the original post that I was using C++Builder, originally a Borland product, then CodeGear and now Embarcadero. I left the code as I used it thinking that one idea behind these posts was to point people in the right direction rather than give complete solutions to problems. It is easy to convert the pertinant code to any C++ platform.

If you wish I can rewrite the code using an external function, but it is easy enough for you to do that yourself.

There was one problem with my code. It works fine for most numbers but not very small or very large numbers. Try 5e-150 for example. The following modified code works very well for all double precision numbers. The comments in the code explain some other improvements. Also there was no need for the fabs() function as c is always positive.

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
   double a, b, c, d, e(0.0000000001), f, count(0);
   a = atof(Edit1->Text.c_str());
   if(a < 0)
   {
      Label1->Caption = "Domain error!";
      return;
   }
   while(e > a) // For very small values the criterion for stopping needs to be smaller.
      e /= 10;
   b = (1.0 + a)/2;	// First estimate of square root of a.
   c = (b - a/b)/2;  // Correction to give a better estimate.
   while(c > e && count < 1000)
   {
      f = b;	// For very small and very large values we will see
      b -= c;	// if the correction has any effect.
      c = (b - a/b)/2;  // A revised correction.
      if(f == b)  // Applying the correction made no difference to our answer.
         break;
      ++count;		// A counter to measure the effectiveness of our algorithm.
   }
   Label1->Caption = AnsiString(b) + " by algorithm";		// Our answer.
   Label2->Caption = AnsiString(sqrt(a)) + " by sqrt() function";	// The true answer for comparison.
   Label3->Caption = AnsiString(count) + " iterations";	// Tells us how much effort it took.
}
//---------------------------------------------------------------------------

If you are having trouble addapting this code I can rewrite it as a function that can be used on any C++ platform.

Cheers
Foamgum

0

In the spirit of C++ coding I've rewritten this with an external function that could be put into a library. When you were confident that you didn't need to see how many iterations there were you could remove that part of the function.

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
   double a, b;
   int count(0);
   a = atof(Edit1->Text.c_str());
   b = MySQRT(a, &count);
   if(a < 0)
   {
      Label1->Caption = "Domain error!";
      return;
   }
   Label1->Caption = AnsiString(b) + " by algorithm";		// Our answer.
   Label2->Caption = AnsiString(sqrt(a)) + " by sqrt() function";	// The true answer for comparison.
   Label3->Caption = AnsiString(count) + " iterations";	// Tells us how much effort it took.
}
//---------------------------------------------------------------------------
double __fastcall TForm1::MySQRT(double number, int *iterations)
{
   double b, c, e(1e-12), f;
   if(number < 0)
      return -1;
   while(e > number) // For very small values the criterion for stopping needs to be smaller.
      e /= 10;
   b = (1.0 + number)/2; // First estimate of square root of number.
   c = (b - number/b)/2; // Correction to give a better estimate.
   while(c > e && (*iterations) < 1000)
   {
      f = b;   // For very small and very large values we will see
      b -= c;  // if the correction has any effect.
      if(f == b)       // Applying the correction made no difference to our answer.
         return b;
      c = (b - number/b)/2; // A revised correction.
      ++(*iterations); // A counter to measure the effectiveness of our algorithm.
   }
   return b;
}
//---------------------------------------------------------------------------

Regards
Foamgum

1

>Unfortunately, this type of religious fanatic non-logic is also quite typical of Microsoft haters.

Dear Narue,

Your insinuation might be unfair.

Contrary to your misconception, I believe I am a reasonable man.
I can accept that "it is better to let 10 guilty persons go free, than to wrongfully accused a single innocent person." Can you?

My personal conviction on a Company or an individual is, to my best knowledge, not based some religious, fanatical and illogical prejudice, but on solid, indisputable and unequivocal evidence.

There got to be some justification in my conviction basing on the common knowledge that there was a historic DOJ anti-trust lawsuit, billion dollars lawsuits (1.5b) in America, hundred of million lawsuits (613m) in Europe and tens of million (32m) lawsuits in Asia -- across 3 continents -- and eventual unfavorable findings against a particular Company. Besides, I have my personal grievances as well, but, I would refrain from dwelling more on this because it is off-topic. I reply basing on an individual's inalienable right to self-defence.
Shall we leave it as it is?

I would refrain from making judgment on you. But, I would make a guess. You were probably an excellent debater in your schooldays. You could get out from tight corners. And you can write very well.

>Borland, huh?
As I was new to C++, I started with Borland C++, knowing nothing about its unpopularity in this forum. Most of the time, I am using CODE::BLOCK and Dev-C++ now, being introduced indirectly and directly to it, respectively in this forum. But I sometimes use Borland for references because of its useful references and examples. I guess, if a program could run under Borland, most other modern compilers may work with some minor modifications, and I know how to do it, as I have pointed out in some earlier postings, for the benefit of new C++ programmers like me.

I use the compiler which seem to support most codes I see in this forum. I am not biased. I adapt myself to what is needed to learn C++. For the purpose of coding C++ program, I have dropped Borland in favor of CODE::BLOCK and Dev-C++, because I get the impression that very many posters seem to be using the latter. However, if the majority of posters eventually shift towards MS Visual C++, I might have to follow suit despite my personal convictions about freedom from the stranglehold of some domineering behemoth.

As Don Corleon said, it is strictly business, nothing personal.

Coming back to the matter raised in this thread, I am really surprised at the number of recent postings which revealed that there are many intelligent and good C++ proqrammers in this forum, whose interest in solving this squareroot problem might have been inadvertently rekindled. Some solutions appeared to be incredibly simple, and yet might work. I am indeed interested to test them with my limited knowledge in C++.

Votes + Comments
+ rep for not flying into fits of rage and giving a coolheaded reply. And BTW, I think you are spot on with your 'guess'. :-)
0

Round 2 - Final round?
--------------------------

To date, 8 working algorithms for computing square-roots are as follows:

opt.1 (tformed) exp() algorithm
opt.2 (Sturm) looping algorithm
opt.3 (Salem) suggested common log algorithm
opt.4 (firstPerson) natural log algorithm
opt.5 (firstPerson) Taylor's series
opt.6 (firstPerson) Brute force
opt.7 (invisal) Inverse Square Root
opt.8 (Foamgum) Spirit MySQRT

NathanOliver's ambitious nth root of a number algorithm has a bug in line 17, which gave rise to infinite loops. firstPerson's Brute force algorithm is original and simplest and the speed may probably be improved if the first computed estimate of the square root of a number entered can be used in the for loop, instead of starting from 0. Precision may have to be sacrificed to increase speed of computation.

The Sqrt program below is used for comparison of performance of the algorithms. Numbers up to 30, 40, 50 and 60 digits data are entered, and the answers given by various algorithms are used for ranking. e.g. a 30-digit number would look like this, 123456789012345678901234567890.

Slow algorithms are skipped, and are considered out of the race.

This time around, the top two entries can match C++'s square root function to the best of my knowledge. However, I may be wrong. Basing on the results, I would rank -- without any bias -- the algorithms in terms of originality and performance as follows:

Foamgum's Spirit MySQRT algorithm (opt. 8) - First place.
firstPerson's Taylor series algorithm (opt.5) - Second place.
invisal's inverse Square Root algorithm (opt.7) - third place.

Foamgum's algorithm is original and answers for numbers up to 60 digits number are correct.

firstPerson's Taylor's series algorithm's answers for numbers up to 60 digits are correct.

invisal's Inverse Square root algorithm uses a magic hex constant. Its answers for numbers up to 30 digits are correct, and for numbers from 40 digits onwards are not correct. Perhaps invisal can debug the codes, and let us have the debugged version. But, if it can only handle float and not double numeric variable, can greater accuracy be achieved? I am curious to know the answer.

Other algorithms were either too slow, were disqualified or could not work (got bug/s).

Run the program below to confirm the above results yourself.
Please feel free to modify the codes to improve them, and kindly post modified parts for me to update my codes. Thanks.

// sqrt       InputCtrl & sqrt          YBM 22 Sep 2009
#include <windows.h> // WinApi header
#include <iostream>
#include <string>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <stdio.h>
#define maxloop 5
using namespace std;
string spaz(int&,int,string);
string datainp(string,int);
int escx=0;
int curs=0;
int extended=0;
string concate = "";
double weight;
double x;
char *endptr;
string sweight;
void gotoxy( short x, short y ) {
  HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
  COORD position = { x, y };
  SetConsoleCursorPosition( hStdout, position );
}
double sturmsqrt(double num) {
    double mod=1;
    double c=0;
    for(int d=0; d<10000000; c+=mod, d++)
    if(c*c>num) {
        c-=mod;
        mod/=10;
    }
    return c;
}
float invsqrt(float zx) {
    float xhalf = 0.5f*zx;
    int i = *(int*)&zx;
    i = 0x5f3759df - (i>>1);
    zx = *(float*)&i;
    for(int k=0; k<5; k++)
        zx*=(1.5f - xhalf*zx*zx);
    return 1.0f/zx;
}
double taylor(double zx) {            // Taylor series
   double k = 1, lim2 = 168;
   double term;
   double x=log(zx)/2;
   double y;
   double sum = 1;
   int i=1;
   y=1; sum = 1;
   do {
        k *= i++; y *= x; term = 1.0*y/k; sum += term;
   } while (i <= lim2);
   return sum;
}
float SquareRootOf(double num)  {   //  firstPerson's BRUTE FORCE SQRT Check for perfect square root
    int i = 0;
	for(i = 0;i < 10000 ; i++) {
		if(i * i > num) break;
		else if(i * i == num) return double(i);
	}
	i -= 2;
	double j = i;
	float precision = 0.001f;
	while(j * j < num - precision )
		j+=precision;
	return j;
}
double MySQRT(double number, int *iterations) {    //  Foamgum's Spirit MySQRT
   double b, c, e(1e-12), f;
   if(number < 0)
      return -1;
   while(e > number) // For very small values the criterion for stopping needs to be smaller.
     e /= 10;
     b = (1.0 + number)/2; // First estimate of square root of number.
     c = (b - number/b)/2; // Correction to give a better estimate.
     while(c > e && (*iterations) < 1000) {
       f = b;   // For very small and very large values we will see
       b -= c;  // if the correction has any effect.
       if(f == b)       // Applying the correction made no difference to our answer.
         return b;
       c = (b - number/b)/2; // A revised correction.
       ++(*iterations);     // A counter to measure the effectiveness of our algorithm.
     }
     return b;
}
int xcz=0;
int decf=0;
int ctr =0;
int cc=0;
int brk=0;
int len=0;
std::string xcon;
char inpg,xconcate;
int getch(void);
int getche(void);
int xc[maxloop]={5,5,8,5,5};      // xy coordinate   starting from zero
int yc[maxloop]={11,11,7,17,19};
int lgth[maxloop];
int condi=3;
char efld[maxloop][25] = {" "," ","Number : "," "," "};
double e=2.7182818283;
int main() {
    double num;
    num=0;
    double heyyou,whome;
    brk=0;
    system ("color 0a");
    do {
      system ("CLS");
      cout << "\n\tEsc:Exit   FINDING THE SQUAREROOT OF A NUMBER";
      cout << "\n\tOnly numbers and 1 dec. allowed, (codes may not be bug-free) ";
      cout << "\n\tNumbers upto 1 trillion seem okay for opt.2 ";
      cout << "\n\tNumbers above 10 trillion seem okay for opt.1, 3, 4, 5";
      cout << "\n\tUse at your own risk.                              ";
      sweight=datainp(efld[condi],condi);
      len=sweight.length();
      concate="";
      if (brk==1) {break;}
      num=weight;
      if (num >0) {
        whome=num;
        heyyou= exp((1.0/2.0)*log(whome));
        // double exp(double arg); is the same as e (2.7182818283) raised to the argth power, identical with opt.4.
        cout << "\n\t0. (C++ sqrt()                                    Ans.: "<< sqrt(num);
        cout << "\n\t1. (tformed)'s exp()sqrt algorithm.               Ans.: "<< heyyou;
        cout << "\n\t2. (Sturm)'s Sturmsqrt algorithm.                 Ans.: "<< sturmsqrt(num);
        x = pow(10,log10(num)/2);
        cout << "\n\t3. (Salem) Common log - pow(10,log10(num)/2).     Ans.: " << x;
        x = pow(e,log(num)/2);
        cout << "\n\t4. (firstPerson) Natural log - pow(e,log(num)/2). Ans.: " << x;
        x = taylor(num);
        cout << "\n\t5. (firstPerson) Taylor Series                    Ans.: " << x;
        if (num <= 1000000000) {
          float(x) = SquareRootOf(num);
          cout << "\n\t6. (firstPerson) Brute force                      Ans.: " << x;
        }
        else { cout << "\n\t6. (firstPerson) Brute force skip "; }
        float fnum;
        fnum=float(num);
        x = invsqrt(fnum);
        cout << "\n\t7. (invisal) Inv.SquareRoot, hex const.0x5f3759df.Ans.: " << x;
        double a, b;    //  Foamgum
        int count(0);
        a = num;
        b = MySQRT(a, &count);
        cout << "\n\t8. (Foamgum) Spirit MySQRT                        Ans.: " << b;
      }
      else {cout <<"\x7";}
      cout << "\n\n\t<Press Any to cont.> ";
      getch();
    } while ( brk==0);
    cout << "\n\n\tBye. Thanks for trying out Homemade SQRT\n";
    cout << "\n\tand Homemade InputCtrl (Feedback, pls.still under construction>\n\n";
}
//   Data Entry subroutine by YBM
string datainp(string efield,int condi) {
int c;
redo:
extended=0;
curs=0;
decf=0;
//std::string concate = "";
gotoxy(xc[condi-1],yc[condi-1]);
cout << efld[condi-1];
// gotoxy(xc[condi-1]+lgth[condi-1],yc[condi-1]);
  do
  {
    c = getch();
    if (c==27) { brk=1;break; }
    char inp=c;       // assign char from ASCII code Backspace's ASCII code is 8
    inpg==inp;
    extended==0;
//  cout << "ASCII code of " << inpg << "=" << c;
    if (c == 0x00 || c == 0XE0 || c==224 || c==0) {
      extended = getch();
//    cout << "  EXTENDED: " << extended << "XXX";
      cout << "\x7";
      if (extended) {
      c= extended;
      inp=(char)NULL;
      inpg==inp;
     }
    }
    if (condi==3) {  // Only Numbers and decimal ASCII 46 allowed
         if (extended==0 &&  (((decf <=1) && ((c >=48 && c <=57) || c==46)) || ((c >=48 && c <=57) || c==46) && (decf==0) && c !=8)) {
          if ((decf==0) || (decf >=1 && c != 46)) {
             concate += inp; // string concatenation.. The character isn't extended
             cout << inp;
          }
          if (c==46 && decf==0) { ++decf;}
        }
        else { concate=spaz(condi,c,concate);if (curs==1) {}}
      }

  } while (c != 13);        // ascii 13 is <enter> or <carriage return>

  if (c !=27) {
    int len = concate.length();
//    cout << "\n  String length =" << len << " chars" << endl;
    if (condi==3) {
    //  convert string to numeric variable
    char xxc[len];    // intialise array
    concate.copy(xxc,len); // fills in array with characters from the string
//    xxc=concate.c_str();
    weight = strtod(xxc,&endptr);    // weight declared as global double
    }
   }
  return concate;
}  // datainput End
//   SUBROUTINE TO MOVE CURSOR POSITION  Up/Dn/LF/RT/PgUp/PgDn by YBM
string spaz(int& condi,int xcz,string xconcate) {
 if (extended >0) {
    cout << "\x7";
    if (xconcate.length()==0) {
     cout << "\x08";
     cout << " ";}
//   gotoxy(xc[condi]+lgth[condi],yc[condi]);
  if (xcz==72 || xcz==73 || xcz==75 || xcz == 77 || xcz == 80 || xcz==81) {
      cout << "\x7";
      if (xcz==72 || xcz==77 || xcz==73) {
        curs=1;
        if (condi >1) {
         }
       }
      if (xcz==80 || xcz==75 || xcz==81) {
        curs=1;
        if (condi < maxloop) {
        }
       }
       extended=0;
    }
   extended=0;
  }
 else
 {
  if (xcz !=8) {   // not backspace
  }
  else
  {
    len = xconcate.length();
    if (len >0) {
       if (condi==3) {
          if (decf >=1 && xconcate.substr(len-1,1)=="."){
              --decf;
          }
      }
      cout << "\x08";
      cout << " ";
      cout << "\x08";
      xconcate=xconcate.substr(0,len-1);
    }
    else
    {
      cout << "";
      decf=0;
    }
  }
 }
return xconcate;
}   // spaz End
0

>Your insinuation might be unfair.
Says the dude who uses the vendor's history of business practices as justification for attacking a very good tool. Based on facts or not, your reasoning is flawed. Consider the following statement, which is false in exactly the same way:

"That programmer is an asshole, so he must write horrible software."

The flaw is easier to see now, I hope. Clearly being an asshole doesn't have any bearing on one's ability to write excellent software. Microsoft's compiler is one of the better ones out there both in terms of performance and standard compliance.

>>Borland, huh?
>As I was new to C++, I started with Borland C++, knowing nothing about its unpopularity in this forum.

Actually, I was subtly informing you that the code was written using VCL, a GUI API supplied with Borland C++ Builder. Your initial assumption that the code was written with Visual Studio was off by an entire corporation. That's what I found so amusing about your rant. I'm not sure what you mean by unpopularity on this forum though. I haven't noticed any particular bias against Borland, and personally I'm rather partial to their C++ compiler, it's very nice.

0

Dear Narue,

>....attacking a very good tool....
I do not recall attacking any Corporation's compiler. Where is your evidence, else was it a hallucination?

My conviction in favor of freedom of choice of compilers is entrenched in my belief that there should be healthy competition in mass market consumer software, like in this thread for the benefit of consumers. The problem with monopoly is that quality could be compromised if consumers have no choice. The monopoly vendor who produces an inferior product says, "Take it or leave it". and if you leave it, you have nothing. You wouldn't be happy if something inferior is rammed down your throat, right? That was proven by the overwhelmingly widespread use of Windows OS in PCs, exceeding 90% despite the superiority of Apple OS over Windows, which was at least 7 years behind when Windows95 was first launched. Millions of PC users had to live with an relatively inferior product vis-a-vis Apple. However, the perpetuality clause in a settlement agreement in a Apple's lawsuit against Microsoft lawsuit -- which Apple won --enabled Windows to copy Apple perpetually.

>>Borland, huh?
>As I was new to C++, I started with Borland C++, knowing nothing about its unpopularity in this forum.

Thanks for pointing out my wrong assumption. I am a novice learning from all of you.

I got the impression from this forum that Turbo C++, a Borland product was 20 years too late, from postings by Salem and Ancient Dragon, two respectable posters in this forum. Do you mean to say there are improved C++ compiler by Borland which would reject Void main(void)? As I am new, along with many others in this forum, please enlighten us. Please provide the link to the improved Borland, and also to VCL GUI API if it is possible. Thanks.

Regards,

0

Dear firstPerson,

>>I like that comparison, younghc, even though your code is not easy
to follow. Its pretty neat.

Thanks for your kind words.

If there is anything in my codes which need explanation, please do not hesitate to ask. Admittedly, I look forward to be of service to this forum, from which I have been receiving invaluable assistance, which enabled me to jumpstart in learning C++ programming.

Remember...
"Ask and you will receive.
Seek and you will find;
knock and it will be opened to you."
(adapted).

This forum is living proof of the veracity of the above statements, and I am proud of it. Keep it up.

Regards,

0

"if there is anything in my codes which need explanation, please do not hesitate to ask"
I don't mean I can't follow the code, I mean its not cleanly written.

And just when you thought there isn't another way :

#include<iostream>
#include<cmath>
#include<limits>

using namespace std;
 
typedef double data_type ;

data_type Approx(data_type num)
{
	int deg = 10;

	data_type cpy = num;

	while(cpy > 9) { cpy/=10; deg++; };

	data_type i = num / deg;	
	
	while(num < i*i) 		
		i-= unsigned long(1 + log(num));	

	if( i < 1) i = 0;	

	for( ; i <= num; i++)
	{
		//power of 2 ?
		if(i * i == num) 
			return i;
		//return closest int approxment
	  else if( i * i > num)
			return i - 1;
	}	
	
	return i-1;

}
inline data_type Avg(data_type X, data_type Y) {
	return (X+Y)/2.0; 
}
data_type SquareRootOf(data_type Num, unsigned int precision = 30)
{
	//check for default precision = 10;
	precision = precision < 10 ? 10 : precision;

	data_type X = data_type(Approx(Num));

	if(X*X == Num)
		return X;

	data_type average = 0;

	while(precision--)
	{		
		data_type Y = Num/X;
		average = Avg(Y,X);
		
		if(average * average == Num) 
			return average;					
		else X = average;		
	}

	 return average;
}
int main()
{ 							
	
	for(float i = 145; i < 164; i+=0.1)	
	{
		cout.width(10);
		cout<<"(cmath,Mines) square root of : "<<i <<" is = ";
		cout.width(10);
		cout<<sqrt(data_type(i))<<"\t"<<SquareRootOf(data_type(i))<<endl;
	}
	return 0;
}

Edited by firstPerson: n/a

0

Oh wait another option , via Newton. Its a good approx.
It has similar logic as above, but the heat of the program relies on
calculus, which is done on paper.

double Sqrt(double Num)
{
	double i = 2;		
	double Result = 0;
	unsigned int Precision = 10;
	for(int j = 0; j <Precision ; j++)
	{
		Result = i - (i*i - Num) / (2.0*i);		
		i = Result;
	}
	return Result;
}
0

Dear firstPerson,

>> .. Oh wait another option , via Newton. Its a good approx.
It has similar logic as above, but the heat of the program relies on
calculus, which is done on paper.

Your Newton algorithm is okay for small numbers. Above 6 consecutive numbers, accuracy of computation will be increasing less compared with other algorithms.

I suggest you plug your new sqrt function inside my program to see the comparative results. Anyway, nice try.

Regards,

0

Dear firstPerson,

> And just when you thought there isn't another way :

There is a bug in line 20 as reported by CODE::BLOCK and Dev-C++, viz.,
"expected primary-expression before "unsigned"". Borland 5.02 reported "expression syntax error".
Please check.

BTW, what compiler are you using?

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.