challenge: can you take the sqrt (n) using only one operation

logics

The best known algorithm ('Babylonian') to take the square root of a number requires 3 operations, less than Newton's. I suppose it's also the fastest. Is it so?
Do you know a simpler or faster one?

Can you find a method that requires only 1 operation?

Hurkyl

Yes: apply the square root operation.

logics

square root is the problem to be solved, can it also be the solution?

[I]
P.S.: I apologize if I have been ambiguous: *(one of the 4 operations. +, -, x, : ). The algorithm should contain 1 op, but it can be iterated a few times, of course!
to simplify discussion and use a pocket calculator, let's choose (n = x²) n with less than 21 digits:
210.3456789², 987654.3012²... 597482²....etc

dodo

Yes; if you already know the solution to be, say, r, then you can find said solution by just one division, n/r.

Hurkyl

So, we get to use "limit" as an operation too? What about "<" as well?


I'm not just being snarky here -- it is provably impossible to obtain [itex]\sqrt{2}[/itex] using just those four operations along with any integers you want, so "limit" or some other related concept is rather important.

Many algorithms for extracting roots rely on being able to tell whether one number is bigger than another, and so "<" is important.

logics

We are only trying to solve a practical problem: we are trying to apply our contemporary wisdom to see we if can do any better than the Babylonian method, if that is really the best algorithm. (I'll tackle this in a separate post). Our solution should be more convenient even using pencil and paper. Do you think it is possible?

If n is not a square number ([itex]\sqrt{2}[/itex]...[itex]\sqrt{125348}[/itex]... etc), we have to stop sometime, somewhere, maybe after 10¹⁰ digits, but we must stop. Hope you agree. If a simple, convenient method requires '>','<' ,... or other, it is interesting to see it.
I was only responding to your (jocular?) post #2, excluding the obvious sqrt, log, ln, etc. I hope that is clear.
here: they decided to stop after 6 digits: 354.045, and it took them 5 rounds (iterations) = 15 (5*3 [+, :, :]) ops. to reach that result. Can you do any better?
I suggested to stop at 10 places (9digits plus the point) so that non specialists (without a computer program), like myself, can follow or take part in the discussion with just a pocket calculator.

If this is not clear I'll exemplify: my calculator says [itex]\sqrt{125348}[/itex] = 354.0451949 , the number is obviously truncated and I cannot know if it is rounded up or down and if it is correct to stop at 354.0451948.
That is why I suggested to start with a number with finite number of decimals ( like [itex]\sqrt{125347.862}[/itex]) to know that exactly 354.045 is our goal.



P.S. Moreover, if you start with a finite n you can find its root even when many digits are missing: [itex]\sqrt{623,470.122 xxx xxx x49}[/itex], we can find the root: x = 789.601243

DonAntonio

Your whole post is pretty confusing, making your nick paradoxical. You talked of calculating the square root of a number

using "only one operation"...Did you mean using one operation several times, did you mean to use one unique

operation once? It should be obvious that either possibility has a negative answer: no, it is not possible IN GENERAL to do that

with only one operation, whatever "one operation" means to you.

Now, it is possible to evaluate the square root of any number to any degree of wanted precision by elementary operations,

namely +, -, *, /, and I don't know if this is the babylonian method.

DonAntonio

logics

If you do not know it, probably that is the reason why you could not understand my post. I gave you a link, scroll up a little:
In the OP (post #1), I noted that Babylonian algorithm requires 3 operations for each iteration, as surely by now you have found out. In the title, if you're referring to that, I could not possibly explain everything.

I'm asking if you can find a simpler one (algorithm), one which requires less then 3 ops at each iteration. One op., of course, is the limit.
EDIT: Such an algorithm is likely to be less powerful, to converge slower, but it would require less then 15 ops. (in the #Example quoted), I suppose anyone can do better than wiki . I'm sure you are able at least to make a first guess more accurate than x₀= 600

If you run the algorithm only once then you take directly sqrt(n), and you reach your goal with one operation.( 'ne plus ultra' !).


Besides the OP, you probably missed also post #3:
I hope it is clear, if it was not.


P.S. A nick is a nick, what's in a name? that which we call a rose....

DonAntonio

I read only what you wrote in your first post, which is exactly the following:


"The best known algorithm ('Babylonian') to take the square root of a number requires 3 operations, less than Newton's. I suppose it's also

the fastest. Is it so? Do you know a simpler or faster one?

Can you find a method that requires only 1 operation?"


No iterations, no links, nothing. That's what confused me and, judging by the first responses at least, apparently also others.

DonAntonio

jgens

No such algorithm exists. Fix the number 2 for example and try to approximate the √2 using only one operation from {+,-,×,/}. If we choose either + or -, then we can either add or subtract 2 (or multiples of 2) from itself repeatedly, so the result will be 2n where n an integer. If we choose either × or /, then we can either multiply or divide 2 (or powers of two) from itself repeatedly, so the result will be 2ⁿ where n an integer. But neither 2n nor 2ⁿ can approximate √2 to more than say one or two decimal places.

logics

Thanks jgens, that gives me a chance to compare methods and check if it is my terminology that generates misunderstanding:

here is: B method, is this procedure an algorithm? (If it cannod described as an algorithm, I stand corrected and I apologize).
This method requires 3 operations:

(x + a : x) : 2
...1....2....3
As wiki shows, the formula must be iterated 5 times and that adds up to 15 ops. (to find: sqrt{125348} = 354.045, 6-digit accuracy)

There is another method : N[ewton]. It is equivalent to B, but (because of the way it is usually formulated), it requires 4 operations:
(x * x + a) : 2 * x
.. 1...2.....3....4
(You can find out how many ops. are necessary to solve the problem, if N it is better than B)

Now, why should all the objections apply only to a hypothetical method A that requires 2 operations?.
If I am missing something and your objections are valid only for my hypothesis, please change n to 125347.862025 or any other n which you deem suitable, and let's change the title:
Can you find the square root of 125347.862025 (x= 354.045) with less than 15 operations?

Thanks for your help, jgens, I hope you'll give us the first concrete contribution: if you were in Alexandria or Miletus, or in the Middle Ages with quill and parchment , how would you find 354.045?

DonAntonio

Using the system my dad taught me and which he learnt when he was a kid, either from my grandpa or at school:

subdive the given number in groups of 2, from right to left, before and after the decimal point:

12´53´47.86´20´25

The above 2-groups will be the ones "going down" after each step is finished.

Begin with 12 at left: take the number whose square is closeset to 12 but less than or equal to it. In this case

it is 3 and we write down aside.

Square it and substract it from 12: we get 3 below 12 and we draw down the next pair, 53, thus getting 353.

Double 3, getting 6 (of course, this is just the double method in some disguise which makes, perhaps, easier to carry on by hand)

Find a digit x such that [itex]6x\cdot x[/itex] is as close as possible to 353 but no more than it: this digit is 5 and we

write down aside at the right of the 3, so 65*5 = 325, and substract this from 352, getting 28, and now draw down the next pair 47...etc.

As you can see, we need two operations for each digit in the answer: doubling the already found number and then multiplying, except

for the first digit which only required squaring it.

So in this case we need 12 - 1 = 11 operations.

DonAntonio


Pd Hmmm...perhaps the substractions must be counted also and thus I have more operations. A pity...

Hurkyl

Division by 2 is barely an operation. General division is more expensive than general multiplication, and much more than plain addition.

I checked GMP source code -- for small square roots ([itex]N \in [0, 2^{64})[/itex]), they use start off with a table lookup (for very small numbers), and then use Newton's algorithm to approximate y ~ 1/√N, which has the advantage of requiring no general divisions:
[tex]y \leftarrow (1/2) (N y^3 + y)[/tex]
with the very last iteration mixing in an extra multiplication by N so the result is an approximation x ~ √N
[tex]x \leftarrow (1/2) (y (Ny)^2 + (Ny)) [/tex]

GMP is actually computing an integer square root with remainder. Once it has the approximation, it computes x^2, and then increments it along until it gets the exact value of [itex]\lfloor \sqrt{N} \rfloor[/itex] (this doesn't require general multiplication: [itex] (x+1)^2 = x^2 + (2x+1)[/itex]), and then obtains the remainder.

I haven't worked out the exact details of what it's doing for larger square roots.

logics

That is true, but may lead to subjective evaluation: plain addition (n+n) is equivalent to division by 2 (n:2) but, arguably, easier. If we want to be more accurate we may count the micro-operations

Doesn't that apply to Newton's algorithm?

coolul007

The sum of the first "n" odd numbers is n^2, conversely, when the sum matches the desired number it's the square root. To find the square root of 2 simply add pairs of zeros for the desired accuracy. I guess this is 2 addition operations and one compare.

logics

Sorry, jgens, I did not reply directly to your post because I thought I was using the term 'algorithm' in a wrong way. You used Hurkyl's example, so I thought you were referring to his post, (which I still do not understand). Probably, as I said, I am missing something, could you tell me what?
The fact that Newton's algorithm (which uses only 3 different ops. +, x, :) is actually used (post #13) proves, I suppose a fortiori, that one can find a method using those four operations.

Yours is sound reasoning, but it is founded on the assumption that any method must use B's (or N) logics (the weighted mean).
You can't prove, by that, that no such algorithm exists.
I do not believe anyone can prove that such method is impossible. As you know, proving that something is impossible is a tough job.
(Which operation is suitable, seems obvious.)
As I said in a previous edit, any schoolboy can do better than wiki and find the right x₀, and that would mean only 4 iterations (that is 12 ops.)
What is the best 'first-guess' you can make?

phylotree

I don't know if this is flawed but a pretty good read to go on.

Given x, now you are asked to find √x. You then will know x's integral sup and inf values, supposing they are a, b then you will have [itex]a ≤ \sqrt{x} ≤ b[/itex]. You can then use [itex]c=\frac{a+b}{2}[/itex] for each iteration to approximate the result
How many operations are needed depending upon how many decimal values you want to find .