The Museum of HP Calculators

HP Forum Archive 17

 Program questionMessage #1 Posted by Vincze on 30 July 2007, 9:00 a.m. 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.

 Re: Program questionMessage #2 Posted by Gerson W. Barbosa on 30 July 2007, 10:28 p.m.,in response to message #1 by Vincze 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.

 Re: Program questionMessage #3 Posted by Vincze on 31 July 2007, 8:39 a.m.,in response to message #2 by Gerson W. Barbosa What key is Rv? I no see on my calculator.

 Re: Program questionMessage #4 Posted by Don Shepherd on 31 July 2007, 8:54 a.m.,in response to message #3 by Vincze Roll the stack down.

 Re: Program questionMessage #5 Posted by Vincze on 31 July 2007, 9:32 a.m.,in response to message #4 by Don Shepherd Thank you. I assume that be key with R and down arrow on? One other question. What is STOP key?

 Re: Program questionMessage #6 Posted by Thomas Radtke on 31 July 2007, 9:45 a.m.,in response to message #5 by Vincze R/S (Run/Stop)

 Re: Program questionMessage #7 Posted by Vincze on 31 July 2007, 9:56 a.m.,in response to message #2 by Gerson W. Barbosa 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.

 Re: Program questionMessage #8 Posted by Gerson W. Barbosa on 31 July 2007, 12:27 p.m.,in response to message #7 by Vincze 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.

 Re: Program questionMessage #9 Posted by Vincze on 31 July 2007, 1:32 p.m.,in response to message #8 by Gerson W. Barbosa 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.

 Re: Program questionMessage #10 Posted by Gerson W. Barbosa on 31 July 2007, 2:19 p.m.,in response to message #9 by Vincze 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].) ```

 Re: Program questionMessage #11 Posted by Thomas Klemm on 31 July 2007, 3:44 p.m.,in response to message #1 by Vincze 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.

 Re: Program questionMessage #12 Posted by Vincze on 31 July 2007, 4:50 p.m.,in response to message #11 by Thomas Klemm 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

 Re: Program questionMessage #13 Posted by Thomas Klemm on 31 July 2007, 5:30 p.m.,in response to message #12 by Vincze 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.

 Re: Program questionMessage #14 Posted by Vincze on 31 July 2007, 8:55 p.m.,in response to message #13 by Thomas Klemm 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.

 Re: Program questionMessage #15 Posted by Gerson W. Barbosa on 1 Aug 2007, 12:19 a.m.,in response to message #12 by Vincze 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.

 Square root digit-by-digitMessage #16 Posted by Nenad (Croatia) on 1 Aug 2007, 7:24 a.m.,in response to message #1 by Vincze 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

 Re: Square root digit-by-digitMessage #17 Posted by Gerson W. Barbosa on 1 Aug 2007, 9:24 a.m.,in response to message #16 by Nenad (Croatia) 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.

 Re: Square root digit-by-digitMessage #18 Posted by Vincze on 1 Aug 2007, 10:13 a.m.,in response to message #17 by Gerson W. Barbosa 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.

 Re: Square root digit-by-digitMessage #19 Posted by Frank Rottgardt on 2 Aug 2007, 7:54 a.m.,in response to message #18 by Vincze 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.

 Re: Square root digit-by-digitMessage #20 Posted by Thomas Klemm on 2 Aug 2007, 9:27 a.m.,in response to message #16 by Nenad (Croatia) 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.

Go back to the main exhibit hall