Philosophers in Rags :: We dive deeper, and come up muddier.

It's done!

Here's the final version (for now) saved as a text file so as to be able to upload it here.

Remember, you can compile and run at https://www.onlinegdb.com/online_c_compiler by copying and pasting.  Just remember to add the command line arguments; that is, the number to find the square root of and the digits of accuracy desired, such as 753 5

To compile offline on a machine with GNU gcc:

gcc -g digit_by_digit.c -lm -o sra

To run:
./sra 753 5

To store output in a file:

./sra 753 5 >> output_753.txt

Notes: 

/* This part of the documentation from Gerald R. Rising's work with TI-84

Here is the algorithm we wish to program, slightly modified from Rising's
PROGRAM: SCHSQRT

1. Separate the radicand into pairs of digits working left and right from the decimal point. Place a decimal point where your answer will appear above the original decimal point.

2. Find the nearest square less than or equal to the leftmost pair.

3. Write this square beneath the leftmost pair and its square root above it as in the long division algorithm.

4. Subtract your square from the radicand pair as in long division.

5. Bring down the next pair of digits.

6. Multiply your partial answer by 20 and write the product to the left of the result you obtained from steps 4 and 5 (or later from step 9).

7. Divide your result in step 5 (or 9) by your answer in step 6, writing the quotient as the next digit in your answer.

8. Add this digit to your answer in step 6 and then multiply your result by the same digit, placing the product under your answer from step 5.

9. Subtract and continue from step 5 until the number of digits required is reached.
*/

While Gosling's work inspired the engine of the code, what motivated me to extend the program into an "educational experiment" was a section in Modern Algebra: A Logical Approach circa 1964 by Frank Allen.

I still have some tweaks to make to this code, but essentially, it does tackle the form.

I put 1681 in, and by hand I get 41.  So does the code, but its "explanation" is not clear so I have some work to do ... 

By hand, without even using the "old school long-division style" and its "tricks", this problem is straight-forward using the the method based on the formula for the square of a binomial:

1681 >= (10a + b)^2 where a is the tens digit and b is the units digit.

a = 4

1681 >= [(10)(4)]^2 + (2)[(10)(4)](b) + b^2 = 40^2 + 80b + b^2 = 1600 + 80b + b^2

1681 - 1600 = 81 >= 80b + b^2 = b(80 + b)

So we just have to find b such that b(80+b) <= 81

Clearly, b = 1 so sqrt(1681) = 41

The problem with my code, even as it comes up with the correct result for this "shadowy copy" of the form, it comes up with 0 then 9 and rounds up to 1.   It does not see that 1 is a better solution than 0 in the first place.

So it's back to the drawing board.  I will have some "fun" running it through a debugger for this case to see why it is not coming up with 1.  I will take a different approach if I have to.   In the end, it does not matter in the least, but I really would like to pull this off even if just for posterity. 
------------------------------------------------------
NOTE TO SELF:  debugging for 1681
At this stage, y = 80 and M = 81
We have a = 4, so 2(10)(4) = 80.  That's why y is 80. 
M = 81 because 1681 - [10(4)]^2 = 1681 - 40^2 = 1681 - 1600 = 81
All is well.  I place a printf before the  while ((y + T)*T > M) to see why T = 0 instead of 1.   

    T = floor(M/y);   
        printf("T = %d", T);
     while ((y + T)*T > M) 
       {
        T -= 1;               
     }

The printf prints T = 1 which makes sense since floor(81/80) = 1
I have zeroed in on the nasty bug.  For some reason, (y+T)*T > M is passing as true and T is getting reduced to 0.

But (80 + 1) * 1 = 81, and M is 81, so this is false.
y and M are real (double which is float), but T is an integer.
This is a strange bug.

I add more printf statements to debug:

    printf("T = %d", T);
    printf("y + T = %g\n", y + T);
    printf("(y + T)*T = %g\n", (y + T)*T);
    printf("M = %g\n", M);

T = 1
y + T = 81
(y + T)*T = 81
M = 81

WHY IS T BEING REDUCED TO 0???

This is not a logic error on my part.
Research this https://randomascii.wordpress.com/2012/02/11/they-sure-look-equal/

https://randomascii.wordpress.com/2012/01/11/tricks-with-the-floating-point-format/

Solution? 
The correct and safest way is to always look at the relative difference between 2 numbers and not the difference. 

I could change this from

while ((y + T)*T > M)

to
 float acceptedDiff = 0.0000001;
 while (fabsf( M - (y + T)*T  ) > acceptedDiff )
 
This makes result -41
NASTY BUG has to do with how computers deal with "floating point numbers"

[SOLVED?]:   do not use fabs (absolute value)
fabsf( M - (y + T)*T = 1.27898e-13
(y + T)*T - M = 1.27898e-13


Use the comparison:

while ( ( (y+ T)*T - M ) > acceptedDiff )

This works even though it's the same.
I could just change the program to only handle integers, but I want it to handle decimals and decimal points. 

In the meantime, at least writing the code helped me understand the algorithm better.
Try not to become so obsessed that you have a tantrum in public.
Also, take a look at this when you are not driving the mother around:  https://bitbashing.io/comparing-floats.html
-----------------------------------------------------------------
end note to self
----------------------------------------------------------------------------------------
Before I am done with it, the program ought to be able to walk you through doing such a thing by hand.

In fact, I created the code to help me do this by hand, so the last thing I want is for my "brain child" to only add to the confusion.

Something you mention plays a role in the parts of the code I have to "tinker with" next.

It always produces the correct result.  That is not the issue.  At the end of the day, our brains can handle rational numbers in their purest form, that is, as mental constructs in our minds; but these "damn" machines, these wonderfully stupid machines, represent everything in decimal form.   I'll get to the bottom of this "nasty bug" --- meanwhile life is going on around me --- interruptions! (my mother puts me on the phone with some debt consolidation company that wants to "help" her by having her stop paying the interest on the credit cards ... WTF!  I can tell from his voice that he's a schmuzer and I just say, DON'T DO  IT.   I don't have time for that shiit!)

You see, I based my code on dealing with one such form the problem takes, and I built the program to deal with such a number.

Now, even though the code certainly works, when I use a different kind of number the "explanation aspect" of the code, which is its entire purpose, may become less coherent.

I suspect that when I track down a universal kind of form inherent in such a problem, then I will be able to tweak the program in such a way that it will be able to ASSIST YOU in understanding how to do this by hand.

You understand that, here, i am not giving you a problem to figure out, but simply sharing with you what I am tinkering with.  In the process maybe we both will learn the forgotten art of extracting a square root from ANY number by the slow digit by digit process with pencil, paper, and maybe a calculator for the arithmetic involved in each step.

I do not expect you do be able to just pick this up like long division since it has not been taught in many years. 

This is the motivation behind the program.  I want it to be educational, so that it can teach users in the future (who happen upon the program on some survivor flash drive) how to do this BY HAND.

I myself am still in the process of totally wrapping my mind around it.

When I make changes to the code, I will replace this file since we have no more space left on the board for uploading any new files.

Also, I mention the site where you can compile and run this.   I would like you to test out this version just so you can see it in action.  It generates a great deal of output, attempting to explain each step.
 
I am on the verge of some kind of inner breakthrough when it comes to understanding how to connect the systematic "long division style" which one does by hand to the actual method based on the formula for the square of a binomial.

The approach I took in the code to present explanations of whichever shadowy copy the form takes was kind of BRUTE FORCE.

If I can figure out a way to expand the role that the variables B and S play in the algorithm, then I may eliminate the reliance on variables "PHASE" when tweaking the placement of decimal places in each phase.

I would like to rely more on variables B and S whose values are derived right at the start of the program.  B and S reveal much about how the code approaches each shadowy copy of the form in question. 

From documentation:

The second step in the algorithm asks us to find the nearest square less than
that first pair of digits on the left. To facilitate doing this it will be convenient if we shift the digits of N (temporarily) to the right or left two decimal places at a time to give us a new value, M, between 1 and 100, that is with 1 ≤ M < 100.

We will retain the value of N to report at the end  of the program, modifying M as the program progresses.

We will have S representing the number of pairs of digits shifted to make a small number larger and B, the number of pairs of digits shifted to make a big number smaller. We will use these values at the end of the program to readjust the decimal point location in the final square root.

The thing is, my code is most likely different from other incarnations of similar code in that I am attempting to force the program to EXPLAIN each step.

The tricky part is that when working such a problem out using the form of the square of a binomial, we use the actual number with decimal point in place.   In the form by hand, there are "tricks" taking place.

Don't worry too much about understanding the code.   I would be content if only I can get it to the point where it can guide you through many problems and eventually, over many moons, be able to do these with pencil and paper.

Not just you, of course, but anyone who happened to stumble upon it in the distant future, you know, when Taylor finds it on the Planet of the Apes.     That is, if he can find a stick ... trees?   or a stone ... or even some sand ...  ugh ...

I will name this version 1.0

In 2.0 I want to make use of B and S.  For each time we shift the decimal point 2 places to the left, this is division by 100.  hence, throughout the code, I would adjust the square by multiplying the "square root being extracted" by 10 for each division by 100 (for each B) or dividing the "square root being extracted" by 10 for each multiplication by 100 (for each S), which is when we move the point to the right, making a smaller number larger.

The thing I like about using a method with just the mathematics based on the formula for the square of a binomial is that it does not involve any shifts or adjustments.  These come into play only because I am trying to display the "living process" of how one might go about doing this by hand on paper with pencil, or on sand with a stick for that matter.

Trust me, the program is about transmitting understanding the form.

I believe it will be helpful when it is finally complete.

When I am confident it will not confuse you, I will send a list of numbers for you to do by hand. 

It will not be today or tomorrow, but it won't be too far in the future.

After that, it would be more of a matter of bothering to understand.

It is not so very easy, which is why they devised TABLES OF VALUES before calculators.

Do not become discouraged if it seems mysterious.

My goal is to  help myself develop the ability to do this by hand.

You are welcome to also learn it if the Spirit moves you.

It is a totally useless craft, but I am determined not only to understand it, but to build a program that will teach it to others using any number to pick from the top of their heads.

The output can be generated into a text file and then studied for any number, any shadowy copy of the form ...

As I said, this program works, but I am considering how I might go about displaying the process to the "user", the "subject", the "student" [we are all students], using variables B and S rather than by brute force (counting the phases).

The code in this 1.0 is somewhat static, and I want to make 2.0 more dynamic.

The bottom line is that I am sharing those notes and this code with you so that you can witness the process unfold.  If you run the code online you will at least see the method in my madness and have an idea of what it is I am attempting to do.

Meanwhile, those who need to make money are building websites for merchants to sell products.  Cha-ching, cha-ching.

(an aside: my nephew just might be able to get out of Columbia, paying fines and air fair by selling such a website with lifetime maintenance as part of the agreement).

For whatever reasons I am at liberty to become engrossed in useless work for the sheer enjoyment of finding beauty in the mundane, or, if you like, extracting intelligence to reveal underlying forms --- and then harnessing this obsessive energy by engaging in a labor of love in an attempt to transmit this intelligence into other brains.

It is my wish that your brain might be a receiver of this intelligence. 

I will work out the quirks.

In the meantime, consider 2025.

The method I prefer:

2025 >= (10a + b)^2 = (10a)^2 + 2(10a)b + b^2

We seek a such that (10a)^2 <= 2025

Think a^2 <= 20

a = 4 since 4^2 <= 20 but 5^2 = 25 > 20

Hence, we have 2025 >= [10(4)]^2 + 2[10(4)]b + b^2 = 40^2 + 80b + b^2

2025 - 1600 = 425 >= 80b + b^2 = b(80 + b)

We need to find b such that b(80 + b) <= 425

Estimate by dividing 425 by 80 ~~~~ a little over 5

5(80 + 5) = 5(85) = 425 so a = 4 and b = 5

Therefore the square root of 2025 is 45, or 45^2 = 2025

Who cares?   I do!   

If I put aside the bug for the case of 1681 for now, we can just be satisfied if you understand how to do a few simple cases with pencil and paper.

324

    1
 |-------
 | 324
  -1
   -----
    2 24

(10(1))^2 = 100 <= 324

324 - 100 = 224 >= b(20 + b)
b = 8 since 8(28) = 224

    1 8
 |-------
 | 324
  -1
   -----
    2 24
   -2 24
 
sqrt(324) = 18


1156:

    3
  |-------
  | 11 56
      9
    -----
      2 56

[10(3)]^2 = 30^2 = 900
1156 - 900 = 256 >= 2(10)(3)b + b^2
b(60 + b) <= 256
b = 4 since 4(64) = 256


      3 4
  |-------
  | 11 56
      9
    -----
      2 56
      2 56

sqrt(1156) = 34


   

Maybe examples are the best approach.  Let's forget about codemode for now.

Find the square root of 177241.

We arrange the radicand in pairs of  2.

I will no longer be writing down the binomial expansion but will be using the shorthand system.  When using pencil and paper, you would of course have all this work in one "long-division style" block.  I separate for clarity of each step of our thought processes unfolding in a natural manner.

Phase 1:

  |----------
  | 17 72 41                 We choose 4 because 4^2 = 16 <= 17



      4
  |----------                  2(10)(4) = 80;  b(80 + b) <= 172
  | 17 72 41                   We choose 2 because 2(80 + 2) = 2(82) = 164 <= 172
   -16
    -------
       1 72
     - 1 64
    --------
             8 41       
                       
                        That first phase of the algorithm is different than the remaining parts.
                        The rest of the algorithm repeats a similar pattern.                   

Phase 2:

      4   2                     We double the result we have extracted so far: 2(42) = 84
  |----------                 
  | 17 72 41                 
   -16                           Now we think:  84_?_ times _?_ <= 841
    -------                      Perhaps using words will make this more clear.
       1 72                       eight hundred forty "something" times "something" is less than
     - 1 64                       or equal to eight hundred forty one, where "something" and
    --------                      "something" are the same number.
             8 41                 Clearly, 1(840 + 1) = 841


      4   2                     We double the result we have extracted so far: 2(42) = 84
  |----------                 
  | 17 72 41                 
   -16                           Now we think:  84_?_ times _?_ <= 841
    -------                      Perhaps using words will make this more clear.
       1 72                       eight hundred forty "something" times "something" is less than
     - 1 64                       or equal to eight hundred forty one, where "something" and
    --------                      "something" are the same number.
             8 41                    Clearly 1(840 + 1) = 1(841) = 841, so we choose 1.


      4   2   1             
  |----------                 
  | 17 72 41                 
   -16                         
    -------                     
       1 72                       
     - 1 64                       
    --------                     
             8 41
            -8 41

So the square root of 177241 is 421.

No calculator, no tables, no black magic.


PS:  I looked at the way this looks when posted, and all the trouble to make it legible and organized is for naught since it goes out of whack when posted.

Sorry Holden.

I'm going to work some out on paper.  It's probably best if I do that and send some examples hand written if you are interested.

Find the largest 3-digit number whose square is less than 261.

       1
   |----------
   |  2 61
     -1
    -----
       1 61

a^2 <= 2  ---->  a = 1
20(1) = 20;  b(20 + b) <= 161
Since 161/25 is between 6 and 7, we'll choose 6
6(20 + 6) = 6(26) = 156 <= 161


       1  6
   |----------
   |  2 61
     -1
    -----
       1 61
     - 1 56
      ------
            5


       1  6 .
   |----------
   |  2 61 . 00
     -1
    -----
       1 61
     - 1 56
      ------
            5 00      Now, 2(16) = 32

c(320 + c) <= 500     Since 500/320 is between 1 and 2, we choose 1.



       1  6 .  1
   |----------
   |  2 61 . 00
     -1
    -----
       1 61
     - 1 56
      ------
            5 00
          - 3 21
           ---------
             1 79           We stop here since we only want 3 digits.


Do you want to try one?

1. Find the largest 3-digit number whose square is less than 3478.

2. Find the largest 3-digit number whose square is less than 7.

This is how to get through a life not worth living, no?

Here is a short but organized explanation: 

https://www.quora.com/What-is-a-digit-by-digit-square-root-algorithm-for-negative-base-number-systems

I found a very interesting page which I think I can follow, but it is written in German.   It seems to get to the root of my interest.  That is, it shows how the formula for the square of a binomial comes into play.

http://www.diaware.de/html/wherleitung.html
I recognize the use of the squaring of a binomial.  I see ...

You can translate the page here.


Consider sqrt(5776) = 76

m = 7, n = 6
sqrt([10m]^2 + 2(10mn) + n^2) = sqrt(70^2 + 20(7)(6) + 6^2) = sqrt(4900 + 840 + 36) = sqrt(5776)

Do you see that I was trying to tie this idea into the presentation of the long-division style algorithm?

Do you see the form of the "formula for the square of a binomial" at play in the way we multiply a number by itself in long form "school mathematics" ?

I also found a link to a mysterious source claiming to be the origin of the algorithm which is similar to the one I am interested in.

Check this out:  http://rechnerlexikon.de/files/PolytJournal1866-Toepler.pdf

Another curiosity:  http://www.ph-ludwigsburg.de/fileadmin/subsites/2e-imix-t-01/user_files/mmm/mmm_online/gruen_frieden.htm

a^2 = the sum of the first a odd numbers

3^2 = 1 + 3 + 5

Fascinating connections made ... Extracting the form ...

Time to at least try to sleep.     Before the depression creeps in.

I don't mind being an obsessed madman.  Even though I do not feel very smart and even though I am usually quite wired and irritable, at least being interested in something keeps me from feeding into all the "manufactured desires" being spread by the Hype Engine.

Take care Fellow Sufferer.

Thanks for respecting my total disdain for "retail programming".

I always like to think that it is because of the likes of me that the U.S. companies outsource their "work" overseas in distant lands, not so much due to some kind of lack of ability on my part, but just my aloofness and total disinterest in licking the boots of the managerial class [human resources].

Anyway, as far as programming long division, the only thing that this old fashioned (and exact, definitely not some kind of approximation) square root algorithm has in common with long division is the way one writes down the work involved, the shorthand that is.

This is why I want to go through the trouble of writing code which will be able to display the work for each given number in that form.  I have not given up on that, although the first attempt become too crazy in C, so I have started from scratch with a totally different approach using C++.   The other code started from an algorithm for the TI-84 programmable calculator.  That is why I had difficulties with some comparisons of floats.

I started over with a "square_root" class which parses the input into a vector so it can handle each pair in turn.

I have completed the code so that it produces the correct results.

The difficult or challenging and therefore most stimulating part I am working on now. 

I am going to use some arrays and, at each phase, I will store each value corresponding to the different places one would jot down in a systematic manner on paper.

My idea is to have an array for subtrahends, for the remainders, and for the results.
In each phase I will add the values to their respective arrays using a "phase counter" so that, at the end of the program, display the "work" all at once.

That's my idea for now.

I have ideas about adding other features in a later incarnation which might talk you through an exercise, having you work WITH the process.

All in good time.   I only get possessed in this CODEMODE every so often, so I do what I can while I am in madman mode until I am able to put it down and say, this is good enough for its purposes; and then i get back into pencil and paper math mode.

So, while I would do this anyway without any correspondence with you, i think that keeping you in mind motivates me to see if I can make this program do far more than instantiate the ancient algorithm.  I want it to display the work, and one day even explain the work involved for each shadowy copy of the form "square root of a number".

You have said in the past that you are some kind of purist.

This is probably the reason why you have far more respect for a tinkerer like myself who spontaneously becomes obsessed with writing code only out of a passion to understand some mathematical idea on a deeper level, than you do for the "hot shots" and "whiz kids" who want to create some GUI APP for retail ...

Even though you may strongly dislike these "techies," I appreciate that you are aware of their inevitable misery.  I'm sure when they were kids they must have been stimulated by coding some mathematical functions at one time; but then at some point they may have preferred working on user-friendly applications for an employer who could pay them a salary, grant them some social status, etc.

I don't judge the gorts too harshly.  But for the grace of the great mysterium, there go I ...

Take care.

I will post upload the shell of this version as Sqrt.txt.

Before I break it by mistake while adding the "educational features", I have renamed the current version being created Sqrt_work.cpp.

I'm taking my time, but, yes, getting very tired at times.  But I do it out of sheer over excitement about these IDEAS ... What a great secret this is, that IDEAS can stimulate our brains even more so than the retail drugs, like ****.

Well, I do love my tobacco and coffee ... but, I am no purist when it comes to thinkgs like that.  The only way I am a purist is that I only exert energy for things which interest me.  If I am forced to labor, I am a total slacker.

And yet ... I do seem to be busy busy busy working on things nobody cares one red cent about ... 

Please understand that I have an extremely humble estimation of my own capabilities.  I have several books which I peck away at a little at a time.  There are some, maybe even many, individuals who are like an entirely different species than me, who are far superior in their mathematical abilities and programming skills.

I will forever be an amateur math junkie; but I am certainly proud of myself for understanding the little bit that I do.  For me, I am proud simply to have an interest and a passion for such things ... to be in awe when running the debugger to see what's what.

It's kind of like how i feel about pianos.  Of course I can't "play the piano," but lead me to a piano in a private place, and I promise I would interact with the contraption in such a way that might bring me to shed a tear or two.

------------------------------------------
I do not take the Internet for granted.  As a solitary autodidact, I do find myself seeking answers to questions in the middle of the night, strange technical questions.  Last night I gained necessary insight from some obscure notes in German which helped me experience a kind of enlightenment. 

Amazingly, tonight I found a cool solution from someone on ZooTube.  It sounds as though he is speaking one of the many dialects in India.  I did not understand a word he said, but I followed the code and I am going to use the solution to deal with setting precision automatically so the user just enters number and desired digits of accuracy.

I was wondering how I might count the decimal places, if any, in the result.

I was trying to use the log10 function, but I like this one:

digits

[attachment deleted by admin]

Thanks to your guidance I have already begun to find consolation-that is, mediation between a hostile earthly reality and aspirations to comprehension-in mathematics. I, by no means, have the ambitions to be another Ramanujan, however, I do wish I could learn a little bit of more mathematics which the Fates condescend to send my way. I perhaps may yet grasp it.

PS: Please ignore the comment if it sounds unreasonable for I do not know such things-but do you think that some of this programming you are involved in could be replicated in a spreadsheet? I have heard that spreadsheets permit VBA code to be incorporated and there are several in-built mathematical formulas in them.

I suppose that implementing this with a spreadsheet would be possible, and perhaps easier, where the results could be placed in the designated cells.

I personally am committed to making this work with C++.

I got it to work with C, but I am trying a more sophisticated approach with C++ using a deque container for working with each pair of numbers.

To be honest, I enjoy learning as much as possible about using the STL containers in C++ and implementing a special file I use in the gdb debugger.   (GDB init file to print STL containers and data members)

So, the project is an opportunity for me to learn about C++.  C and C++ have been an interest of mine for 2 decades now.

I'm not prejudiced against the use of spreadsheets (maybe I am just a little prejudiced) and I know they are used for differential equations, such as the Runge-Kutta method.

I do think it is possible, yes.

I would eventually like to create a version that is more interactive, where the user could be lead by the hand in extracting the square root digit by digit, so, for this kind of approach, no, a spreadsheet would not be how I would want to go about it.

You see, the part where a human being still would want to use a calculator is the part where we seek a value of b such that b(number + b) <= a certain value.   So far, I can have the program display its work as it goes along.  This is not possible with a spreadsheet where only the final results would be displayed.

So, the bottom line is that your suggested is quite valid, but it's not something that I would want to implement at this time since I am committed to a certain way of approaching this problem which will afford an opportunity for me to struggle a little to get some kind of "brute force educational software" to manifest.

Imagine Max from PI using a spreadsheet to display his results ...
It's just more challenging and "pure" to have all this done from the console, that is, from the command line.

Thanks for your mails and attachments.Much appreciated.Today I solved a problem: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.

Keep well.