I saw this math video and don't have time to try it out now (got a CT scan appointment, but after I get back I will) but I thought I'd give a head's up. What to beat? Using floats and the square root function.
I do not remember ever knowing this..
I gave it a try, but I'm sorry: that video and that explanation gave me a bad headache. She always seems confused; she doesn't explain things clearly, which confuses anyone watching this video... And then at 6:00 she even gets lost in the 5x7 multiplication...
You should focus on the video below, which comes from a reliable, excellent, and highly popular mathematics YouTube channel I follow:
Another method for extracting the square root of an integer
using only basic arithmetic.
It always starts with 1 and uses the odd numbers in the sequence.
Ex square root of 278
- 278 - 1 = 277
- 277 - 3 = 274
- 274 - 5 = 269
- 269 - 7 = 262
- 262 - 9 = 253
- 253 - 11 = 242
- 242 - 13 = 229
- 229 - 15 = 214
- 214 - 17 = 197
- 197 - 19 = 178
- 178 - 21 = 157
- 157 - 23 = 134
- 134 - 25 = 109
- 109 - 27 = 82
- 82 - 29 = 53
- 53 - 31 = 22
.... 22 - 33 = -11
16*16 = 256 + 22 = 278
I have applied her method to the number 1237.235 and have found 35.17 as the correct square root. How old is this manual method, and who is the inventor?
remember years ago using "Heron's method" for determining square roots, e.g.
// iterative method of square root - called"Babylonian method" or "Heron's method"
//https://www.math.uwaterloo.ca/~baforres/UCM137/Lectures/Chapter1/L3b_HeronSLIDES.pdf
// https://en.wikipedia.org/wiki/Square_root_algorithms#Heron's_method
#include<iostream>
#include<fstream>
#include<cmath>
#include<cfloat>
#include<iomanip>
using namespace std;
// recursive version ??
double FindSqrtRecursive(double x)
{
static double r=2.0; // guess at root
r = (x/r + r)/2; // next itteration
if (fabs(r-x/r)<= FLT_EPSILON) return r; // accuracy required, if so return
return FindSqrtRecursive(x); // no, do next itteration
}
// iterative method of square root - called"Babylonian method" or "Heron's method"
double FindSqrt(double x)
{
double r=2.0; // guess at root
do
r = (x/r + r)/2; // next itteration
while(fabs(r-x/r)>= FLT_EPSILON); // accuracy required?
return r; // yes, return
}
int main()
{
ifstream sqrtin;
double x =0;
x=16.0;
cout << "enter number ? ";
cin >> x;
cout << "sqrt("<< x << ") Heron's " << FindSqrt(x) << " recursive " << FindSqrtRecursive(x) << " library " << sqrt(x);
}
a run using CodeBlocks GNU C++ for sqrt(2.0)
enter number ? 2.0
sqrt(2) Heron's 1.41421 recursive 1.41421 library 1.41421
Process returned 0 (0x0) execution time : 7.915 s
Press any key to continue.
Think the idea is based upon
(a+b)^2 = a^2 +2ab +b^2
A is the larger part and b is the smal part
Sqrt(234)
We can see a = 15 as 16 is too large.
So 15 is first estimate for a.
Equation becomes
234 =15^2 + 2x15xb + b^2
234-225 = 9 = 2x15xb + b^2
If we ignore b^2 we see that b = 9/30= 0.3
B^2 ~ 0.09
So sqrt of 234 = ~15.3 with an error of 0.09
The video chooses 0.2 as 0.3 is just too large and subtracts. And the equation becomes
234 = (15.2 + b)^2 = 231.04 + 2x15.2xb +b^2
234-231.04 = 2.96 = 30.4xb +b^2
Ignore b^2
B = 2.96 /30.4 = 0.097...
So a better estimate becomes 15.29
So 234 = (15.29 +b)^2
Etc
15.29 squared = 233.78... so closing in.
It dates back to Rafael Bombelli, around the middle of the 16th century; a more rigorous description follows below:
But if you're interested, MindYourDecisions YT channel is a good starting point.
For binary integers a bisection method should not be difficult to implement. If the integer can e.g. be represented with 22 bits, the sqrt has half or half +1 that number so 11 (or 12). Every bit takes a test (is the next bit a one or a zero)
Fun exercise for the students.
In the category amazing hacks this one is still one of the best imho.
It is more than that!
While finding the square root of 1237.235 using the long division method of post #1, at the third step, I have a divisor prefix of 702 and a dividend of 52250. As a human, I can quickly deduce that the next digit of the divisor is 7 (since 7027 x 7 = 49189). However, it is not so trivial for a human being (student) to design an algorithm for an MCU to determine that digit 7 automatically.
Hopefully, someone will provide an implementation.
I guess I'm not 'anyone'. I had to back up and re-view one step I missed. All that matters is the idea.
It seems to work off the 10's squares of the decimal system and every step cranks out a final answer digit.
I'm going to have to think for a while... use serial strings maybe.
and how that can apply in a sliding manner, flattening as it goes.
2 digit groups, radix squared to crack out square roots in that radix high order to low. 2 digits that generate 1 cause square root of 2 digits will always be 1 digit.
2 digits to make a square, 3 for cube?
It would be an interesting task to convert the manual steps of post #1 into Arduino code. I am also trying to write the code.
Adding a group of 2 digits is like multiplying by 100 (of which sqrt = 10). That keeps digits same
E.g sqrt 16 = 4, sqrt 1600 = 40. Sqrt 1.6 =0.4
But sqrt 160 = 12. 64... Sqrt 1.6 = 1.264.. sqrt 16000 = 126.4..
.------
For cubes I don't know, readoning along the same lines one would add in groups of 3 digits indeed as cuberoot has same digits for every factor 1000.
The strategy could be similar, approaching the answer from below. Algorithm wise unknown.
Are you sure that a string-based approach, which requires converting character strings into integers to perform each step of the calculations, is more efficient than Heron's method (Newton-Raphson) on our MCUs?
I really don't think so off the top of my head, but a program to compare efficiency (i.e., processing time, as well as any memory usage) could provide an answer.
String based will not be as efficient for sure.
As far as I understand the question, it is more how the method works.
Tried to extend the method to cube root but without success so far.
The approach extends to cube roots if you group the digits in threes starting from the decimal point, but whereas finding the next digit is fairly easy to do mentally for square roots, it is more convoluted for cube roots.
Variables. p is the number formed by the root digits already found (0 at the start). d is the new digit you are trying, from 0 to 9. B is the current working number, made of the previous remainder followed by the next group of three digits (for the first step, B is simply the first group).
For square roots, the trial term is (10 × (2 × p) + d) × d, with groups of two digits. You can guess d by dividing B by 10 × (2 × p), and that guess is usually right or off by one, because the d × d part is small compared with the rest once p has a couple of digits. The check is a single multiplication of a number by one digit.
For cube roots, the trial term is (100 × (3 × p × p) + 10 × (3 × p) × d + d × d) × d. You look for the largest d for which the trial term does not exceed B, the new remainder is B minus the trial term, and the new p is 10 × p + d. Guessing d by dividing B by 100 × (3 × p × p) ignores the two other terms, which are not negligible, so the guess is often too high and has to be lowered. You also have to compute 3 × p × p at each step, which has about twice as many digits as p, then build the three-term bracket for each candidate digit, then multiply by d. The working numbers also grow by three digits at each step instead of two.
Example with the cube root of 74088 (which is 42 × 42 × 42). Group the digits in threes from the decimal point: 74 | 088.
First step. The first group is 74. The largest d with d × d × d ≤ 74 is 4, since 4 × 4 × 4 = 64 and 5 × 5 × 5 = 125. So p = 4, and the remainder is 74 − 64 = 10.
Second step. Bring down 088, so B = 10088. With p = 4, 100 × (3 × 4 × 4) = 4800 and 10 × (3 × 4) = 120, so the bracket is 4800 + 120 × d + d × d. Quick estimate: 10088 divided by 4800 is about 2.1, so the guess is d = 2. Check: the bracket is 4800 + 240 + 4 = 5044, and the trial term is 5044 × 2 = 10088, which equals B exactly, so d = 2 is accepted. For comparison, d = 3 would give (4800 + 360 + 9) × 3 = 15507, which is too large. The new remainder is 10088 − 10088 = 0 and the new p is 10 × 4 + 2 = 42. The cube root of 74088 is 42.
PS. The formula comes from expanding the cube of the root found so far, written as 10 × p + d, where d is the new digit: (10 × p + d) × (10 × p + d) × (10 × p + d) = 1000 × p × p × p + 100 × (3 × p × p) × d + 10 × (3 × p) × d × d + d × d × d. The first term, 1000 × p × p × p, was already subtracted in the previous steps, since it is the cube of the root found so far shifted by three digits. What remains to subtract at the current step is therefore 100 × (3 × p × p) × d + 10 × (3 × p) × d × d + d × d × d, which is the trial term above. The square root method comes from the same idea applied to (10 × p + d) × (10 × p + d) = 100 × p × p + 10 × (2 × p) × d + d × d.
might be useful with streamed data
BCD would be more efficient and it can be streamed
Fair enough, but—aside from the fact that I can't quite picture an Arduino application requiring the calculation of a square root from a number streamed as a string (or BCD)—these calculations seem more "heavy" to me than simply using floats with Heron's method.
As I said, I’d be interested to see a comparison regarding efficiency (calculation speed and memory usage). But since I don't have a need for this myself, I'll pass... ;-)