Square root program without sqrt or pwr

[tformed]

is there any way one could do a square root program without sqrt or pwr functions?

Any tips?

I am not asking for code btw.:)

[Narue]

>is there any way one could do a square root program without sqrt or pwr functions?
No, those functions are magic. There's no way you can simulate their behavior in C++ without pixie dust or phoenix feathers. One might assume that if you know how the mathematics work, you could come up with a sensible facsimile, but in reality, only compiler writers are capable of creating such things...

[Rashakil Fol]

You could use a binary search algorithm. (It would be easy to name better ways, but Meh.)

[Salem]

There seems to be a rash of "do x without using the obvious" problems at the moment.

Are they all at the same school with some dim-wit teacher who thinks that learning dumb tricks is the way to teach programmers.

[tformed]

lol, point me out to these threads if you can, just in case i can point them out lol

anyways, the teacher wants us to write a program without relying on these special functions. I can do them with, but now he wants us to do without.

I do not know of any mathematical formula that will enable me to achieve this without using a square root.
I will ask him, to clarify. Will post back later.

There seems to be a rash of "do x without using the obvious" problems at the moment.

Are they all at the same school with some dim-wit teacher who thinks that learning dumb tricks is the way to teach programmers.

[Narue]

>anyways, the teacher wants us to write a program without relying on these special functions.
Yea, we figured as much. The thing is, there's no point to it if the functions are available. That's why they're there, so you don't have to write them. Anyway, a simple pow is easy to write: Just multiply x with itself y times and you have [TEX]x^y[/TEX]. sqrt is harder, but you can find examples and explanations all over the web. Most likely you don't care about efficiency for a class, so just pick the first one you find that works. Two relatively simple ones are binary search (like Rashakil suggested) and newton iteration.

[Sturm]

heres one (I do not know what it is called. My friend and I were having a competition who could make the fastest sqrt algorithm, so this is mine):

double sqrt(double num)
{
    double mod=1;
    double c=0;

    for(int d=0; d<50; c+=mod, d++)
    if(c*c>num)
    {
        c-=mod;
        mod/=10;
    }
    
    return c;
}

[Salem]

Obviously, my coloured in hint wasn't enough ;)

Compare log(10000) with log(100)
Try it with a few others as well where one is the square root of the other.

[~s.o.s~]

Different methods of finding the square root.

> Try it with a few others as well where one is the square root of the other.
Yes, logarithmic method seems to be a good choice.

[tformed]

I keep on getting the following as an error:

'ln' undefined; assuming extern returning int

do i need to define ln? If so, what value?

[~s.o.s~]

There is no function name 'ln' in standard C++. Its the 'log' function which you need to look into. You also need to refer the Math library for completing your task.

[Narue]

It's log, not ln. And you can find it in <cmath>.

[ndeniche]

>is there any way one could do a square root program without sqrt or pwr functions?
No, those functions are magic. There's no way you can simulate their behavior in C++ without pixie dust or phoenix feathers. One might assume that if you know how the mathematics work, you could come up with a sensible facsimile, but in reality, only compiler writers are capable of creating such things...

I'm sorry, but i will have to disagree with that, since, a little time ago, one of my teachers asked the same thing, and there's a simple solution just as the one sturm suggested...

int main(){
   int c,n;
   float a,b,d=1;
   printf("Input a number\n");
   scanf("%d",&n);
   c=n-1;
   for (a=0;a<c;a+=d){
      b=a*a;
      if (b==n){
         b=a;
     a=c;
      }else{
     if (b>n){
        a-=d;
        d/=10;
     }
      }
   }printf("The square root of %d is %3.4f\n     Press >>ENTER<< to exit",n,b);
   getchar();
   getchar();
   _exit(0);
   return 0;
}

That will return any exact square root for any whole number... if you want a square root for a number with decimal points, you have to do some modifications... but that's the main idea...

[Terry Robinson]

OK, now that everyone has had a good joke about this - I had to do this years ago using a very primitive BASIC. I can't remember the exact algorithm, but I reasoned that guys like Sir Isaac Newton and his crowd didn't have calculators or even log tables and they did some pretty hairy calculations. So...I looked up the topic in some really old books to see how it was done before we had computers.

The trick is to make a guess, determine your error and then make a new guess based on your error. You may also have to specify a required accuracy range (since you can't get perfect for many numbers using binary math). You make a loop which continually refines your guess based on your last error and exit when the guess is within your required accuracy range. I remember that the code was only a few lines of BASIC and it only needed to loop a few times for even very large numbers.

Anyway, if no one gives you a straight answer by tomorrow I will try to remember just how it went and post here again, but that should be enough for you to figure it out.

Cheers.

[Narue]

>I'm sorry, but i will have to disagree with that, since, a little time ago,
>one of my teachers asked the same thing, and there's a simple solution
>just as the one sturm suggested...
Nichito meet sarcasm, sarcasm meet Nichito. I'm sure you'll become good friends. I was rather hoping that what I said was ridiculous enough that intelligent people would realize I was joking.

[ndeniche]

jesus... can't you let me be the hero just for once?? :P

i mean... i knew you couldn't be serious when you said it was impossible... just let me be happy...

[Narue]

>jesus... can't you let me be the hero just for once??
I'm always the villain, so you can't be anything but the hero in comparison.

[ndeniche]

hmmm... good to know...

[ndeniche]

The trick is to make a guess, determine your error and then make a new guess based on your error. You may also have to specify a required accuracy range (since you can't get perfect for many numbers using binary math). You make a loop which continually refines your guess based on your last error and exit when the guess is within your required accuracy range. I remember that the code was only a few lines of BASIC and it only needed to loop a few times for even very large numbers.

This is a good method, but it will NEVER return an exact answer...

[tformed]

Ok, I got it working by replacing the ln with log. :P

i get some warnings, which I will ignore for the time being. (I have everything defined as float, it tells me that conversion from double to float might lead to loss of value.)

Decimals work also.

I did and else statement where if the number is negative it gets the absolute value and does the program as is and places an "i" behind the result. leading imaginary numbers.

now i am trying to restrict characters, as the program shows a large number when a character is placed.

but the main program itself works, as it does the problem correctly.

I will post the warning later on. I will give it some more tries with the type, but so far as stated before i have everything as float.

Update:
#include <stdio.h>
#include <math.h>

int main(void)
{
float whome, heyyou;

printf("Place number to square root:\n");
scanf_s ("%f",&whome);

if (whome >= 0) {
heyyou= exp((1.0/2.0)*log(whome));
printf ("The square root of the number is: %5.4f\n",heyyou);
}
else
{
heyyou= exp((1.0/2.0)*log(abs(whome)));
printf ("The square root is: %5.4f i\n",heyyou);

}

return 0;
}

my warnings:

1>source.c(18) : warning C4244: '=' : conversion from 'double' to 'float', possible loss of data
1>source.c(23) : warning C4244: 'function' : conversion from 'float' to 'int', possible loss of data
1>source.c(23) : warning C4244: '=' : conversion from 'double' to 'float', possible loss of data

[Narue]

Ideally you would use double instead of float because double is the default floating-point type in C (it really looks like you're using C) and the standard library tends to assume it.

[tformed]

nope, i am using c++...as it has the extension of .cpp

I edited by warning so it would be shorter, must have taken out the pp at the end. :D

I am working from a book also, reading and trying.

[Narue]

>nope, i am using c++...as it has the extension of .cpp
Then your code is wrong. <stdio.h> and <math.h> are deprecated headers. You should be using <cstdio> and <cmath> instead. Also, cin and cout would make your life easier. It's a good idea to get into the habit because eventually you'll start wanting to extend the standard I/O for your own custom types. scanf and printf can't do that.

[tformed]

ok i will replace then, but then why is the cpp book explaining that one must use stdio.h and math.h if it is wrong.

just to let you know that i am still in chapter three :(

[Terry Robinson]

I just had to solve this, so I Googled it and found the answer a few seconds. No logs or any high math is required. And yes, it is true that it will not find the EXACT answer for a lot of numbers, but there are two reasons for that: First many numbers do not have an exact square root (kind of like Pi). Second, we are dealing with binary data which limits the accuracy for a lot of things (ever hear of round off error?). Anyway, here is the calculation. Sorry, it is in Pascal. I quit using C++ 10 years ago. It shouldn't be a problem to convert.

function SquareRoot(x, r: double): double;
var
last :double;
begin
last := 0;
repeat
last := r;
r := (r + (x/r))/2;
until (r = x/r) or (r = last);
result := r;
end;

Note the need for the variable last. That is necessary due to the possible error mentioned above. The final result may not be exact, but once the program cannot get any closer due to the imprecision of double and/or numbers with no exact square root, it will come up with the same approximation every time, so to avoid and endless loop, you must exit.

[Terry Robinson]

I forgot to point out in my last post that X is the number for which we need the square root and R is the initial guess. About anything can be used for R but a good guess will result in fewer loops than a bad one.

[ndeniche]

by the way tformed... ever considered using code tags?

[~s.o.s~]

> but then why is the cpp book explaining that one must use stdio.h
> and math.h if it is wrong.
Either the book is a relic or not its worth. Get a better book. The book most people seem to be recommending around here is 'Accelerated C++'. If you can't get hold of some decent books, try looking around for tutorials on the Internet; there are many out there.

[tformed]

> but then why is the cpp book explaining that one must use stdio.h
> and math.h if it is wrong.
Either the book is a relic or not its worth. Get a better book. The book most people seem to be recommending around here is 'Accelerated C++'. If you can't get hold of some decent books, try looking around for tutorials on the Internet; there are many out there.

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

also, i did use "

" but it still appeared with normal text.

[ndeniche]

i would recommend you the book i read, but... it's in spanish, so i think it would be of no use...