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?
Visual studio 2008. Just take away the unsigned part, I guess.
Erratum:
Reference to my post # 52 in this thread, Line 17 of NathanOliver's code
for (;;)was not the bug causing problem to his program. Sorry for the mistake.
In a private message I have just received from NathanOliver, a bug in his "raisedTo function" has since been fixed, and his ambitious nth root program is working. However, fine-tuning for larger numbers exceeding 12 digit consecutive numbers may improve performance.
The codes may be finalized in due course.
Regards,
Dear firsPerson,
Yes after removing "unsigned" from line 20, your program is working. However, the speed of computation could be improved in comparison with other high-performance algorithms to date.
Regards,
Dear firsPerson,
Yes after removing "unsigned" from line 20, your program is working. However, the speed of computation could be improved in comparison with other high-performance algorithms to date.
Regards,
Well I not trying to compete. I am just helping for future reference. I
believe that there are plenty of square root functions here as an
alternative to c++ sqrt(...);
Dear firsperson,
Competitiveness is good for technological advancement and human improvement.
You must be proud of your own competitive spirit. That is something I had gleaned from our current World Sqrt Champion, Foamgum, whose algorithms works even for a 150-digits consecutive number. In fact, his is the only algorithm which works with such huge number, without relying on sqrt() , pow() or exp() functions in C++, and very fast too.
After posting #52, we saw a surge of mind-boggling Sqrt algorithms in this informal Sqrt World Championship. We just simply can not underestimate human ingenuity in this C++ community.
We have learnt from invisal's magic hex constant that square root computation has practical application in games programming for lighting and reflection effects. There is much truth in what Confucius said, "The essence of knowledge is in its application". I am sure there are many other practical applications of simple mathematical computations, even for something seemingly academic like computation of the square root of a number.
Also, besides the good mental exercises, there is a good feeling that all of us are like citizens of a borderless world, where there are no boundaries, and no religious, racial, cultural, economic or gender barriers dividing us. This C++ community may be a model for future world peace.
Regards,
hi all after talking with yonghc i have a working version. i am going to be doing some performance testing to see if i can make it better and will post it if i come up with anything.
A better newton :
#include <iostream>
#include<cmath>
using std::cout;
using std::endl;
typedef unsigned long long Uint64;
long getDeg(double Num)
{
long deg = 1;
double T = Num;
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Uint64 guess(double num, int itr = 10)
{
int deg = getDeg(num);
Uint64 i = Uint64( num * 0.35 );
while( i*i > num) i -= deg;
for(; i < num; i++)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
double Sqrt(double Num)
{
long deg = getDeg(Num);
int itr = deg + 10;
double initGuess = double(guess(Num,itr));
long Precision = 15 + deg;
double root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
int main()
{
double P = 12345678901234567890.99999999; //Any bigger, I get compiler error
cout.precision(10);
cout<<"Cmath : "<<sqrt(P)<<endl;
cout<<"Mines : "<<Sqrt(P)<<endl;
return 0;
}Dear frstPerson,
There is vast improvement in your better Newton. I would like to test it further. Meanwhile, just some preliminary comments...
I am not sure if it is better to add "using namespace std" to replace your two lines which i have remarked out, to cover other keywords besides cout and endl if any. Pls enlighten me on this.
using namespace std;
//using std::cout;
//using std::endl;
regards,
Dear firstPerson,
Congratulations! To date, your better Newton algorithms is now ranked fourth in this thread's informal Sqrt World Championship.
Though CODE::BLOCK did not report any problem in compiling your better Newton codes, a 21-digits number greater than or equal to 123456789012345678901 will not compute its square root, or take too long. I am not sure which.
Your Taylor Series algorithm retains the second placing. You are smart, and you do have tenacity and fighting spirit.
Regards,
It takes too long because the number passes the limit of double.
If you tried another data type thats greater than double, long double
perhaps in some compiler, then it should work.
Make every data type th same, something bigger than double, if you
have it. The algorithm should work for as much as the limit of a compound datatype.
It takes too long because the number passes the limit of double.
If you tried another data type thats greater than double, long double
perhaps in some compiler, then it should work.
Make every data type the same, something bigger than double, if you
have it. The algorithm should work for as much as the limit of a compound datatype.
Replace the typedef with the highest amount of data_type(i.e the most bit supported) on your compiler. It should work.
#include <iostream>
#include<cmath>
using std::cout;
using std::endl;
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
uInt64 getDeg(Ldouble Num)
{
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10)
{
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
sub = deg * 0.5;
for(; i < num; i+=sub)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
Ldouble Sqrt(Ldouble Num)
{
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
int main()
{
Ldouble P = 12345678901234567899.999; //Any bigger, I get compiler error
cout.precision(40);
cout<<"Cmath : "<<sqrt(P)<<endl;
cout<<"Mines : "<<Sqrt(P)<<endl;
return 0;
}well after rechecking my code i am getting a compounding error with the division of floating point number and after a 12 digit number there is enough error each loop that it makes finding a 13 digit or longer root impossible. after pulling out my old math book for a refresher in logarithms i have decide that this is much faster and smaller unfortunately it goes against the OP's problem of not using the pow function
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
long double number, root, answer;
cout << "enter a number for the root: ";
cin >> number;
cin.get();
cout << "enter the root you wish to find: ";
cin >> root;
cin.get();
answer = pow(10, log10(number)/root);
cout.precision(20);
cout << root << char(251) << number << " = " << answer << "\n";
cin.get();
return 0;
}Dear All,
With the laudable efforts of the last two posters in this thread, which I believe were mentally challenging and exhausting as well, perhaps the OP, and the second OP who resurrected this two-year-old thread should find closure acceptable after I post the final results with 5 placings and final C++ codes incorporating various working and commendable Sqrt algorithms soon.
I believe the final Sqrt comparison program -- sqrt.cpp -- is impartial and transparent enough -- though as yet not cleanly as pointed out by firstPerson as it is still under construction to cater for carious data-types during data entry -- for the purpose of comparing performance of various Sqrt algorithms from C++programmers from different backgrounds, viz., mathematicans, game programmers, professional programmers, students, etc.
Regards,
Round 3 - Final round.
--------------------------
Results
--------
Congratulations to Foamgum, firstPerson, invisal, Sturm and NathanOliver for their commendable Sqrt programs.
The final results of performance tests were obtained using the program sqrt.cpp compiled using CODE::BLOCK 8.02. The codes are shown below.
First place - Foamgum's Spirit MySQRT algorithm (opt. 8)
Second place - firstPerson's Taylor series algorithm (opt.5)
Third place - invisal's inverse Square Root algorithm (opt.7)
Fourth place - firstPerson's Mines2 (opt.12)
Fifth place - firstPerson's Better Newton (opt.10)
Sixth place - Sturm's for-looping (opt.2)
Seventh place - NathanOliver's nth root (opt.13)
To date, 13 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
opt.9 ((firstPerson) proto newton Sqrt
opt.10 (firstPerson) Better Newton
opt.11 (firstPerson) Mines1 Sqrt
opt.12 (firstPerson) Mines2 Sqrt
opt.13 (NathanOliver) Sqrt
1. Foamgum's algorithm is original and answers for numbers up to 150 digits number are correct. Larger numbers not tested yet.
2. firstPerson's Taylor's series algorithm's answers for numbers up to 60 digits are correct.
3. invisal's Inverse Square root algorithm uses a magic hex constant. Its answers for numbers up to 30 digits are correct.
4. firstPerson's Mines2 Sqrt algorithm can handle up to 20-digits numbers.
5. firstPerson's Better Newton algorithm can handle up to 20-digits number, but speed is slower than Mines2.
6. Sturm's for-looping Sqrt is simple and effective, and can handle up to 14-digits numbers.
7. NathanOliver's nth root algorithm can handle up to 11-digits number not only for square root, but nth root. For example, it answered correctly the 4th root of 16 as 2. However, for comparison only square root was used. Numbers exceeding 11-digits will give problem.
NathanOliver's ambitious nth root of a number algorithm has been debugged and is working for numbers upto 11 digits.
firstPerson's Better Mines and Better Newton are indeed improved algorithms, which can handle up to 20-digits numbers. But Better Newton was excruciatingly much slow when a 11-digit number, viz., 12345678901 was entered than when a 20-digits number, viz., 12345678901234567890 was entered. Anybody knows the reason?
The final Sqrt program below is used for comparison of performance of the algorithms. Numbers up to 30, 40, 50 and 60 digits data were entered, and the answers given by various algorithms were 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. Better Newton surprisingly showed better performance with some larger than some smaller numbers. It would have been skipped if it could not handle larger numbers, up to 20-digits.
Other algorithms were either too slow, were disqualified.
You may 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.
Discussion
------------
Some knowledge of the range of values of different numeric types, and the historical precision of computation of the e constant may offer a better perspective on the accuracy of the algorithms above.
Range of values
The table below is based on some C++ text-book, which mentioned that the range of values of different numeric type are dependent on compilers and may be as follows:
Type Values
float 7 significant digits. 3.4 X 10 ^38 (+/-10^38)
double 15 significant digits 1.7 X 10^308
long double 19 significant digits 1.7 X 10 ^4932
Significant digits
For numbers, you could replace the use of a notation like 42.5×10^9 by a notation like 42.5E9, borrowed from programming languages.
The term significant figures refers to the number of important single digits (0 through 9 inclusive) in the coefficient of an expression in scientific notation . The number of significant figures in an expression indicates the confidence or precision with which an engineer or scientist states a quantity.
The table shows several examples of numbers written in standard decimal notation (first column) and in scientific notation (second column). The third column shows the number of signficant figures in the corresponding expression in the second column.
Decimal expression Scientific notation Sig. figs.
1,222,000.00 1.222 x 10 6 4
1.22200000 x 10^ 6 9
reference : http://www.cs.tut.fi/~jkorpela/math/
A double number can have a value of up to 308 digits, and a long double, up to 4932 digits. This would allow the precision of computation using C++ to be rather high.
Historical computation of the e constant.
----------------------------------------------
firstPerson's Taylor series was used to compute square roots.
Taylor series, e^x can be used to calculate the value of e, when x=1.
The precision of computing e (Euler's constant) -- as measured using significant digits -- had increased tremendously since its discovery in the 18th century, as shown by the table below:
Known digits of e
--------------------
The number of known digits of e has increased dramatically during the last decades. This is due both to the increase of performance of computers as well as to algorithmic improvements.
Number of known decimal digits of e.
Date Decimal digits Computation performed by
1748 18 Leonhard Euler
1853 137 William Shanks
1871 205 William Shanks
1884 346 J. Marcus Boorman
1946 808 Unknown
1949 2,010 John von Neumann (on the ENIAC)
1961 100,265 Daniel Shanks & John Wrench
1978 116,000 Stephen Gary Wozniak (on Apple II)
1994 10,000,000 Robert Nemiroff & Jerry Bonnell
1997 May 18,199,978 Patrick Demichel
1997 Aug 20,000,000 Birger Seifert
1997 Sep 50,000,817 Patrick Demichel
1999 Feb 200,000,579 Sebastian Wedeniwski
1999 Oct 869,894,101 Sebastian Wedeniwski
1999 Nov 21 1,250,000,000 Xavier Gourdon
2000 July 10 2,147,483,648 Shigeru Kondo & Xavier Gourdon
2000 July 16 3,221,225,472 Colin Martin & Xavier Gourdon
2000 Aug 2 6,442,450,944 Shigeru Kondo & Xavier Gourdon
2000 Aug 16 12,884,901,000 Shigeru Kondo & Xavier Gourdon
2003 Aug 21 25,100,000,000 Shigeru Kondo & Xavier Gourdon
2003 Sep 18 50,100,000,000 Shigeru Kondo & Xavier Gourdon
2007 April 27 100,000,000,000 Shigeru Kondo & Steve Pagliarulo
2009 May 6 200,000,000,000 Shigeru Kondo & Steve Pagliarulo
Reference: http://en.wikipedia.org/wiki/E_%28mathematical_constant%29
Conclusion
------------
With the PCs and C++ compilers that most of us have, the greatest accuracy of our computation would be that achieved between 1949 and 1961.
In the 21st century, precision up to 200 billion significant digits for e can be achieved using supercomputers. This is much higher than what Apple's Wozniak achieved in 1978 with his Apple II, 116,000 decimal digits.
Our tools are supposed to be much more advanced than Apple's in 1978. However, we can only make do with what we have, and be satisfied with our results. We need not be perfectionists.
Let us find solace in changing the topic. For the purpose of reference, the following prefixes and symbols to describe numbers may be useful:
Prefix Symbol(s) Power of 10 Power of 2
------- ------------ ------------- ------------
yocto- y 10^-24 * --
zepto- z 10^-21 * --
atto- a 10^-18 * --
femto- f 10^-15 * --
pico- p 10^-12 * --
nano- n 10^-9 * --
micro- m 10^-6 * --
milli- m 10^-3 * --
centi- c 10^-2 * --
deci- d 10^-1 * --
(none) -- 10^0 2^0
deka- D 10^1 * --
hecto- h 10^2 * --
kilo- k or K ** 10^3 2^10
mega- M 10^6 2^20
giga- G 10^9 2^30
tera- T 10^12 2^40
peta- P 10^15 2^50
exa- E 10^18 * 2^60
zetta- Z 10^21 * 2^70
yotta- Y 10^24 * 2^80
* Not generally used to express data speed
** k = 10^3 and K = 2^10
Regards,
// sqrt InputCtrl&sqrt YBM 27 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>
#include<cmath>
#include<limits>
#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 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;
if (RaisedTo(sqrt, nthRoot) == number)
return sqrt;
for ( double i = sqrt; i <= (temp + 1); i += plusplus){
if (RaisedTo(i, nthRoot) > number) {
sqrt = i - plusplus;
digits++;
// cout << sqrt << "\n"; // added this so i could see the process
break;
}
}
}
}
double RaisedTo(double base, int power) {
double temp = base;
for (int i = 1; i < power; i++) {
base *= temp;
}
return base;
}
double newtonSqrt(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;
}
typedef unsigned long long Uint64;
long getDeg(double Num) {
long deg = 1;
double T = Num;
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Uint64 guess(double num, int itr = 10) {
int deg = getDeg(num);
Uint64 i = Uint64( num * 0.35 );
while( i*i > num) i -= deg;
for(; i < num; i++) {
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
double NewtonSqrt2(double Num) {
long deg = getDeg(Num);
int itr = deg + 10;
double initGuess = double(guess(Num,itr));
long Precision = 15 + deg;
double root = 0.0;
for( Precision; Precision; --Precision) {
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
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-= 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 SquareRootOfse(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;
}
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
uInt64 getDeg(Ldouble Num) {
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10) {
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
sub = deg * 0.5;
for(; i < num; i+=sub) {
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
Ldouble fpSqrt(Ldouble Num) {
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision) {
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
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 = 136;
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 and above.";
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 skipped "; }
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;
cout << "\n\t9. (firstperson proto Newton Sqrt Ans.: " << newtonSqrt(num);
if (num < 123456789012345678901.0) {
cout << "\n\t10.(firstperson Better Newton Sqrt Ans.: " << NewtonSqrt2(num);
}
else { cout << "\n\t11.(firstPerson) Better Newton Sqrt skipped "; }
if (fnum <= 1000000000) {
cout << "\n\t11.(firstperson)'s Mines1 sqrt Ans.: " <<SquareRootOfse(data_type(fnum));
}
else { cout << "\n\t11.(firstPerson)'s Mines1 sqrt skipped "; }
Ldouble P = Ldouble(num);
if (P <= 12345678901234567899.999) { //Any bigger, I get compiler error
// cout.precision(40);
cout << "\n\t12.(firstperson)'s Mines2 sqrt Ans.: " << fpSqrt(P);
}
else {cout << "\n\t12.(firstPerson)'s Mines2 sqrt skipped ";}
if (num <= 12345678901.0) {
cout << "\n\t13.(NathanOliver) nth root Ans.: "<< NthRoot(num, 2);
}
else {cout << "\n\t13.(NathanOliver) nth root skipped "; }
}
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 EndWe shall see if format of display is improved within code tags. WYSIWYG?
Number of known decimal digits of e.
Date Decimal digits Computation performed by
----- ----------------- ------------------------------
1748 18 Leonhard Euler
1853 137 William Shanks
1871 205 William Shanks
1884 346 J. Marcus Boorman
1946 808 Unknown
1949 2,010 John von Neumann (on the ENIAC)
1961 100,265 Daniel Shanks & John Wrench
1978 116,000 Stephen Gary Wozniak (on Apple II)
1994 10,000,000 Robert Nemiroff & Jerry Bonnell
1997 May 18,199,978 Patrick Demichel
1997 Aug 20,000,000 Birger Seifert
1997 Sep 50,000,817 Patrick Demichel
1999 Feb 200,000,579 Sebastian Wedeniwski
1999 Oct 869,894,101 Sebastian Wedeniwski
1999 Nov 21 1,250,000,000 Xavier Gourdon
2000 July 10 2,147,483,648 Shigeru Kondo & Xavier Gourdon
2000 July 16 3,221,225,472 Colin Martin & Xavier Gourdon
2000 Aug 2 6,442,450,944 Shigeru Kondo & Xavier Gourdon
2000 Aug 16 12,884,901,000 Shigeru Kondo & Xavier Gourdon
2003 Aug 21 25,100,000,000 Shigeru Kondo & Xavier Gourdon
2003 Sep 18 50,100,000,000 Shigeru Kondo & Xavier Gourdon
2007 April 27 100,000,000,000 Shigeru Kondo & Steve Pagliarulo
2009 May 6 200,000,000,000 Shigeru Kondo & Steve Pagliarulo
Reference: http://en.wikipedia.org/wiki/E_%28mathematical_constant%29Moderator, Please help.
With a minor change, The newton works for at least 200 digits, any more
wasn't tested.
#include <iostream>
#include<cmath>
using std::cout;
using std::endl;
using std::cin;
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
uInt64 getDeg(Ldouble Num)
{
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10)
{
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
if(deg < 10) sub = 1.1;
else if(deg < 20) sub = 1.25;
else sub = 1.5;
for(; i < num; i*=sub)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-sub);
}
return (i-sub);
}
Ldouble Sqrt(Ldouble Num)
{
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
if(root == Num) return root;
}
return root;
}
int main()
{
while(1)
{
Ldouble P = 0;
cin >> P;
cout.precision(40);
cout<<"The degree of you number is : "<<getDeg(P)<<endl;
cout<<"Cmath : "<<sqrt(P)<<endl;
cout<<"Mines : "<<Sqrt(P)<<endl;
cout<<"\n\n\n";
}
return 0;
}Review of Results - Round 3
--------------------------------
The history of computation of the constant e is more than 260 years since 1748. Better computers and algorithms have led to greater precision in its calculation.
The algorithms for computation of Square root in this thread have achieved greater precision within a relatively short time after a lapse of 2 years. Since there is no end to improvement of computers and algorithms, there may not be any necessity to end this thread yet, as long as C++programmers can come up with something better than the best algorithms to date, 309-digits consecutive numbers, most probably in our lifetime.
The latest algorithm from firstPerson has warranted some changes to the placings.
Congratulations to Foamgum and firstPerson for their leading Sqrt algorithms.
Foamgum's and firstPerson's Better Newton2 algorithm can handle numbers up to 309 digits. Larger numbers will give problem. Even C++'s sqrt() and other algorithms using pow() functions will give infinity as answers to a 310-digits consecutive number.
The results to date are as follows:
First place - Foamgum's Spirit MySQRT algorithm (opt. 8) and
firstPerson's Better Newton2 (opt.10)
Third place - firstPerson's Taylor series algorithm (opt.5)
Fourth place - invisal's inverse Square Root algorithm (opt.7)
Fifth place - firstPerson's Mines2 (opt.12)
Sixth place - Sturm's for-looping (opt.2)
Seventh place - NathanOliver's nth root (opt.13)
The current list comprises nine working algorithms for computing square-roots as follows:
opt.1 (tformed) exp() algorithm
opt.2 (Sturm) looping algorithm
opt.3 (Salem) suggested common log algorithm
opt.5 (firstPerson) Taylor's series
opt.7 (invisal) Inverse Square Root
opt.8 (Foamgum) Spirit MySQRT
opt.10 (firstPerson) Better Newton2
opt.12 (firstPerson) Mines2 Sqrt
opt.13 (NathanOliver) Sqrt
Opt.10 has been replaced by much a superior version. Four weaker algorithms opt. 4, 6, 9, 11 have been removed.
The final results of performance tests were obtained using the program sqrt.cpp compiled using CODE::BLOCK 8.02.
The sqrt program has been improved to allow for continuously increasing the number of digits up to 309; more than that, the program will not work.
The latest codes are shown below. Suggestions for improvement of the sqrt program are welcome. We may not be able to use C++'s sqrt() as a benchmark for the next round. Homemade sqrt() will definitely outdo C++'s sqrt().
In firstPerson's program, assigning P= 12345........ (310-digits) will cause program to freeze up with a blank screen with a blinking cursor on top left corner. Remarking out line 40, you see only Cmath : Infinity.
Line 40: // cout<<"The degree of you number is : "<<getDeg(P)<<endl;
Regards,
// 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>
#include<cmath>
#include<limits>
#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 = "";
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
Ldouble weight=0;
Ldouble num=0;
// long 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 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;
if (RaisedTo(sqrt, nthRoot) == number)
return sqrt;
for ( double i = sqrt; i <= (temp + 1); i += plusplus){
if (RaisedTo(i, nthRoot) > number) {
sqrt = i - plusplus;
digits++;
// cout << sqrt << "\n"; // added this so i could see the process
break;
}
}
}
}
double RaisedTo(double base, int power) {
double temp = base;
for (int i = 1; i < power; i++) {
base *= temp;
}
return base;
}
//typedef long double Ldouble; //Change to the highest compound data_type you have
//typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
uInt64 getDeg(Ldouble Num)
{
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10)
{
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
if(deg < 10) sub = 1.1;
else if(deg < 20) sub = 1.25;
else sub = 1.5;
for(; i < num; i*=sub)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-sub);
}
return (i-sub);
}
Ldouble NewtonSqrt2(Ldouble Num)
{
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
if(root == Num) return root;
}
return root;
}
typedef unsigned long long Uint64;
long getDeg(double Num) {
long deg = 1;
double T = Num;
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Uint64 guess(double num, int itr = 10) {
int deg = getDeg(num);
Uint64 i = Uint64( num * 0.35 );
while( i*i > num) i -= deg;
for(; i < num; i++) {
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
Ldouble fpSqrt(Ldouble Num) {
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision) {
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
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 = 136;
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;
}
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;
string* 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] = {" "," ","Enter a number : "," "," "};
double e=2.7182818283;
int main() {
num=0;
double heyyou,whome;
brk=0;
system ("color 0a");
redo:
do {
system ("CLS");
cout << "\n Esc:Exit FINDING THE SQUAREROOT OF A NUMBER ";
cout << "\n Only numbers and 1 dec. allowed, ";
sweight=datainp(efld[condi],condi);
len=sweight.length();
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\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;
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;
Ldouble fpP;
fpP = Ldouble(num);
cout << "\n\t10.(firstperson Better Newton Sqrt(New27Sep2009) Ans.: " << NewtonSqrt2(fpP);
Ldouble P = Ldouble(num);
if (P <= 12345678901234567899.999) { //Any bigger, I get compiler error
// cout.precision(40);
cout << "\n\t12.(firstperson)'s Mines2 sqrt Ans.: " << fpSqrt(P);
}
else {cout << "\n\t12.(firstPerson)'s Mines2 sqrt skipped ";}
if (num <= 12345678901.0) {
cout << "\n\t13.(NathanOliver) nth root Ans.: "<< NthRoot(num, 2);
}
else {cout << "\n\t13.(NathanOliver) nth root skipped "; }
}
else {cout <<"\x7";}
cout << "\n\nCurrent No. of digits: " << len << "\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;
redo2:
extended=0;
curs=0;
decf=0;
//std::string concate = "";
// gotoxy(xc[condi-1],yc[condi-1]);
cout << efld[condi-1] << endl;
cout << concate;
// 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) {
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 EndSecond Review of Results - Round 3
------------------------------------------
This is it.
Two Homemade square root algorithms in this forum outperform C++ sqrt() function.
The sqrt program had to be upgraded out of necessity, because I suddenly realized that the earlier version did not do justice to the sqrt algorithms posted in this forum.
After a flurry of private-message exchanges with relevant participants in this forum, the sqrt program used for comparison of performance of square-root-computating algorithms contributed by participants in this forum had been upgraded.
Press F12 to go into cin mode to enter numbers exceeding 309 digits (double maximum value is 1.7E +/-308). User-friendliness has to be sacrificed in order to achieve greater precision and capability of the sqrt program shown below. String to numeric conversion has to be eschewed because only 17 significant digits could be converted, the rest could be garbage or zeroes depending on the converting functions used, including atof(), sstream and strtod(), thus adversely reducing accuracy of computation.
Results of the latest sqrt program prove that the top two homemade Sqrt algorithms seemingly outperform C++'s sqrt() functions in being able to handle a 400*-digits consecutive number. Sqrt() and all other algorithms including those using pow() functions either showed infinity, or incorrect answers as square roots of that 400-digits number. This is a historic achievement, isn't it? Figures do not lie, right?
* Higher value than 400 digits have not yet been tested.
I used the word seemingly because my respect for scientific integrity due to my research background forbids me from misleading people all the way. Pardon me for being just curious to find out for how long can I, a C++ novice with less than a month's exposure to C++ bent the truth a little bit by withholding some information regarding C++ programming from C++ enthusiasts in this forum.
Yes, I am withholding some information, which I discovered accidentally. I may reveal it at a later stage if no one can prove me wrong in declaring that the top two sqrt algorithms contributed by Foamgum and firstPerson in this forum outperform C++'s sqrt() functions.
Nevertheless the laudable efforts of Foamgum and firstPerson should not be affected in any way by my curiosity.
Congratulations to Foamgum and firstPerson, the current C++ Sqrt World Champions -- in this thread -- who have done their countries, Australia and Nepal respectively, proud.
Regards,
// sqrt InputCtrl & sqrt YBM 28 Sep 2009
#include <windows.h> // WinApi header
#include <iostream>
#include <string>
#include <conio.h>
#include <stdlib.h>
#include <iomanip>
#include <stdio.h>
#include <cmath>
#include <limits>
#define maxloop 5
using std::cout;
using std::endl;
using std::cin;
using std::string;
string spaz(int&,int,string&);
string datainp(string,int);
int escx=0;
int curs=0;
int extended=0;
string concate = "";
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
Ldouble weight=0;
Ldouble num=0;
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 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;
if (RaisedTo(sqrt, nthRoot) == number)
return sqrt;
for ( double i = sqrt; i <= (temp + 1); i += plusplus){
if (RaisedTo(i, nthRoot) > number) {
sqrt = i - plusplus;
digits++;
// cout << sqrt << "\n"; // added this so i could see the process
break;
}
}
}
}
double RaisedTo(double base, int power) {
double temp = base;
for (int i = 1; i < power; i++) {
base *= temp;
}
return base;
}
uInt64 getDeg(Ldouble Num)
{
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10)
{
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
if(deg < 10) sub = 1.1;
else if(deg < 20) sub = 1.25;
else sub = 1.5;
for(; i < num; i*=sub)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-sub);
}
return (i-sub);
}
Ldouble NewtonSqrt2(Ldouble Num)
{
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
if(root == Num) return root;
}
return root;
}
typedef unsigned long long Uint64;
long getDeg(double Num) {
long deg = 1;
double T = Num;
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Uint64 guess(double num, int itr = 10) {
int deg = getDeg(num);
Uint64 i = Uint64( num * 0.35 );
while( i*i > num) i -= deg;
for(; i < num; i++) {
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
Ldouble fpSqrt(Ldouble Num) {
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision) {
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
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 = 136;
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;
}
long double MySQRT(long double number, int *iterations) { // Foamgum's Spirit MySQRT
long double bfg, cfg, 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;
bfg = (1.0 + number)/2; // First estimate of square root of number.
cfg = (bfg - number/bfg)/2; // Correction to give a better estimate.
while(cfg > e && (*iterations) < 1000) {
f = bfg; // For very small and very large values we will see
bfg -= cfg; // if the correction has any effect.
if(f == bfg) // Applying the correction made no difference to our answer.
return bfg;
cfg = (bfg - number/bfg)/2; // A revised correction.
++(*iterations); // A counter to measure the effectiveness of our algorithm.
}
return bfg;
}
int xcz=0;
int decf=0;
int ctr =0;
int cc=0;
int brk=0;
int len=0;
std::string xcon;
char inpg;
string* 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;
int cinmode=0;
char efld[maxloop][25] = {" "," ","Enter a number : "," "," "};
//double e=2.7182818283;
int main() {
num=0;
double heyyou,whome;
brk=0;
system ("color 0a");
redo:
do {
if (cinmode==0) {
system ("CLS");
cout << "\n Esc:Exit F12:cin>> mode FINDING THE SQUAREROOT OF A NUMBER ";
cout << "\n Only numbers and 1 dec. allowed, ";
sweight=datainp(efld[condi],condi);
len=sweight.length();
}
if (cinmode==12) {
system ("CLS");
cout << "\n cin mode ON FINDING THE SQUAREROOT OF A NUMBER ";
cout << "\n Enter a number : " << endl;
cin >> weight;
}
if (brk==1) {break;}
num=weight;
if (num >0) {
whome=num;
//cout << "\nN:"<<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\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;
float fnum;
fnum=float(num);
x = invsqrt(fnum);
cout << "\n\t7. (invisal) Inv.SquareRoot, hex const.0x5f3759df.Ans.: " << x;
long double afg, bfg; // Foamgum
int count(0);
afg = num;
bfg = MySQRT(afg, &count);
cout << "\n\t8. (Foamgum) Spirit MySQRT Ans.: " << bfg;
Ldouble fpP;
fpP = Ldouble(num);
cout << "\n\t10.(firstperson Better Newton Sqrt(New27Sep2009) Ans.: " << NewtonSqrt2(fpP);
Ldouble P = Ldouble(num);
if (P <= 12345678901234567899.999) { //Any bigger, I get compiler error
// cout.precision(40);
cout << "\n\t12.(firstperson)'s Mines2 sqrt Ans.: " << fpSqrt(P);
}
else {cout << "\n\t12.(firstPerson)'s Mines2 sqrt skipped ";}
if (num <= 12345678901.0) {
cout << "\n\t13.(NathanOliver) nth root Ans.: "<< NthRoot(num, 2);
}
else {cout << "\n\t13.(NathanOliver) nth root skipped "; }
}
else {cout <<"\x7";}
if (cinmode==0){
cout << "\n\nCurrent No. of digits: " << len << "\t<Press Any to cont.> ";getch();
}
else {cout << "\n\nCurrent No. of digits: " << getDeg(num) << "\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;
redo2:
extended=0;
curs=0;
decf=0;
cout << efld[condi-1] << endl;
cout << concate;
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;
if (c == 0x00 || c == 0XE0 || c==224 || c==0) {
extended = getch();
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 (cinmode==12) {c=13;}}
}
} while (c != 13); // ascii 13 is <enter> or <carriage return>
if (cinmode==12) {return concate;}
if (c !=27) {
len = concate.length();
if (condi==3) {
char xxc[len]; // intialise array
concate.copy(xxc,len); // fills in array with characters from the string
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 (xcz==134) {
extended=0;
cinmode=12;
}
// 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 EndDear All,
Theoretically, Foamgum and firstPerson's square root algorithms can handle up to a 4900-digits number (the actual limits depend on compilers), far exceeding the 309-digit limit beyond which all other sqrt algorithms failed, including C++'s sqrt() basing on the results obtained using the current* sqrt program written for algorithmic comparison.
* If we can accept that the above is true until proven wrong -- like innocent until proven guilty -- there is much truth in the saying "If ignorance is bliss, it is folly to be wise."
I would be interested to know if there is any problem with the sqrt program's cin mode entry for large numbers above 400 digits, which has not been tested. I have tested up to 400 digits, whereas the theoretical limit is more than 10 times higher.
Do not use the default customized INKEY mode entry for numbers exceeding 309 digits because the sqrt program will not work. This is because a string variable was input, and conversion to numeric will not work. Even when it worked for numbers below 310 digits, accuracy would have been compromised with only 17 significant digits.
However, besides large numeric input above 309 digits, for everyday data entry I would prefer to use the customized INKEY mode because of its flexibility. I am not sure if the keyboard's function keys F1 to F12, cursor control keys, etc can be used when using C++'s existing input functions say cin.getline() or others. If anybody can do that, please enlighten me and others in this forum. It would be very much appreciated.
I found from a program under construction using the INKEY mode, that it is possible to move from field to field using Up, Dn cursor keys during data entry without pressing the <enter> button, thereby increasing flexibility and perhaps speed during data entry. It is also more user-friendly. You can practically use any key on the keyboard without pressing the <enter> button.
Regards,
Dear All,
Using my PC, a Pentium 4, 2.4GHz, 1.5GB Ram, to run the sqrt program, the maximum number of digits (all 9s) which can be entered into the keyboard is 4095, (perhaps due to keyboard buffer problem?), and the maximum number of digits (all 9s) beyond which all algorithms would fail is 617, (not 4900 even though C++ textbook long double's maximum value is supposed to more than 4900). Does anybody know why there is such a great discrepancy?
The sqrt program's cin input has error trapping incorporated as shown below:
// coutesy of http://prime357.net/node/83
while (!(cin >> weight) || cin.peek() != '\n') { // checking against cin fail state
cout << "\nMust enter a number: " << endl;
cin.clear(); // reset error state back to false
while (cin.get() != '\n') // clear out non newline characters
continue;
}Non-numeric input would not cause any problem like before. Invalid Numeric inputs with more than 1 decimal or included non-numeric characters would be rejected.
A comparison between my customized INKEY versus C++'s cin input may be pertinent here. INKEY pre-empts non-numeric input before <Enter>, whereas cin mode will handle validation after <Enter>.
Which is better, birthcontrol before or abortion after <Enter>? Perhaps, the former is preferable if large numbers exceeding 309 digits are not anticipated, for things like weight, age, etc.
The string to numeric conversion, strtod() has also been changed to atof() as suggested by NathanOliver in a PM to enable Borland compiler, -- which can not handle dynamic arrays -- to compile.
Borland's C++ Builder 6 can compile, but on execution would not be able to handle a 400-digits number. However, both CODE::BLOCK and Dev-C++ performed equally well. Both showed the same results as to the maximum number of digits which could be handled, viz., 617.
Regards,
Hey All,
FINAL REVIEW – ROUND 3
RESULTS
Congratulations to firstPerson and Foamgum for their tip top-performance Square root algorithms basing on the latest improved honest-to-goodness sqrt comparison program.
The final placings for sqrt algorithms' performance test are truthfully as follows:
1.First placing: firstPerson better Newton2 and C++'s sqrt()
2.Third placing: Foamgum's sqrt algorithm.
The rest of the placings remain relatively unchanged.
firstPerson a student from Nepal, studying in the US is a living proof of what Thomas Alva Edison said, “Genius is one percent inspiration and ninety percent perspiration”.
firstPerson had put in the greatest effort in creating the best square root algorithm among all others posted by participants in this forum, improving by leaps and bounds with each new improved algorithm. firstPerson's algorithm is on par with C++'s sqrt() and could be the world's highest performance square root algorithm where source codes are accessible, under Windows OS. Please correct me if I am wrong.
Foamgum, a professional from Brisbane Australia had been using his square root algorithms in his surveying and engineering work before square root functions were available to him, in fact before there were Personal Computers.
The complete source codes of the sqrt program used for the comparison of square root algorithms posted in this thread since 2 years ago are shown below.
MANIPULATION OF PRECISION OF C++'s SQRT()
The above results are honest-to-goodness, impartial and transparent.
It was inadvertently discovered that the precision of C++'s sqrt() could be reduced to produce infinity for numbers exceeding 309 digits, whereas homemade sqrt algorithms were not affected. This could be done by using the following statements
using std::cout;
using std::endl;
using std::cin;
using std::string;
using std::ofstream;
using std::ios;
(remarked out in the codes), instead of “using namespace std;”. C++'s sqrt() can handle up to 617 digits if “using namespace std;” was used.
So, if we could manipulate the precision of C++ sqrt(), we could manipulate truth. The reason this accidental finding had been withheld for more than a week was to encourage feed-backs, which might unravel other problems – which I might not have been aware of – with my first C++ program codes posted in a C++ forum. Some of you might be guessing like the way I have been guessing a 7 letter word beginning with a vowel posted by Narue in response to my earlier posting more than a week ago. It took me a while to figure out that that word begins with 'a' and ends with 'e', to which the Queen of England would probably say “horribilis”, since to be called one is to have your soul ripped apart and shat on. Nevertheless, let bygones be bygones, and let's move on.
COMPILERS' PERFORMANCE IN COMPUTATION OF SQUARE ROOTS
We may arrive at wrong conclusions if we rely on the results of limited choice of compilers, which might not have detected differences in performance and might not have done justice to the high-performance algorithms posted in this forum.
firstPerson's algorithm showed the same result as C++'s sqrt() with 617 digits (all 9s). All algorithms including these top two showed infinity using both CODE::BLOCK and Dev-C++ compiled sqrt program when numbers exceeding 618 digits were entered. Foamgum's algorithm started to show deviation from these 2 algorithms when numbers exceeding 602 digits were entered. It showed infinity at 611 digits.
All other compilers failed to detect differences in performance among the top performance algorithms.
Visual C++ 2008 Express Edition compiled sqrt program showed infinity when numbers exceeding 309 digits were entered. Microsoft C++ deems long double and double ranges to be the same, which should not be the case. See http://msdn.microsoft.com/en-us/library/s3f49ktz%28VS.80%29.aspx
Borland 5.02-compiled sqrt program showed infinity when numbers exceeding 39 digits were entered.
Borland C++ Builder 6.0 compiled program showed infinity when numbers exceeding 18 digits were entered.
The results may be summarized as follows:
The number of digits CODE::BLOCK and Dev-C++ compiled sqrt programs' sqrt algorithms could handle were as follows:
firstPerson's algorithm..........617 digits
C++ sqrt()..........................617 digits
Foamgum's algorithm...........602 digits
Visual C++ 2008 Express Edition, Borland 5.02 and Borland C++ Builder 6.0 all did not detect differences in high performance algorithms because they showed infinity for all algorithms at 309, 40, and 19 digits respectively.
SQRT PROGRAM
The latest sqrt program can save in the hard disk a string of numbers entered using customized INKEY mode in a file viz., sqrtkeys.txt. In 24 hours, the sqrt program's customized INKEY input mode could handle 3,029,574 characters (all 9s) in 24 hours, 24 minutes using a Pentium4, 2.4Ghz PC.
CIN versus INKEY MODE
By extrapolation, in one year a one GB file (1 billion digits) could be created. On the other hand, using the C++'s cin input mode, the maximum characters which could be entered ranged from 510 to 4095*, after which the keyboard would not accept anymore key presses.
...............................NO OF DIGITS (9s)
COMPILERS..............cin INPUT.......CUSTOMIZED INKEY
CODE::BLOCK............. 4095.............2,980,480 in 23:45hr
Dev-C++.....................4095.............3,029,574 in 24:24hr
VC++ 2008 Exp.Ed.......4095................319,290 in 02:35hr.
Express Edition
Borland 5.02...................510..............Not tested
Borland C++Builder6.0....510..............Not tested
However, because string rather than numeric variables were used when using the INKEY mode, the limitation of C++'s string-to-numeric-variable-conversion functions, viz, sstream, atof() and strtod() – which could convert up to only 17 significant figures, the rest being garbage or zeroes – meant that C++'s cin input mode using numeric variables had to be used for computation of square roots.
COMPILERS TESTED AND COMPILING PROCEDURES
The sqrt program can now be compiled with the following compilers:
SEQ.....SIZE....dll&others..COMPILERS
1.........520K.....................CODE::BLOCK 8.02, Feb2008
2.........507K.....................Dev-C++ Version 4.9.9.2, dl Aug2009
3....... .100K.....................Borland C++ 5.02, 1997(#include<math.h>)
4...........42K....1984K........Borland C++ Builder 6.0, 2002.
5...........65K....Unknown....Microsoft Visual C++ 2008 Express Ed.*
{* building/compiling steps:
a) File->Project From Existing code
b) What type of project [Visual C++] -> Next
c) Enter project file location : {here i create a new
folder where the *.cpp file is stored.}
Enter Project Name: sqrt
d) Check add files ->Next
e) Project type->Console application project
->Next->Net->Finish
f) Build Solution F7
g) Start without Debugging Ctrl+F5.}
CODE::BLOCK, Dev-C++ and Borland 5.02 compiled programs are stand alone executables.
Borland C++ Builder 6.0 is not a stand alone executable. It will warn you that it requires 2 dll files, stlp45.dll and cc3260.dll to run.
VC++ 2008 Express Edition compiler was the least user-friendly and most difficult one to download and use. See instructions a) to g) above. It also gave more warnings than the rest of the compilers. Compiled program is not a stand alone executable. You get a message “This application has failed to start because the application configuration is incorrect....” without any warning as to what are missing, if some essential files are not present.
If you are new to VC++ 2008 Express Edition, what do you do? You have to download a vcsetup.exe. See http://www.microsoft.com/express/download/ And then run this file which will take some time to download the compiler along with other files, like SQL Server, as a package whether you need them or not. After compiling, you have to look for the executable program in some debug subfolder.
VC++ 6.0, 1998 was even worse, giving out error messages and failed to compile sqrt, and since it was the only compiler giving problem and being the odd one out, I tend to believe that there was no problem with that line in the sqrt codes reproduced below. VC++ 6.0 reported :
'operator <<' is ambiguous in the following line:
else { cout << "\nCurrent No. of digits: " << getDeg(num) << endl; }As a result, VC++ 6.0 had to be excluded from the test.
Regards,
// sqrt.CPP InputCtrl & sqrt YBM 6 Oct 2009
#include <windows.h> // WinApi header
#include <iostream>
#include <string>
#include <conio.h>
#include <stdlib.h>
#include <iomanip>
#include <stdio.h>
#include <limits>
//#include <math.h>
#include <cmath>
#include<fstream>
#define maxloop 5
using namespace std;
/*
using std::cout;
using std::endl;
using std::cin;
using std::string;
using std::ofstream;
using std::ios;
*/
ofstream out("sqrtkeys.txt", ios::out);
string spaz(int&,int,string&);
string datainp(string,int);
int escx=0;
int curs=0;
int extended=0;
string concate = "";
typedef long double Ldouble; //Change to the highest compound data_type you have
typedef unsigned __int64 uInt64; //Change to the highes data_type range you have
Ldouble weight=0;
Ldouble num=0;
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 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;
if (RaisedTo(sqrt, nthRoot) == number)
return sqrt;
for ( double i = sqrt; i <= (temp + 1); i += plusplus){
if (RaisedTo(i, nthRoot) > number) {
sqrt = i - plusplus;
digits++;
// cout << sqrt << "\n"; // added this so i could see the process
break;
}
}
}
}
double RaisedTo(double base, int power) {
double temp = base;
for (int i = 1; i < power; i++) {
base *= temp;
}
return base;
}
uInt64 getDeg(Ldouble Num)
{
uInt64 deg = 1;
uInt64 T = uInt64(Num);
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Ldouble guess(Ldouble num, Ldouble itr = 10)
{
Ldouble deg = Ldouble(getDeg(num));
Ldouble i = Ldouble( num * 0.35 );
Ldouble sub = deg/(deg*1.5);
while( i*i > num)
i *= sub;
if(deg < 10) sub = 1.1;
else if(deg < 20) sub = 1.25;
else sub = 1.5;
for(; i < num; i*=sub)
{
if(i * i == num) return (i);
else if(i*i > num) return (i-sub);
}
return (i-sub);
}
Ldouble NewtonSqrt2(Ldouble Num)
{
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision)
{
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
if(root == Num) return root;
}
return root;
}
typedef unsigned long Uint64;
long getDeg(double Num) {
long deg = 1;
double T = Num;
while(Num > 9) { Num *=0.1; deg++; }
return deg;
}
Uint64 guess(double num, int itr = 10) {
int deg = getDeg(num);
Uint64 i = Uint64( num * 0.35 );
while( i*i > num) i -= deg;
for(; i < num; i++) {
if(i * i == num) return (i);
else if(i*i > num) return (i-1);
}
return (i-1);
}
Ldouble fpSqrt(Ldouble Num) {
Ldouble deg = Ldouble(getDeg(Num));
Ldouble itr = deg + 10;
Ldouble initGuess = (guess(Num,itr));
Ldouble Precision = 15;
Ldouble root = 0.0;
for( Precision; Precision; --Precision) {
root = initGuess - (initGuess*initGuess - Num)/ (2.0 * initGuess);
initGuess = root;
}
return root;
}
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 = 136;
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;
}
long double MySQRT(long double number, int *iterations) { // Foamgum's Spirit MySQRT
long double bfg, cfg, 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;
bfg = (1.0 + number)/2; // First estimate of square root of number.
cfg = (bfg - number/bfg)/2; // Correction to give a better estimate.
while(cfg > e && (*iterations) < 1000) {
f = bfg; // For very small and very large values we will see
bfg -= cfg; // if the correction has any effect.
if(f == bfg) // Applying the correction made no difference to our answer.
return bfg;
cfg = (bfg - number/bfg)/2; // A revised correction.
++(*iterations); // A counter to measure the effectiveness of our algorithm.
}
return bfg;
}
int xcz=0;
int decf=0;
int ctr =0;
int cc=0;
int brk=0;
int len=0;
std::string xcon;
char inpg;
string* 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;
int cinmode=0;
char efld[maxloop][25] = {" "," ","Enter a number : "," "," "};
//double e=2.7182818283;
int main() {
num=0;
double heyyou,whome;
brk=0;
system ("color 0a");
redo:
do {
if (cinmode==0) {
system ("CLS");
cout << "\n Esc:Exit F12:cin>> mode FINDING THE SQUAREROOT OF A NUMBER ";
cout << "\n Only numbers and 1 dec. allowed, ";
sweight=datainp(efld[condi],condi);
len=sweight.length();
}
if (cinmode==12) {
system ("CLS");
cout << "\n cin mode ON FINDING THE SQUAREROOT OF A NUMBER ";
cout << "\nEnter a number: " << endl;
// coutesy of http://prime357.net/node/83
while (!(cin >> weight) || cin.peek() != '\n') { // checking against cin fail state
cout << "\nMust enter a number: " << endl;
cin.clear(); // reset error state back to false
while (cin.get() != '\n') // clear out non newline characters
continue;
}
}
if (brk==1) {break;}
num=weight;
if (num >0) {
if (cinmode==0){
cout << "\n\nCurrent No. of digits: " << len << endl;
}
else { cout << "\nCurrent No. of digits: " << getDeg(num) << endl; }
whome=num;
//cout << "\nN:"<<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\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;
float fnum;
fnum=float(num);
x = invsqrt(fnum);
cout << "\n\t7. (invisal) Inv.SquareRoot, hex const.0x5f3759df.Ans.: " << x;
long double afg, bfg; // Foamgum
int count(0);
afg = num;
bfg = MySQRT(afg, &count);
cout << "\n\t8. (Foamgum) Spirit MySQRT Ans.: " << bfg;
Ldouble fpP;
fpP = Ldouble(num);
cout << "\n\t10.(firstperson Better Newton Sqrt(New27Sep2009) Ans.: " << NewtonSqrt2(fpP);
Ldouble P = Ldouble(num);
if (P <= 12345678901234567899.999) { //Any bigger, I get compiler error
// cout.precision(40);
cout << "\n\t12.(firstperson)'s Mines2 sqrt Ans.: " << fpSqrt(P);
}
else {cout << "\n\t12.(firstPerson)'s Mines2 sqrt skipped ";}
if (num <= 12345678901.0) {
cout << "\n\t13.(NathanOliver) nth root Ans.: "<< NthRoot(num, 2);
}
else {cout << "\n\t13.(NathanOliver) nth root skipped "; }
}
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 YBM144
string datainp(string efield,int condi) {
int c;
redo2:
extended=0;
curs=0;
decf=0;
cout << efld[condi-1] << endl;
cout << concate;
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;
if (c == 0x00 || c == 0XE0 || c==224 || c==0) {
extended = getch();
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;
out << inp;
}
if (c==46 && decf==0) { ++decf;}
}
else { concate=spaz(condi,c,concate);if (cinmode==12) {c=13;}}
}
} while (c != 13); // ascii 13 is <enter> or <carriage return>
out.close();
if (cinmode==12) {return concate;}
if (c !=27) {
len = concate.length();
if (condi==3) {
weight = atof(concate.c_str());
}
}
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 (xcz==134) {
extended=0;
cinmode=12;
}
// 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 EndHey all,
I would like to share with you all, especially those new to C++ some of my recent findings as follows:.
IDE and minGW compilers
CODE::BLOCK ver.8.02 and Dev-C++ ver. 4.9.9.2 are IDEs, Integrated Development Environment. They both use minGW compilers, and that is probably why the results they produced in the sqrt program are the same.
minGW (Minimalist GNU for Windows), formerly mingw32, is a native software port of the GNU Compiler Collection (GCC) to Microsoft Windows, along with a set of freely distributable import libraries and header files for the Windows API. minGW allows developers to create native Microsoft Windows applications.
The term "minimalist" is often applied colloquially to designate anything which is spare or stripped to its essentials. it has been used to describe plays and novels. It has also been used in visual art and music where the work is stripped down to its most fundamental features.
The GNU Project was launched in 1984 to develop a complete Unix-like operating system which is free software: the GNU system. The name “GNU” is a recursive acronym for “GNU's Not Unix!”; “Free software” is a matter of liberty, not price. To understand the concept, you should think of “free” as in “free speech”, not as in “free beer”.
Free software is a matter of the users' freedom to run, copy, distribute, study, change and improve the software.
minGW was originally called mingw32; the numbers were dropped in order to avoid the implication that it would be limited to 32-bit systems.
regards,
references:
http://en.wikipedia.org/wiki/MinGW
http://www.gnu.org/
// hope this can help u guys....
#include <iostream.h>
#include<conio.h>
double sqroot(double n)
{
double estimate;
double newEstimate;
newEstimate = n-1;
estimate = n;//estimate can be made closer to expected value but the number to square will also work just needs to run a few more times
for(int i =0;estimate != newEstimate && i !=20;i++)
{ // i is only to stop cycling due to calculation errors in using doubles
estimate = newEstimate;
newEstimate = estimate- (estimate*estimate - n)/(2*estimate);
}
return newEstimate;
}
int main()
{
double temp;
clrscr();
cout<<"Please enter no. to sqaure";
cin>>temp;
temp = sqroot(temp);
cout<<temp;
return 0;
}the root is up to tenth place w/out using sqrt
float sqroot(int x)
{
a=1; /*integer x & nearest assumption integer factor a*/
while(a*a<=x)
{
a++;
}
a--;
if(a*a==x)
{
return a;
}
else
{
sqqrrt = ((x/a) + a) / 2.0;
return sqqrt;
}it is not just merely *magic
it is only for integer output values only like 4,9,16,25............it is my own program
c++
void main()
{
int i,j,n,l;
cout<<"enter the value of n";
cin>>n;
for(i=1;i<=n/2;i++)
{
for(j=1;j<=i;j++)
{
l=i*j;
}
if(l==n)
{
cout<<i;
break;
}
}
getch();
}
not working !
Seems to me I remember that you can estimate the square root by subtracting consecutive odd integers and counting the number of subtractions until you get to zero or less. If less than zero extrapolate to get the final answer.
Shhhhhh, don't wake the necrothread.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.