▼
Posts: 376
Threads: 35
Joined: Jul 2007
I have very enjoyable weekend playing with new 35s. Based on one post on Friday about square root algorithm, I sat down and wrote program on 35s to calculate the square root. I had some problem with it, but it generally work ok. I also write program in C to do, and it much quicker that calculator, but that understandable. In C, it very fast for some numbers, but when number get over 20 digit long, it take long time to calculate.
I know we have sqrt function on calculator, but anyone know of way to write optimized program on 35s? I not very good with programing calculators, but I be interested in seeing how wiser person write.
Again, please excuse poor English mine.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Hello Vincze,
This is not optimized for the HP35s (I haven't read the manual yet). As an exercise, I tried to use only the stack, although I am not sure if this will make to program run any faster on the 35s. It could be shorter, I think. This is the same algorithm in the TurboBCD program below, except it doesn't handle sqrt(0). The initial guess should be improve (the program will take longer to run for large arguments).
S001 LBL S
S002 0.5
S003 x<>y
S004 *
S005 ENTER
S006 ENTER
S007 ENTER
S008 LASTx
S009 ENTER
S010 Rv
S011 x<>y
S012 /
S013 x<>y
S014 +
S015 LASTx
S016 x<>y
S017 2
S018 /
S019 x=y?
S020 STOP
S021 x<>y
S022 ENTER
S023 /
S024 x<>y
S025 Rv
S026 x<>y
S027 *
S028 GTO S010
I am implementing some functions in TurboBCD. The square root function will be handy for inverse trigs.
Regards,
Gerson.

_{
Program Sqrt;
var x: real;
i: integer;
function Sqrt(x: real): real;
var s, t: real;
begin
if x<>0 then
begin
s:=x/2;
repeat
t:=s;
s:=(s+x/s)/2
until s=t;
Sqrt:=s
end
else
Sqrt:=0
end;
begin
ClrScr;
WriteLn(' x  Sqrt(x)');
WriteLn('');
for i:=0 to 10 do
WriteLn(i:2,'  ',Sqrt(i):18:17)
end.
Output:
x  Sqrt(x)

0  0.00000000000000000
1  1.00000000000000000
2  1.41421356237309505
3  1.73205080756887730
4  2.00000000000000000
5  2.23606797749978970
6  2.44948974278317810
7  2.64575131106459059
8  2.82842712474619010
9  3.00000000000000000
10  3.16227766016837933
}
Edited: 30 July 2007, 10:35 p.m.
▼
Posts: 376
Threads: 35
Joined: Jul 2007
What key is Rv? I no see on my calculator.
▼
Posts: 1,392
Threads: 142
Joined: Jun 2007
▼
Posts: 376
Threads: 35
Joined: Jul 2007
Thank you. I assume that be key with R and down arrow on? One other question. What is STOP key?
▼
Posts: 1,089
Threads: 32
Joined: Dec 2005
Posts: 376
Threads: 35
Joined: Jul 2007
Gerson, I try your program, but it no work. Maybe I not use program correct. I clear stack, and put 9 in X, but I get divide by 0 error.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Hi Vincze,
Please check your listing:
K001 LBL K
K002 0.5
K003 x<>y
K004 *
K005 ENTER
K006 ENTER
K007 ENTER
K008 LASTx
S009 ENTER
K010 Rv
K011 x<>y
K012 /
K013 x<>y
K014 +
K015 LASTx
K016 x<>y
K017 2
K018 /
K019 x=y?
K020 STOP
K021 x<>y
K022 ENTER
K023 /
K024 x<>y
K025 Rv
K026 x<>y
K027 *
K028 GTO K010
Please notice x<>y ‚ x<>y?
STOP > R/S
Rv > Roll down key
Regards,
Gerson.
P.S.: I changed the label to K to match the squareroot symbol.
Checksum: C435
Length: 88 bytes
( yellowshift MEM 2 yellowshift SHOW )
Edited: 31 July 2007, 12:33 p.m.
▼
Posts: 376
Threads: 35
Joined: Jul 2007
Thank you Gerson. I see I did have error in entry. I fix and try and it now work. It seem slow. I enter 9999999999999 and it take about 8 seconds. I wonder how HP wrote algorithm for assigned sqrt key? I always wonder how a key could be faster than program can be. Granted, it must be written in machine language, so should be faster, but I wonder if anyone have knowledge of how calculator company does this.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Quote:
I enter 9999999999999 and it take about 8 seconds.
This takes 4.5 seconds in mine. Perhaps you've missed one 9 here. It all depends on the initial guess. Change line K002 to 3E7 and it will take 1.2 seconds. On the other hand, it will take 4.5 second for 9.
Quote:
I wonder if anyone have knowledge of how calculator company does this.
Well, not exactly from a calculator company (MS in MSX stands for you know what).
_{
Quoting from "The MSX Red Book":

Address... 2AFFH
This routine is used by the Factor Evaluator to apply the
"SQR" function to a double precision operand contained in DAC.
The function is computed using the NewtonRaphson process, an
equivalent BASIC program is:
10 INPUT"NUMBER";X
20 GUESS=10
30 FOR N=1 To 7
40 GUESS=(GUESS+X/GUESS)/2
50 NEXT N
60 PRINT GUESS
70 PRINT SQR(X)
The above program uses a fixed initial guess. While this is
accurate over a limited range maximum accuracy will only be
attained if the initial guess is near the root. The method used
by the ROM is to halve the exponent, with rounding up, and then
to divide the first two digits of the operand by four and
increment the first digit.

(Avalon Software. The MSX Red Book. Pangbourne: Kuma Computers, [c.1985].)
}
Posts: 735
Threads: 34
Joined: May 2007
Instead of calculating the square root of a number d the inverse of the square root may be calculated followed by the multiplication of d:
1
sqrt(d) =  * d
sqrt(d)
Use an initial value:
x_{0} ~ 1 / sqrt(d)
and calculate x_{1}, x_{2}, x_{3}, ...
with the following formula:
1  d * x_{i}^{2}
x_{i+1} = x_{i} + x_{i} 
2
This method has the advantage that only a division by 2 is needed.
Here's an HP11c program:
01 LBL A 14 *
02 STO I 15 
03 1 16 *
04 + 17 2
05 1/x 18 /
06 ENTER 19 RND
07 LBL 0 20 x#0
08 + 21 GTO 0
09 ENTER 22 +
10 x^2 23 RCL I
11 1 24 *
12 x<>y 25 RTN
13 RCL I
I guess it's easy to convert that into a program for the HP35s.
Now let's suppose we want to calculate sqrt(5) only with paper
and pencil using an initial guess x_{0} = 0.4.
At the beginning the multiplications are easy to perform since we have only few significant digits whereas at the end the numbers become smaller and smaller.
However there's a slight difference compared to the program above.
Since x_{i+1} = x_{i} + dx the square of the next value is calculated using the square of the previous:
(x_{i+1})^{2} = x_{i}^{2} + (2*x_{i} + dx)*dx
1.00000
.....................................................................
0.00000 > 0.00000 5.00000
+ 0.40000 > * 0.40000
 
0.40000 > + 0.40000 2.00000
======= 
0.40000 > * 0.40000

0.80000 >  0.80000

* 0.20000 < 0.20000

0.08000
/ 2

0.04000
=======
.....................................................................
0.40000 > 0.40000 5.00000
+ 0.04000 > * 0.04000
 
0.44000 > + 0.44000 0.20000
======= 
0.84000 > * 0.84000

0.16800 >  0.16800

* 0.03200 < 0.03200

0.01408
/ 2

0.00704
=======
.....................................................................
0.44000 > 0.44000 5.00000
+ 0.00704 > * 0.00704
 
0.44704 > + 0.44704 0.03520
======= 
0.88704 > * 0.88704

0.03122 >  0.03122

* 0.00078 < 0.00078

0.00035
/ 2

0.00017
=======
.....................................................................
0.44704 > 0.44704 5.00000
+ 0.00017 > * 0.00017
 
0.44721 > + 0.44721 0.00087
======= 
0.89425 > * 0.89425

0.00078 >  0.00078

* 0.00000 < 0.00000

0.00000
/ 2

0.00000
=======
.....................................................................
0.44721
* 5.00000

2.23607
=======
Credits to Newton for this marvelous algorithm.
Edited: 31 July 2007, 4:09 p.m.
▼
Posts: 376
Threads: 35
Joined: Jul 2007
Quote:
Credits to Newton for this marvelous algorithm.
I do like Newton's method, but I believe the Babylonian method to be better since it considered a quadratically convergent algorithm meaning that with each iteration, it get closer to final result.
On a side note, I do some research and see that most pocket calculator use routine to compute exponential function and the natural log in for of sqrt = e^.5lnS where S is the number you are trying to find sqrt of (I believe). I try this, but I have not had luck with yet on 35s.
Ok.. I figure out how to use exp ln method, and it work very fast. Here is how I write.
S001 LBL S
S002 ENTER
S003 LN
S004 0.5
S005 *
S006 ex (as is EXP(x))
That is it. I try with large number (63 9's) and it calculate instantly. I should have thought of this before with my experience with slide rule. That how we could find sqrt on slide rule (although good slide rule have ability to square and show square root too).
Edited: 31 July 2007, 5:10 p.m. after one or more responses were posted
▼
Posts: 735
Threads: 34
Joined: May 2007
Quote:
I believe the Babylonian method to be better since it considered a quadratically convergent algorithm ...
Both algorithms converge quadratically with a good initial choice.
That's not the difference. Use the one I've mentioned above if for some reason division compared to multiplication is expensive.
Quote:
... meaning that with each iteration, it get closer to final result.
Well, that's not exactly the definition of
quadratic convergence.
▼
Posts: 376
Threads: 35
Joined: Jul 2007
Good evening Thomas. Yes you right that both quadratically convergent. I think that yours harder to do in head if wanting, but we not talking about doing in head, but in basic calculator program, so you have valid point. My apologies.
Please excuse my poor english.
Posts: 2,761
Threads: 100
Joined: Jul 2005
Even shorter and faster:
S001 LBL S
S002 SQRT
S003 RTN
Just kidding :)
Klemm's idea and mine was to present a numeric method for the square root function. Using logarithm to compute the square root is slower than computing it through those methods, so computer languages and calculator might use the latter, even though they have builtin logs.
Here is an improved version of the first algorithm, slightly slower but shorter despite handling zero:
L001 LBL L
L002 x=0?
L003 RTN
L004 ENTER
L005 ENTER
L006 2
L007 /
L008 ENTER
L009 REGZ
L010 x<>y
L011 /
L012 LASTx
L013 ENTER
L014 Rv
L015 +
L016 2
L017 /
L018 REGZ
L019 x=y?
L020 RTN
L021 Rv
L022 GTO L008
People who've read up the manual might come up with an even shorter routine :)
Edited: 1 Aug 2007, 12:20 a.m.
Posts: 172
Threads: 21
Joined: Sep 2005
This is something I remember from elementary school, i.e. how we calculated the square root digitbydigit, implementing penand pencil methods. It goes something like this:
SQRT(24378)=?
SQRT(2 43 78)=1 5 6,1 3...
1 43 : 25 x5
18 78: 306 x6
42 00: 3121 x1
10 79 00: 31223 x3
In each step you calculate a single digit x, by guessing it so that the present remainder added the two digits of the original number, divided by the doubled current result with the digit x, written at its end times x subtracted from the current remainder gives the new remainder...
OK, I admit that I have just got lost in this explanation, but hopefully the shown example may shed some more light.
Maybe, someone could write an RPN program to do this.
Until then I prefer the Gerson's solution for my faithful HP67:
LBL A; SQRT(x); RTN
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Hello Nenad,
Quote:
This is something I remember from elementary school, i.e. how we calculated the square root digitbydigit...
That's the way we computed square roots at school too. I remember once I forgot the algorithm when I needed it but I did remember the iterative method. I couldn't help remembering Isaac Asimov's short story "A Feeling of Power"...
Quote:
Until then I prefer the Gerson's solution for my faithful HP67: LBL A; SQRT(x); RTN
Actually, I prefer just to press the SQRT(x) key, especially when it is a primary key as on the HP35s. There are some side effects though... Read Asimov's short story :)
Best regards,
Gerson.
▼
Posts: 376
Threads: 35
Joined: Jul 2007
Good morning Gerson. The story you talk about is very important to mankind. I remember reading long time ago, and thinking it not possible that man forget how to do math. But when you see young people struggle with math, and even simple math like multiplication, it do seem very real, and very scary. This why I have fear of my son using calculator in high school. Calculator ok for checking, but I think too many child become calculator dependent that they know not how to think properly. I know I am not smartest person in world, but I also know that skills that I have need to be used to maintain them and calculator and computer only tool to help do math faster. I believe it is so important that child know math and not rely on calculator.
In Hungary, we no allowed to use calculator when I was in school. Has this changed since, I do not know. I need to write my brother and see as he have children my son age there. In fact, when I in university, slide rule was even frowned upon as a crutch, but much needed crutch for more advanced math. Main point though, all students at university understood concept of doing math with pencil and paper first.
Anyhow friend, thank you for reminding us of that short story. It is something all should read.
▼
Posts: 115
Threads: 16
Joined: Jul 2007
Once the rifle and matches became common our hunting ancestors couldn´t imagine how huamnity will survive without knowing the basics of archery and making fire. The most important part of hunting is a) to find the deer b) to sneak up and finally c) to kill it. Today only c) has changed. Skills a) and b) are still something each hunter need to know how.
Back to math:
a) is to understand the problem, b) is to know wich mathematic tools are necessary and c) is to obtain the result
a) and b) is the same as for 100 years ago, only c) changed: calculator or PC. As long as our kids are familiar with a+b I can´t see the end of the world. If your calculator should be broken, let´s fetch a second one from the 23 each one has around. Or go to the next shop and buy a new one for 20 bugs or borrow one from your neighbour.
But I do agree in one point:
It gives you a better feeling if you know to judge the calculator results since you are able to make a rough estimation by means of mental arithmetics. Also it looks better if you are able to check the bill at Walmart without pulling your calculator.
Posts: 735
Threads: 34
Joined: May 2007
Quote:
SQRT(2 43 78)=1 5 6,1 3...
(...)
10 79 00: 31223 x3
Just wanted to point out that by actually calculating the quotient in the last step some more correct digits may be obtained:
sqrt(24378) = 156.134557353...
107900 / 31223 = 3.4557857...
====
Edited: 2 Aug 2007, 11:04 a.m.
