HELP WANTED ON ALGORITHMS



#21

Hello community, I received this email:

I am a maths teacher at a Collège (high school I believe) in Geneva,
Switzerland, and am currently following a student in her final year's
personal project. She decided she wanted to know how her calculator
works, not the physics, but the algorithms behind the
sums/subtractions/multiplications/divisions, then working her way up
to "higher functions" (square root, sin, cos,...) It has appeared to
be difficult to find information on the web referring specifically to
pocket calculators, in many instances it is not clear wether the
algorithms are meant for basic pocket calculators (which we are
looking for) or computers/highly developped calculators.

My student would have preferred to do her work on the calculator she uses (TI-30XS MultiView already a little further on than the basic models), but we were not able to find specific information on this model on the internet and Texas Instruments wasn't willing to share either, maybe because the model is too recent ?

Would you have any idea where my student could find information
related to algorithms used in pocket calculators ? It doesn't need to be detailed explanations, nor for any specific brand or model, right now we would be happy with anything just specific to pocket
calculators, even pure code text would be very helpful.

ANY IDEAS?

Regards,
Joerg


#22

Here is an article on transcendental function algorithms from the TI graphic products team you might want to take a look at:

ftp://ftp.ti.com/pub/graph-ti/calc-apps/info/cordic.txt

P.S.: Yet another one, in French:
http://www.jacques-laporte.org/LeSecretDesAlgorithmes.htm


Edited: 26 Apr 2013, 8:57 p.m.


#23

Quote:
Yet another one, in French: http://www.jacques-laporte.org/LeSecretDesAlgorithmes.htm

From the same source:
J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes. In: IBM Journal. April 1962.

#24

Cochran's patent: DIGITAL CALCULATOR SYSTEM FOR COMPUTING SQUARE ROOTS

#25

If she owns an iPhone I suggest to install rpn-21 which provides a debugger:

This allows to track a calculation and thus gives an impression of its complexity.

Kind regards

Thomas


#26

Y'know, as I have some of these RPN-Woodstock and RPN-Spice calcs on my iPhone, I've wondered what that code was. Now I know it's the debugger. Thanks for the explanation.

#27

The family of CORDIC algorithms are able to calculate square root, exponential, logarithm, trigonometric functions, and inverse trigonometric functions.

The heart of the CORDIC algorithm resembles a hi-low number guessing game.


Here is a good link for Matlab code that has the CORDIC implementations for the above functions.

Namir


#28

From SQRT_CORDIC:

  for i = 1 : n
poweroftwo = poweroftwo / 2.0;
if ( ( y + poweroftwo ) * ( y + poweroftwo ) <= x )
y = y + poweroftwo;
end
end

Probably not the most efficient way to do that.

Cheers

Thomas


#29

Very easy to read and understand, especially for a high school student.

Edited: 27 Apr 2013, 12:46 a.m.


#30

Given the task to produce a list of squares these are two ways to do it:

0      0      0 * 0     0
1 1 1 * 1 0 + 1
2 4 2 * 2 1 + 3
3 9 3 * 3 4 + 5
4 16 4 * 4 9 + 7
5 25 5 * 5 16 + 9
6 36 6 * 6 25 + 11

The left one uses multiplication and doesn't use the previous result. The right one reuses the previous result and thus needs only addition which is more efficient. I assume a high school student will understand both solutions.

But when somebody wants to know how a calculator works I prefer to point to the real thing. Because it's not Matlab code running within a calculator. But I like this example because it shows that it's worth to ask yourself: what do I know and how can I use that to improve my next step?


Kind regards

Thomas


#31

Does a high school student want to know the machine code for ANY calculator????? Really??????? If he/she does, then he/she is truly exceptional and should contact Cyrille who conveniently (for the Geneva student) lives near Geneva. Cyrille may well put that student on HP's R&D payroll.

I am not knowledgeable in machine code for any machine and I doubt the high school student in Geneva is either. However, I can understand the algorithm used. When that algorithm is expressed in high level languages like Matlab or Visual Basic, I can get a better grasp of it.

Namir

Edited: 27 Apr 2013, 10:08 p.m.


#32

Cyrille described the method to calculate the square root in HP Solve:

Quote:
hello,

the method used by all HO calculators from the 71 is described at: in the HP Solve: Volume 5 (June 2008) newsletter at: http://h20331.www2.hp.com/Hpsub/cache/580500-0-0-225-121.html

regards, cyrille


cf.
Computing Square Roots

Donald Knuth uses assembly language, which runs on the hypothetical MIX computer, to describe the algorithms in The Art of Computer Programming. And he has some good reasons to do so.
That's only one example where assembler is used as an educational programming language.

I don't mind a high level description of an algorithm. There's a nice flow-chart diagram in Cochran's patent which describes it best IMHO. There are different levels of understanding and some may be satisfied with that. But I think it's worth the effort to go one step deeper and then you might end up stepping through assembler code using a debugger. Hopefully this will give you a more profound understanding.

As source code was requested I pointed to the VASM listing. We are lucky that we have the original with comments in a searchable format. What else could you want?

Just hope you might take the occasion and start having a look at MCODE. After all it's not that difficult.

Kind regards

Thomas

#33

She ;-)

Joerg

#34

Quote:
even pure code text would be very helpful.

Coconut VASM Listing by Jackie F. Woldering

If she's not afraid of assembler it might be enlightening to compare the description of the algorithm in Cochran's patent with it's implementation in the HP-41C. Here's the core of the routine:

   279  336 SQR60  1042 C=C+1  PT
280 337 SQR70 716 A=A-C W
281 340 1763 GONC SQR60 ( 336)
282 341 516 A=A+C W
#35

TI-30XS MultiView is nit programmable !
It is a just a scientific calculator.

Here is a review of the calc :

http://www.calc-bank.com/index.php?mod=archives&ac=voir&id=841

#36

Inside Your Calculator: From Simple Programs to Significant Insights by Gerald R. Rising may be useful.

Link 1

Link 2


#37

Quote:
Inside Your Calculator: From Simple Programs to Significant Insights by Gerald R. Rising may be useful.

Link 1

Link 2



This is a good book, I will second this recommendation.

#38

From my understanding CORDIC is used for transcendental functions. (sin, cos, ln, e^x, etc)

As far as arithmetic is concerned (+, -, x, ÷), I believe binary representations of numbers are used to carry out these operations. An example for addition in an eight bit system: 17 + 54

17 in binary is 000010001
54 in binary is 000110110

The sum is 71, 71 in binary is 001000111

In a bit system, there is n-1 bits that are dedicated to number representation, with the left most bit being the "sign bit". If the sign bit is 1, the number is negative.

I found this video
2's Complement, 1's Complement, and Signed Magnitude by GroundhogGrafix to be helpful in understanding various ways negative numbers are interpreted, and why 2's Compliment is preferable.

Hope this helps,

Eddie


#39

Usually CORDIC isn't used for logs and exponentials, although it is possible to do so by using hyperbolic CORDIC. CORDIC is in the general class of shift-and-add algorithms, and there is a simpler one for logs and exponential first published in 1624, only ten years after the invention of logarithms by Napier. I'm not sure whether the HP 9100A (1968) used Briggs' algorithm, but all of HP's handheld and handheld-derived calculators from the HP-35 (1972) through the Saturn-based and Saturn-emulating calculators have used it. Recent HP-designed calculators such as the HP 10bII+, 20b, 30b, and 49gII apparently use a math library based on that from Saturn calculators, so they presumably also use Briggs' algorithm.

There is a good description of Briggs' algorithm on Jacques Laporte's "Briggs and the HP35" web page.

Another excellent reference for algorithms for transcendental functions is Elementary Functions: Algorithms and Implementations by Jean-Michel Muller, second edition, which covers many classes of algorithms including shift-and-add (Briggs', CORDIC, and others), and has especially good coverage of accurate argument range reduction algorithms.

It should be noted that the HP algorithms for sine and cosine use CORDIC, but not in the most basic method normally described. Instead, they compute the tangent (or cotangent), and use an identity to compute the sine (or cosine) from it. This avoids an issue with each CORDIC iteration effectively multiplying the resulting sine and cosine by a scale factor; by using tangent (or cotangent), these scale factors cancel out. In binary CORDIC, the number of CORDIC iteration is fixed, so the result can be multiplied by the inverse of the product of the scale factors, which is constant. In decimal CORDIC as implemented by HP, the number of CORDIC iterations is variable, so it would take more work to compensate for the non-constant product of the scale factors.

For specifics of the algorithms used by HP, see:


Edited: 27 Apr 2013, 1:04 p.m.

#40

Note that in binary floating-point arithmetic, two's complement representation is almost never used. For the significand (also known as the coefficient, and often incorrectly referred to as the mantissa), sign-magnitude representation is normally used, and for the exponent, a biased integer representation is normally used.

However, the BCD floating point used in most HP calculators uses ten's complement representation for the significand.


Possibly Related Threads...
Thread Author Replies Views Last Post
  An easy course in using the HP16c-wanted- Frank 4 407 10-29-2013, 11:50 AM
Last Post: Mark Hardman
  OT--TI-36X Algorithms Matt Agajanian 48 2,330 09-01-2013, 08:13 PM
Last Post: robert rozee
  HP 39gii Help Wanted: Inputting Strings in a Program Eddie W. Shore 0 164 02-09-2013, 02:17 PM
Last Post: Eddie W. Shore
  CAS beta testers wanted Oliver Unter Ecker 5 398 07-30-2012, 07:11 AM
Last Post: Oliver Unter Ecker
  OT: primitive mult/div algorithms Egan Ford 9 526 05-27-2012, 09:27 PM
Last Post: Egan Ford
  Help wanted SR-52 nina scholz 29 1,429 05-16-2012, 07:48 AM
Last Post: Anders Persson
  Hard or wanted CAS stuff Oliver Unter Ecker 9 524 04-16-2012, 04:32 AM
Last Post: Mike (Stgt)
  wanted: high-resolution photo of 50g internals Eric Smith 9 644 10-04-2011, 02:08 AM
Last Post: Marcus von Cube, Germany
  HP 15C LE - review wanted Jeroen Van Nieuwenhove 12 622 09-15-2011, 11:19 PM
Last Post: megarat
  Input wanted Paul Dale 30 1,348 06-24-2011, 01:59 PM
Last Post: David Hayden

Forum Jump: