Author Topic: Old School Algorithm for Calculating Square Root  (Read 1277 times)

0 Members and 1 Guest are viewing this topic.

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Re: Old School Algorithm for Calculating Square Root
« Reply #15 on: February 06, 2018, 11:36:39 pm »
That's Abstract Algebra, Holden.  Yep, in fact, that is exactly what they meant by "Modern Algebra".  It was condemned as "New Math".

I am very interested in that kind of thing.  It's as though, if you wanted, you might invent your own field ...

I am going to upload another text version I completed before moving on to the next stage, where I alter the output.

I really like it the way it is, and I suppose I will have to give each version special names.

This version I really like even as I am doing the problems by hand.  The way I have the output for different sections of the code gives me a great feeling when the form stands out, when the subtrahends all add up to nearly the original number.

Have you pasted any of this and run it online?

Do you still have that Mac?  I'm sure, since it is Unix, it would have a GNU g++ compiler or could easily be installed via some kind of internal software manager of the OS.

You would rename the file to Sqrt_work.cpp, then

g++ -g Sqrt.cpp -o Sqrt

Then, to run, from that directory:  ./Sqrt 7720.17 4

If you place Sqrt in your path, you can just type the command and arguments.

Eventually, if I ever think others might be interested in using this to teach themselves or others, I could make the version request the needed input rather than being command line driven.

Myself, I prefer typing the command with the parameters.  If I were to leave it around for someone to inspect or explore, perhaps it would be better if the program took the initiative and requested the input, explaining to the user what it will do.

Quote
if a@b=a+b/2, a#b=a^2-b^2, (a!b)=a-b/2

Given this info,I found out what (4#3)@(2!3) would be.I sort of liked it.

Hmmm.  Yes, that is a cool problem, very much like what they wanted to teach just before or when I was born into this realm. I also like such problems since they are novel, and, well, to put it plainly, WEIRD.

Let's see.  Since a#b = a^2-b^2, 4#3 = 16 - 9 = 7
Since (a!b)=a-b/2, 2!3 = 2 - 3/2 = 4/2 - 3/2 = 1/2
Since a@b=a+b/2, (4#3)@(2!3) = 7@(1/2) = 7 + 1/4 = 7.25

Is this the result you came up with.  I am sleepy so my brain might be fried.

That's kind of similar to the composite functions you were looking at a few days ago.

Oh well, I am actually getting sleepy earlier than usual tonight, so I'm going to see if I can step away from the machines and leave my math books alone for a second.

Believe it or not, I just pulled a book on Abstract Algebra off the shelf and was going to read a couple pages in the intro before switching gears and reading a few pages of philosophy before hopefully dozing off.
« Last Edit: February 20, 2018, 04:43:07 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Holden

  • { ∅, { ∅ } }
  • Posts: 5070
  • Hentrichian Philosophical Pessimist
Re: Old School Algorithm for Calculating Square Root
« Reply #16 on: February 07, 2018, 04:58:46 am »
God bless you Herr Hentrich,my true friend.
La Tristesse Durera Toujours                                  (The Sadness Lasts Forever ...)
-van Gogh.

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Square Root Algorithm Program Will Teach You
« Reply #17 on: February 10, 2018, 01:28:20 am »
You can compile this.

You won't be able to see what it does just by looking at the code.

It is 763 lines of code, and I still want to add another part.

But this is complete.

Now it is just a matter of tweaking different versions to suit different tastes ...
and to throw it different data.

Still, I would like to move on ... but when I wake up in the morning, I always seem to be like, "Oh my god, I can't believe I did that."

« Last Edit: February 20, 2018, 04:43:20 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
An Open Letter to My Nephew
« Reply #18 on: February 10, 2018, 08:06:00 pm »
I am storing this email I sent to my nephew because I intend to read it to help me do something "tricky" in Windows.

I am going to use Visual Studio Code to see if I can get what compiled flawlessly in Arch Linux to compile in "Microsoft" -- only because i wish to be able to give someone this code to use who may only have Windows on their computer, like my sister or even Senor Raul de Paraguay.

--------------------------------------------------------------------------------------------------------------

I fixed the problem where 205.25 was showing up in the string as 2 5 . 25

I wanted it to be 2 05 . 25 according to how the algorithm works when we do it by hand.

I had to make it store as 0 and number.

Then it came up as 02 05 . 25 which is still not perfect, since when there is an odd number of numbers before the decimal point, the first number is isolated.

So I had to remove that first zero.  Now it is stored as 2 25 .25, which is what I need.

This is just one function:

void create_input_string()  {

          // List elements of tokens deque
          std::cout << "\nThe contents of tokens are: ";
          for (std::deque<double>::iterator i = tokens.begin(); i != tokens.end();++i)
          {
                 std::cout << ' ' << *i;
           }
           std::cout << std::endl;

          // Store in string for easy printing
           std::ostringstream convert;
           int count = 0;
           for (std::deque<double>::iterator i = tokens.begin(); i != tokens.end();++i)
           {
             convert << *i;  // sends double into stream
             if (count == point_location)  input_str += ".";
             if (std::stod(convert.str()) < acceptedDiff)  input_str += "00 ";
             else {
               if (std::stod(convert.str()) < 10)  {
                 input_str += '0' + convert.str() + " ";
               }
               else input_str += convert.str() + " ";
           }
             pairs[count] = std::stod(convert.str());
             convert.str("");
             convert.clear();
             count +=1;
          }

}

The problem I am running into with Windows is that it does not recognize std:stod which converts a string to a double.

With that version, I may use streamstring.  It seems like overkill, but this is what it takes to deal with this situation.

I got the idea while coding an alternate version (aimed at "Windows users," that is, our Moms) which will prompt the user for the number to find square root of and number of digits.

In C++ , when taking input with std::cin >>, it reads what it is told to read, such as a string, char, float, int, or whatever, but it leaves the "newline \n" in the stream, so the next call to it takes that and causes unpredictable behavior.

So I am using streamstring from <sstring> not to be confused with <istream> for istreamstring, <ostream> for ostreamstring like in above code.  Both of these are in <iosream>?

The question mark is intentional.  We always have to be humble enough to ALWAYS be learning for we can not know all we need to know in order to do anything, right?  We start a "project" knowing we will have to research every step of the way.

I am thinking of combining ostreamstring and stringstream (in Windows Version) to pull of the part that is working (in Windows only) due to it not recognizing c++11's std::stod.

Here an example of using getline with stringstream instead of just using cin >>.

 double real_n = 0.0;
  int d;
  std::string line = "";
  std::stringstream stream;

 std::cout << "\nAn Old School Square Root Algorithm Teacher\n\n"
           << "We wish to find the largest n-digit number whose square\n"
           << "is _____________.\n\n";
         
while (true) {
    std::cout << "Please enter any positive rational number you wish.\n"
       << "It may contain an integer part and a fractional part.\n"
       << "Enter in decimal format: ";
         
 std::getline(std::cin, line);
 stream << line;
 if (stream >> real_n)
     break;
 std::cout << "Invalid number.  Please try again." << "\n";
}


 std::cout << "\n\nHow many digits of the square root of "
           << real_n << "to extract?\n3 or 4 works best, but we can handle more\n";
 while(true) {
     std::cout << "\nEnter number of digits: ";
     std::getline(std::cin, line);
     stream << line;
     if (stream >> d)
         break;
    std::cout << "Invalid number.  Please try again." << "\n";
 }

So, I am thinking of first feeding the ostream (convert [which is a string]) into a streamstring, like:

convert << *i;  // double (number with integer and fractional part, a float) as a double

stream << convert.str()     // sends a string into stream

stream >> pairs[count];

You see, pairs holds "doubles".  I am thinking this should work since in the "prompt for user input" line is a string which goes into the stream and the stream send it to input_r or d as a double or an int.  It knows what to do with the data and how to store it in memory.  This would accomplish what std::stod does.

It is not possible to just store the numbers from the deque, tokens, directly into the pairs[] array.

This is why I have pairs[] array, tokens deque, input_double, input_long, and input_str.

These are all the "same" number, but input_str is how I print it in the beginning which shows a student/user how to write it down to set up the work.  pairs[] is to have access to these real numbers when displaying the work in each step, actually, this is how I "bring down the next pair of numbers" after each subtraction.

This is the remainder = remainder * 100

and then the remainder = remainder + num, where "num" is the next pair of numbers being brought down.

The there is the connection between input_long and input_double.

Input_double is the actual number we are working with.

But we have to transform this into an integer, input_long before storing pairs into the tokens deque, which is like a vector of doubles.

Wow.   THEN, just do DO THE MATH and keep the results on point, I have to keep track of how many times I multiplied input_double to make input_long (an integer with no decimals).

I had to create decimal_places[] array of ints to represent the decimal places.

Each pair is linked to a power of 10 ... 10^(4), 10^(2), 10^(0), 10(-2), 10^(-4) ... etc

That's 10000, 100, 1, 0.01, 0.0001 ... etc

decimal_place[0] is the greates, and the last element in the array is the smallest power of 10.

When decimal_place == 10^(-2), I let decimal_point = i.

Holy ****, there is alot to this!

Sorry to type this up in an email, but now I am going to store this mail as some kind of documentation.

Peace brother.

- Uncle Mike
« Last Edit: February 10, 2018, 08:29:28 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
It worked in Windows this way without using std::stod
« Reply #19 on: February 10, 2018, 08:22:25 pm »
void create_input_string()  {

          // List elements of tokens deque
          std::cout << "\nThe contents of tokens are: ";
          for (std::deque<double>::iterator i = tokens.begin(); i != tokens.end();++i)
          {
                 std::cout << ' ' << *i;
           }
           std::cout << std::endl;

          // Store in string for easy printing
           std::ostringstream convert;  // takes in pairs of double from tokens
           int count = 0;
           std::stringstream stream;  // stream << convert.str()
                                      // stream >> pairs[count]
           for (std::deque<double>::iterator i = tokens.begin(); i != tokens.end();++i)
           {
             convert << *i;
             if (count == point_location)  input_str += ".";
             stream << convert.str();
             stream >> pairs[count];
             if (pairs[count] < acceptedDiff)  input_str += "00 ";
             else input_str += convert.str() + " ";
             convert.str("");
             convert.clear();
             stream.str("");
             stream.clear();
             count +=1;
          }
    /*      if (tokens.size() < (digits) )   {
            input_str.erase(input_str.find_last_not_of(' ')+1);
            input_str += "0";
          }
*/
            std::cout << "\nThe pairs array:\n";
            for (int i = 0; i < tokens.size(); i++)  {
              std::cout << "pairs[" << i << "] = "
                  << square_root::fix(pairs, 2) << "\n";
            }

          std::cout << "\n\nThe length of string is " << input_str.length() << "\n";
          input_str.erase(input_str.find_last_not_of(' ')+1);  // trims last " "

          std::cout << "input_str.erase(input_str.find_last_not_of(' ')+1);\n";
          std::cout << "The length of string is " << input_str.length();
          std::cout << "\n\nThe Input String is: " << input_str << "\n"
               << "----------------------------------------------------\n";
   }


Also, a great amount of the output was not appearing when running in the console (only in Windows, the Linux version was fine ... that's where I did all the coding and debugging), but by adding std::flush to the end of many of the stdout lines, this solved the problem.

Now I have a SquareRootAlgorithm.exe that runs in Windows, prompts user for input, and pauses at appropriate junctures ... all complete before the wicked midnight hour into 211.   8)
« Last Edit: February 11, 2018, 12:52:57 am by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Re: Old School Algorithm for Calculating Square Root
« Reply #20 on: February 11, 2018, 08:40:37 pm »
This is a cross-platform version that compiles with g++ in both Linux and Windows without the -std=c++11 flag.  In other words, I put together some brute force functions to do some dirty work that do not rely on things like std::stod, which transforms a string to an double.

Also, this version takes input from the user rather than relying on arguments being passed on the command line.

I thought this would be safer for posterity were someone to stumble upon the program and not know what the F it does.

They just have to call it by name or click on it (after compiled) and it will ask for the two required parameters.

I call it wsra, the w so I remembered it was the version aimed at Windows, and then it ended up being the version with "prompting user for input" in Linux as well.

One little aesthetic difference about this "safer" version is that I use the pipe | instead of the [ALT+251], square root symbol.

That was a long birthing process with code over 800 lines.

I think it is rather elegant.
« Last Edit: February 20, 2018, 04:43:37 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Re: Old School Algorithm for Calculating Square Root
« Reply #21 on: February 20, 2018, 04:46:52 pm »
I apologize if I have been preoccupied.

I have decided that, even if compiling and running the code I wrote may not sound very enticing, I can at least show the out put.

You give me a number, and I will runn it on the command line with my program and upload the generated output in a text file.

Here is the code for the prompt version along with output from the command line version (for the number 753),

« Last Edit: February 21, 2018, 07:48:59 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Re: Old School Algorithm for Calculating Square Root
« Reply #22 on: February 21, 2018, 07:50:22 pm »
It's done.

Exhausting but fulfilling.

I learned a great deal while working on it.


UPDATED:  25 February 2018

« Last Edit: April 30, 2018, 05:30:04 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
sra_.cpp Line 676 of 1884
« Reply #23 on: April 30, 2018, 05:35:49 pm »
Somehow I had compiled a file which was ever so slightly different than one which I printed (over 30 pages).  In the first phase, there is a line with a statement where we look to find b such that b times (such and such + b) <= remainder.   In this first, when displaying to the user, I need to add the next pair of numbers to be brought down, as in  remainders[0]*100+pairs[1]*decimal_places[1]

Somehow, all the versions I had saved, uploaded, compiled, zipped, etc, were a version that did not include this minor adjustment.

I will upload the version here so I don't go crazy looking for it again.

I will name the post something obvious so I can find it.

« Last Edit: May 07, 2018, 03:56:17 pm by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
sra_.cpp Line 676 of 1884
« Reply #24 on: May 03, 2018, 06:48:24 am »
This was one of those little errors that one must be a perfectionist to be concerned about.

Each part must be considered important, for if one were using this program in a distant future (and, in terms of computing technology, the distant future is merely a few decades away), if one were seriously tryinh to follow along (and not merely looking for the end result), then this is an important step.

My note to self is not simply about having corrected this error a couple months after completion, but to remind myself of how mysteriously this one slipped by me.  It had more to do with having too many copies of the same titled program since the version I printed DID have this correction; whereas the version that ended up getting compiled and stored in my ~/bin folder (and compressed into tar.gz and .zip folders) did not have the correction.

The reason why an error such as this may have been difficult to detect (that I had saved the wrong version) is because in the series of "cases" in the "switch structure", the form this result takes is unique only in the first case.  In the remaining cases, the result displayed to the user at this stage is stored in an array named remainders[count], where count is an iterator one less than the case number (since iterations begin with zero rather than 1).

In the first remainder,  remainders[0], the number being displayed must be transformed to include the next pair of digits being brought down ffrom the number we are extracting the square root from, hence  remainders[0]*100+pairs[1]*decimal_places[1].  That is, we multiply remainders[0] by 100 to give its relative position, then add the next pair, pairs[1] (times its decimal value).

I understand that posts such as this are notes to myself which require no comments from others.
If someone were to actually compile the code with

g++ -g sra_.cpp -std=c++11 -o wsra

and one were to follow along with interest, then such an individual may be inclined to respond to a post such as this; but I do not expect this to be the case.  Nay, perhaps I do not even desire this.  I certaily do not require or need anyone other than myself to take interest in a post such as this.

 :P
« Last Edit: May 03, 2018, 07:00:43 am by Non Serviam »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
OK.

After a couple months of not looking at this code, fearful of breaking it I suppose, I rolled up my sleeves working until 3AM on it (after throwing some dirt into the garden just before nightfall (for balance)), and this morning I made some small but significant adjustments which I will not document here, preferring to express as much as I can of these technical matters in my private "diary" which used contain "philosophical notes" ... and now gathers mostly notes about math or programming.

I've become a reclusive math/computer geek, and i like it this way.   8)

I sure don't miss hiding my coffee under my nut-sack in the county jail to protect it from my thieving cell-mate and his shiit-eating-grin sportin' card-flippin' cronies.   ;D

Anyway, i deleted the previous version and will attach the command line version (sra-cl.cpp, the version which prompts for input (sra2_.cpp), and a couple output files generated with:

sra-cl 24336 4 >> sra_24336_4.txt
sra-cl 2 5 >> sra_2_5.txt

To compile with GNU g++ (version > 6.3):

g++ -g sra3_.cpp -o sra
g++ -g sra-cl.cpp -o sra-cl

If < g++ 6.3, add the flag:  -std=c++11 or -std=gnu++11

as in:  g++ -g sra3_.cpp -std=gnu++11 -o sra

This version rejects numbers < 0.01 but handles many, many cases with grace.
It is not GUI or "user-friendly" but meant to last several decades as it is a console program that can be compiled cross-platform and depends on no fancy graphics or libraries.

It is meant for someone to go through with paper, pencil, and maybe even a calculator for the challenging arithmetic.
There are many videos out there on ZooTube for those interested in doing this by hand, using little "tricks" for the arithmetic; but my code displays the extraction of each digit by digit in systematic detail.

I have tested many cases, even those with begin with 0, such as 0.05.

I leave the out put for the square root of 2 (up to 5 digits) as well as an easy one, 24336, which is a perfect square (of 156).

I have compiled the source code into versions for Linux 64 bit, Linux 32 bit, Windows 64 bit, and Windows 32 bit.

I have also compressed the files into a zip file and tarball file.  If anyone is ever interested in have the execuatable code and cannot compile themselves, just private message me with your email, and I will send the compressed file.

Sorry, I do not have access to a Mac, and therefore have not compiled a version for that.

Peace.
« Last Edit: February 27, 2021, 10:30:16 pm by Sticks and Stones »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~

Nation of One

  • { }
  • { ∅, { ∅ } }
  • Posts: 4756
  • Life teaches me not to want it.
    • What Now?
Re: Old School Algorithm for Calculating Square Root
« Reply #26 on: January 04, 2020, 09:03:35 am »
2020 : used sra "classic version" to bring to the surface of consciousness the underlying logic behind approximating the square root of an integer by hand (with paper and pencil, in long form - allowing for side calculations) ... I was able to follow the logic even though sleepy and feeling like a tired old chimpanzee, blurry eyed.   I think it does work, and I shed tears of enlightenment/joy  :'( knowing that I was able to create, with brute force and care/obsession, a vessel for the "spirit-thought" of the digit by digit square root algorithm, thereby harmonizing an incongruity:
{
Rather than the Computer being used to handle the calculations and dirty tedious arithmetic, it is being coded to display [forces understanding of] the algebraic forms of the Devil Itself ---> the details of the thought processes, the bare bones in excrutiating detail ...

But, after a handful of examples, some simple, some comlicated, The One Inner Subbject may absorb these patterns, expressed algebraically, in vivid detail, feeling it, practicing this method spontaneously, away from any computer, scribbling on the back side of receipts, always carrying a pen and little notebook.

Rather than the usual dependence relationship, the code is doing something very special.  It is trying to teach you to make bread rather than simply handing you buttered toast!

sra does restore the "by hand method" in my own memory, and this means it just might work for others.

Like cursive writing, performing these mechanical tasks with pencil and paper may be perceived as an ArtCraft.
To use Code to preserve Thought, instilling a magical kind of reverence for being the receiver of a Lost Art ... I suppose it doesn't get any better than that as far as being satisfied at death.
« Last Edit: January 04, 2020, 09:11:59 am by Tired Lazy Busy Bones »
Things They Will Never Tell YouArthur Schopenhauer has been the most radical and defiant of all troublemakers.

Gorticide @ Nothing that is so, is so DOT edu

~ Tabak und Kaffee Süchtigen ~