Hi, I have just created an algorithm and could this be the greatest algorithm invented for calculating square roots? Perhaps the answer is yes with 100% accuracy unlike some algorithms that round the last digit up. Below is the algorithm I have created and I used php. Also this algorithm can easily be imported into any language with any bitrate and is very scalable unlike some of the standard built in square root algorithms for some interpreters (all of the ones tested so far). Now below is the code with it in both the form of a class and the form of a function.

You may notice that the function name is funny but it is tatically named that way so that the string length of the function name is the same as the sqrt() function so you don't get qwerky results when comparing the two.

``````<?php
class sqrt {
public \$value;
function __construct(\$in) {
\$tmp = (int) \$in;
\$tmpp = (\$tmp/2);
for (\$i=1;(\$i*\$i)<=\$tmp;\$i*=2) {}
\$i/=2;
for (;(\$i*\$i)<=\$tmp;\$i++) {}
\$i--;
\$k=\$i;
\$i++;
if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
for (\$j=1;(\$i*\$i)>=\$tmp;\$j/=2,\$i=(\$j+\$k)) {}

\$v=strlen((string)\$j);
\$m=1/pow(10,\$v);
for (;(\$i*\$i)<=\$tmp;\$j+=\$m,\$i=(\$j+\$k)) {}
\$j-=(\$m);
\$i=\$j+\$k;

if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
//\$w = (strlen((string)pow(2,32))+1);
//\$w = same number as below
\$w = 11; //32 bit
\$q=\$m;
for (\$n=\$v+1;\$n<\$w;\$n++) {
\$m=1/pow(10,\$n);
\$p=pow(10,((\$n-\$v)+1));
for (\$o=0;\$o<\$p && (\$i*\$i)<=\$tmp;\$j+=\$m,\$i=(\$j+\$k),\$o++) {}
\$j-=\$m;
\$i=(\$j+\$k);
}
}
}
echo \$i;
\$this->value = \$i;
return \$this->value;
}

}
function mysq(\$in) {
\$tmp = (int) \$in;
\$tmpp = (\$tmp/2);
for (\$i=1;(\$i*\$i)<=\$tmp;\$i*=2) {}
\$i/=2;
for (;(\$i*\$i)<=\$tmp;\$i++) {}
\$i--;
\$k=\$i;
\$i++;
if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
for (\$j=1;(\$i*\$i)>=\$tmp;\$j/=2,\$i=(\$j+\$k)) {}

\$v=strlen((string)\$j);
\$m=1/pow(10,\$v);
for (;(\$i*\$i)<=\$tmp;\$j+=\$m,\$i=(\$j+\$k)) {}
\$j-=(\$m);
\$i=\$j+\$k;

if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
//\$w = (strlen((string)pow(2,32))+1);
//\$w = same number as below
\$w = 11; //32 bit
\$q=\$m;
for (\$n=\$v+1;\$n<\$w;\$n++) {
\$m=1/pow(10,\$n);
\$p=pow(10,((\$n-\$v)+1));
for (\$o=0;\$o<\$p && (\$i*\$i)<=\$tmp;\$j+=\$m,\$i=(\$j+\$k),\$o++) {}
\$j-=\$m;
\$i=(\$j+\$k);
}
}
}
return \$i;
}

\$s = microtime(true);
mysq(128);
\$e = microtime(true);

\$a=(\$e-\$s);
unset(\$e,\$s);

sleep(1);

\$s = microtime(true);
sqrt(128);
\$e = microtime(true);
echo 'mysq time   ='.\$a.'<br>';
echo 'mysq result='.mysq(128).'<br>';
echo 'sqrt time  ='.(\$e-\$s).'<br>';
echo 'sqrt result='.sqrt(128).'<br>';
echo 'The mysq function is '.bcdiv(substr((\$e-\$s),0,11),\$a,0).' times faster for this calculation.<br>';``````
7
Contributors
7
Replies
8
Views
7 Years
Discussion Span
Last Post by firstPerson

No, it's not the greatest method ever. The Newton-Raphson method is faster and you have a lot of inefficient code in there.

Doing one square root shouldn't take enough time to be measurable on any computer made after 1990. If you can actually get a real time measurement, you are just showing how slow PHP is.

I just discovered after an IRC chat that the measurements are incorrect and as measured my script is slower. However I'll post an update for an algorithm that is 4-6 times slower than the php inbuilt algorithm and I am working on fixing the glitches I have made to make it faster. I'm sure I can make it 6 times faster somehow.

``````<?php
function mysq(\$in) {
\$tmp = (int) \$in;
\$tmpp = (\$tmp/2);
for (\$x=0,\$i=1;(\$i*\$i)<=\$tmp;\$i*=2,\$x++) {}
\$i/=2;
for (;(\$i*\$i)<=\$tmp;\$i++) {}
\$i--;
\$k=\$i;
\$i++;
if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
for (\$j=1;(\$i*\$i)>=\$tmp;\$j/=2,\$i=(\$j+\$k)) {}

\$v=strlen((string)\$j);
\$m=1/pow(10,\$v);
for (\$g=(32-\$x);\$g>=0;\$g--) { //32 is for 32 bits
\$z=\$m*pow(2,\$g);
for (;(\$i*\$i)<=\$tmp;\$j+=\$z,\$i=(\$j+\$k)) {}
\$j-=\$z;
\$i=\$j+\$k;
}

if ((\$i*\$i)>\$tmp || (\$i*\$i)<\$tmp) {
//\$w = (strlen((string)pow(2,32))+1);
//\$w = same number as below
\$w = 11; //32 bit
\$q=\$m;
for (\$n=\$v+1;\$n<\$w;\$n++) {
\$m=1/pow(10,\$n);
\$p=pow(10,((\$n-\$v)+1));
if (\$m>5) {
for (\$o=0;\$o<\$p && (\$i*\$i)<=\$tmp;\$j+=\$m,\$i=(\$j+\$k),\$o++) {}
\$j-=\$m;
\$i=(\$j+\$k);
} else {
for (\$o=0;\$o<\$p && (\$i*\$i)>=\$tmp;\$j-=\$m,\$i=(\$j+\$k),\$o++) {}
\$j+=\$m;
\$i=(\$j+\$k);
}
}
}
}
return \$i;
}

\$s = microtime(true);
mysq(128);
\$e = microtime(true);

\$a=(\$e-\$s);
unset(\$e,\$s);

sleep(1);

\$s = microtime(true);
sqrt(128);
\$e = microtime(true);
echo 'mysq time   ='.rtrim(number_format(\$a, 64, '.', ''),'0').'<br>';
echo 'mysq result='.mysq(128).'<br>';
echo 'sqrt time  ='.rtrim(number_format((\$e-\$s), 64, '.', ''),'0').'<br>';
echo 'sqrt result='.sqrt(128).'<br>';
echo 'The mysq function is '.rtrim(number_format((\$a/(\$e-\$s)), 64, '.', ''),'0').' times faster for this calculation.<br>';``````

with 100% accuracy unlike some algorithms

There is no any square root algorithm that guarantee a 100% accurate result. For example: Let's say what is 100% accurate result of square root of 2?

greatest algorithm invented for calculating square roots?

Fast inverse square root is still one of amazing algorithm I have seen so far.

Anyway, still it is nice to see people try to invent something new.

There is no any square root algorithm that guarantee a 100% accurate result. For example: Let's say what is 100% accurate result of square root of 2?

The IEEE floating-point specification requires the square root operation to return the representable number that is the correctly rounded value of the infinite-precision square root. So in that sense, it is reasonable to talk about a particular implementation as being accurate or not.

Wouldn't FSQRT on x86 processors be quicker? Or for many values SQRTPS?

Basically anything would be faster.

Basically anything would be faster.

Well....

``````float squareRoot(float num){
const float epsilon = 10e-6;
float start = epsilon;
while( start * start < num) start += epsilon;
return start;
}``````
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.