Program question



#2

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.


#3

Hello Vincze,

This is not optimized for the HP-35s (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.


#4

What key is Rv? I no see on my calculator.


#5

Roll the stack down.


#6

Thank you. I assume that be key with R and down arrow on? One other question. What is STOP key?


#7

R/S (Run/Stop)

#8

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.


#9

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 square-root symbol.

Checksum: C435
Length: 88 bytes

( yellow-shift MEM 2 yellow-shift SHOW )

Edited: 31 July 2007, 12:33 p.m.


#10

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.


#11

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 3E-7 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 Newton-Raphson 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].)

#12

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:

x0 ~ 1 / sqrt(d)

and calculate x1, x2, x3, ...
with the following formula:

               1 - d * xi2
xi+1 = xi + xi -----------
2

This method has the advantage that only a division by 2 is needed.

Here's an HP-11c 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 HP-35s.

Now let's suppose we want to calculate sqrt(5) only with paper
and pencil using an initial guess x0 = 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 xi+1 = xi + dx the square of the next value is calculated using the square of the previous:


(xi+1)2 = xi2 + (2*xi + 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.


#13

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


#14

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.


#15

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.

#16

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 built-in 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.

#17

This is something I remember from elementary school, i.e. how we calculated the square root digit-by-digit, implementing pen-and 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


#18

Hello Nenad,

Quote:
This is something I remember from elementary school, i.e. how we calculated the square root digit-by-digit...

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 HP-35s. There are some side effects though... Read Asimov's short story :-)

Best regards,

Gerson.


#19

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.


#20

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 2-3 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.

#21

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP Prime: run a program in another program Davi Ribeiro de Oliveira 6 334 11-11-2013, 08:28 PM
Last Post: Davi Ribeiro de Oliveira
  42s program question David Persinger (US) 5 252 08-09-2012, 06:34 AM
Last Post: David Persinger (US)
  WP34S program question Mike Maiorana 12 394 04-05-2012, 03:09 AM
Last Post: Steve Simpkin
  HP-41 MCODE: Making an MCODE program call another MCODE program Geir Isene 10 436 01-13-2008, 05:58 AM
Last Post: Raymond Del Tondo
  15C program question John Nelson 7 297 06-06-2007, 10:01 PM
Last Post: Karl Schneider
  19BII Program Question Hans van der Drift 3 138 01-29-2007, 06:58 PM
Last Post: Hans van der Drift
  HP-97 (Diagnostic) Program Question Olaf 3 159 09-25-2004, 06:35 AM
Last Post: Olaf
  Another hp42s program question Tom White 11 367 08-30-2004, 01:05 AM
Last Post: Tom White
  32SII Program Question Charles Perry 2 119 05-19-2004, 02:55 PM
Last Post: Mark Hardman
  HP 33S Program question Mike 7 304 05-12-2004, 10:08 AM
Last Post: Richard Garner

Forum Jump: