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

  • Thread starter logics
  • Start date
  • #26
137
0
As far as programming a (programmable) calculator, I'm pretty sure it could be done... and implement the algorithm in some programming language.
I'm not sure if that applies to my old 'programmable' (£10) Sharp EL-509, with no programming language. It has a 12²-place buffer where I can write formulas and ANS. I can put there N (B), [because it's a simple formula], changing x [itex]\rightarrow[/itex] ANS : {(ANS²+a) : 2ANS} , and press 5x Enter. But, is this an algorithm, just because of the feedback : ANS? I can't put LD in my calculator (how do I deal with 'trial-and-error'?), I'd like to learn how to do that, without a real algorithm. This problem has been bugging me, I wonder if anyone can kindly help, as:

I used that term in the OP only beacause I read it in other threads, but I was afraid it was not appropriate, as , AFAIK, N (or B) is just an iterative method, and an iterated formula requires no logical decisions such as : "if A, ...then GOTO; if B...."
The best known algorithm... requires 3 operations, ... Do you know a simpler or faster one? Can you find a method that requires only 1 operation?
1 operation: { k [:] m} can hardly be referred to as an 'algorithm'...(I called it, more modestly, a method)
What about "<" as well?....Many algorithms ...rely on being able to tell whether one number is bigger than another, and so "<" is important.
...which, as it was rightly pointed out, needs decisions like : if p > q, then....;.... if p< q... then STOP etc. But in post #13, again, N was referred to as Newton's algorithm, so, why N's can do without '> <' and mine can't?

Lastly, to explain the sense of my question ("could you tell Altrepair..."): LD is surely less expensive than N and B, especially if we count micro-operations, but is surely more cumbersome than both: my challenge was to find the most simple (and fastest), formula: LD is much more complex than N (B).
'Only one operation' may seem a tall order, but not only it is possible , it is not too difficult if you examine the structure of a square
 
Last edited:
  • #27
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Many languages have conditional expressions in addition to conditional statements: e.g. a function satisfying:

[tex]\textrm{Choose}(P, x, y) = \begin{cases} x & P \\ y & \neg P \end{cases}[/tex]

where P is a truth value. In other languages, conditions return numeric values; e.g. true is 1 and false is 0, but sometimes the opposite. You can implement absolute value, for example, by

[tex] |x| = x (1 - 2(x<0) )[/tex]

Sometimes, various operations can be used as substitutes for tests. e.g. if you have the sign function available, you can use it in ways similar to what I just described when you just care about orderings:

[tex] |x| = x \mathop{\textrm{sign}}(x)[/tex]
 
  • #28
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Doesn't that apply to Newton's algorithm?
Yes. But at the time, I had decided to give you the benefit of the doubt and assume you really mean to ask about algorithms for producing approximations to square roots, but just didn't want to say it out loud.
 
Last edited:
  • #29
137
0
I had decided to ..... assume you really mean to ask about algorithms for producing approximations .
You'll greatly oblige me (and future wievers) :smile:, if you help me edit the OP, can you (or Mark44, or ... anyone) do it?
 
Last edited:
  • #30
34,936
6,699
Wievers - ?? What does that mean? It's not in my dictionary. Did you mean "viewers"?
 
  • #31
1,679
3
It can be done in one step provided you specify the precision in advance.

You use the number as the index into an array containing the root. As long as the precision is specified, each real number is represented by an integer. Most modern computers will perform the indexed register load as an atomic operation (single step).
 
  • #32
137
0
Did you mean "viewers"?
I'm of courteous disposition and act my age, do you expect a reply?

I suggested: (edited OP)
The best known algorithm EDIT: i.e. iterative method ('Babylonian') to take the square root of a number requires 3 operations.....
Do you know a simpler or faster one?
Can you find a method that requires only 1 operation? (No = 1)

EDIT : a [square]root is found with Nt ops., iterating Ni times a formula that requires No ops. using N+ different op-signs. Nt = Ni * No.
Babylonian method
, [itex]\sqrt{354.045^2}, ([/itex] if x0 = 300.00) : N+=No = 3, Ni = 4 , 3 * 4 [itex]\rightarrow[/itex] Nt = 12 operations
if No = 1 [itex]\rightarrow[/itex] (N+ = 1, Nt = Ni); [in the title: N+ = 1 [itex]\rightarrow[/itex] No = 1 , Nt < 12] ;
Nt < 8 is a 'good' solution, (5 * 1) = 5 operations would be 'brilliant'.
Post #31 proves that new readers can't carefully examine all previous posts. An edit to the OP would probably help. Thanks.
 
Last edited:

Related Threads on Challenge: can you take the sqrt (n) using only one operation

Replies
19
Views
4K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
1K
Replies
6
Views
2K
Replies
6
Views
931
Replies
4
Views
1K
Replies
14
Views
13K
Top