How does the calculator actually work?

[vic9317]

So I got to thinking recently about how computers/calculators have become pretty quick when it comes to calculating things. I was wondering how the calculator actually does this. For example, per TI|BD, I know that the fnInt( function uses the Gauss-Kronrod method to approximate definite integrals (though I don't nearly have enough math experience to understand what that method is exactly). Another example: the rand command uses L'Ecuyer's algorithm to generate its pseudorandom numbers.

What about simpler functions, like abs(? I'd imagine the calculator just follows a simple routine, right? But what about other commands, i.e. normalcdf( or even sin(? How does the calculator even calculate something like 3^8.329 or ln(4)? Naturally, I assume that these all come down to some advanced approximation methods, do they?

Pardon me if I'm asking too many questions, I'm just curious. :P

If there are any reading materials that might shed some light on the matter, could you please provide links to them? If you do decide to answer with a lengthy response, however, I shall be extremely grateful.

[Xeda112358]

How familiar are you with assembly? That would make it easier to answer some questions. I think the abs( command is the easiest command of the ones you mentioned, so I will explain that one real quick (I'm a tad sleepy). Real numbers use 9 bytes. The first two bytes have info that tells if it is negative/positive, imaginary/real, and the power and decimal location. If bit 7 of the first byte is set, the number is negative, otherwise it is positive. For a real number, you simply reset that bit and it is positive.

[DrDnar]

The calculator use BCD, Binary Coded Decimal, so it does a lot a math the same way you'd do it by hand. I don't know how exactly the EOS calculates sine values, but one popular way is to use Taylor series. Although a Taylor series is infinite, a reasonably small finite polynomial can yield a surprisingly accurate approximation. For example,
x - x^3/3! + x^5/5! - x^7/7! is accurate to five decimal places for -1 < x < 1. There is, in fact, a specific algorithm for computing sine that's based on Taylor series and is optimized for CPUs without multiplication and division instruction.

[Impiety]

The answer to your question "how does the calculator work" can either be abstract and simple or insanely complex. There are multiple different levels of understanding involved, so how your question is answered depends on how deep you want to delve into the matter. The programming language you're familiar with, TI-BASIC, is a high-level language - ultimately, it must be converted somehow into low level language (assembly) in order to function; in this instance through an interpreter. However, assembly, in turn can be broken down to machine language, which can be broken down to circuits, buses and registers, which can be broken down to Chemistry, which can be broken down to Physics, etc.

For more info on assembly, you can download Lean TI-83+ Assembly in 28 days here.

Don't be afraid to ask questions, too . It's not like this site gets a whole lot of traffic anyway - we need all the activity we can get.

[Xeda112358]

Well said Also, now that I am a little more awake, I can answer some more... The calculator actually has the value of pi/4 or some constant like that stored in memory somewhere, so that is probably loaded into memory somewhere and basic math can be performed on it. However, for sin/cos and whatnot, a Taylor series is likely used (as Dr. D'nar said). A lot of calculus and number theory is used to create math functions and stuff gets really fun when you are working in binary or hex

[vic9317]

[FloppusMaximus]

Trig functions are calculated using a table-based method called CORDIC. See http://www.ticalc.org/archives/files/fileinfo/14/1416.html for some information that was released by TI many years ago. It's old, but most of the algorithms used by the Z80 models haven't changed substantially since the TI-85 (many of them haven't changed since the TI-81!)

[Xeda112358]

Haha, cool! I have used CORDIC before to make trig functions... that stuff is a little tricky x.x
Anywho, for the most part, algorithms are used to calculate things and some of those algorithms are actually pretty cool and may surprise you. If you remember way back in grade school you probably learned longhand multiplication. That is actually how the calc multiplies. I am not sure of how it is done with BCD exactly, but I do know how it is done in straight binary/hex. I have had a little experience with making programs that perform simple operations...

[FloppusMaximus]

Hmm. I've never actually looked at how the multiplication routine works. Let's take a look...

...and WOW, that's inefficient. :P

Worth keeping in mind: the time taken to perform an FPMult doesn't depend on the contents of OP1 (unless OP1 is zero), but it depends greatly on OP2 (the number of additions performed is proportional to the sum of the digits of OP2; the number of shifts performed is proportional to the position of the last nonzero digit.) So if you have a choice, put the "simpler" of your two numbers in OP2.

[Xeda112358]

Oh wow, that is good to know! I have only worked with BCD a little and I've only ever done addition and subtraction :/

[thornahawk]

People who are curious as to the simpler functions of the calculator (e.g. computing rational powers or CORDIC for the trigonometrics) should have a peek at Rising's Inside Your Calculator; the book gives a (more or less) simple explanation for what goes under the hood.

The stuff on L'Ecuyer's algorithm was teased out in one of those threads in the TI-Basic subforum; I believe I also left a link to the original paper by Pierre L'Ecuyer there.

As for Gauss-Kronrod... it's a bit tricky; suffice it to say that it's a so-called "adaptive quadrature" method, where the interval of integration for the function being integrated is recursively split up such that in sections where the integrand is "steeper" more function evaluations are done in computing the integral.

The basic quadrature rule underlying the adaptive Gauss-Kronrod method, just like the usual trapezoidal and Simpson's rule methods, evaluates the integrand at certain points and computes a "weighted average" of those values, but instead of the equal spacing in the trapezoidal and Simpson's rule methods, the integrand is evaluated at the roots of two special polynomials (the Legendre and Stieltjes polynomials), which are then used to compute two estimates of the integral (thus, the error estimate is the difference between these two estimates). If the estimate is too "large" (depending on how the error tolerance was set), the interval is split up; otherwise, the result is added to a running total. The method stops when all the sub-intervals have "small" enough error estimates, or when "too many" function evaluations have already been done without meeting the error tolerance.

(I had written a TI-BASIC routine to generate the basic Gauss-Kronrod rules a few years ago; they are a bit long, and I'll post them only if there's interest.)

thornahawk

[vic9317]

Wow! Great stuff! I'll be sure to take a look at everything.

Thanks guys.