Question about series

lemelinm's picture

Hi all,

I have been asked how a calculator works to calculate say exp(5) and did Maple use the same scheme.  I am sure it's a question of series but I am sure it's not a power series.  The question seemes stupid and I am ashamed for not knowing it but that's life.

 

Mario

Axel Vogt's picture

hm ...

showstat(`evalf/exp`) or showstat(`exp`)shows the code for floats or symbolics

Robert Israel's picture

hmmm ....

showstat(`evalf/exp`) is not that enlightening.  For floats, at sufficiently low settings of Digits, Maple just passes the computation off to evalhf, which uses the floating-point hardware of the system.  To see how exp is implemented there, you'll have to ask Intel, not Maple.  If Digits is too high to use evalhf, you want to look at `evalf/exp/general`. 

 

acer's picture

why series?

Why are you so sure that calculators all use a series approximation instead of, say, polynomial interpolation alongside table lookup, continued fractions, or a digit-by-digit method?

You might find BKM and CORDIC interesting.

acer

JacquesC's picture

Indeed

If I remember well, at low Digits, evalhf used either the built-in function (when the platform provides one which is accurate enough), or otherwise an approximation based on the (Horner form of) a polynomial interpolant.  I believe it also uses range reduction for arguments which are too small/too large.  But it has been a very long time, I could be misremembering.

alec's picture

Intel Math Kernel Library

Intel has a very good math library. I hope that it is used in Windows, Mac OS X and Linux for evalhf.

Alec

acer's picture

vector based

That does not make much sense for scalars, which were being discussed here, I think.

What might be useful is having map[evalhf] utilize the Vector Math (VML) subset of MKL.

One can observe that LinearAlgebra's hardware floating-point routines are linked to MKL on MS-Windows (32bit). On Linux, ATLAS is used for this. That and other packages get to MKL/ATLAS via Maple's external calling.

I would like to see external calling work directly under evalhf (without recourse to the new `eval` capability under evalhf, which seems to add a costly transition between hardware and scalar floats). The advent of option hfloat indicates movement in the other direction, toward faster float operations outside of evalhf. How that will pan out will be interesting.

Note that scalar hardware floats are now "first class citizens" in Maple, but not yet widely used. They might be used as the type for returns from external calling within evalhf, were it enabled. Or they might be used for such returns outside of evalhf (this is not yet so, I believe).

ps. Is it just me, or does this seem odd. Note the accuracy. Why isn't Digits=trunc(evalhf(Digits)) used within the HFloat constructor?

> HFloat(1./3);
                                 0.3333333333
 
> lprint(%);
HFloat(.333333333299999979)

acer

alec's picture

elementary functions

Elementary functions are also very good there. In particular, both exp and ln, as well as trigonometric functions, are much faster and with only slight loss of precision comparing to the OS (or C runtime library) functions.

Alec

alec's picture

Free software

So, much of Maple performance is obtained by using Free software, GMP and ATLAS?

What would happen if they changed their licensing from LGPL to GPL?

Alec

acer's picture

not much, in the short term

Not much would alter, in the short term, because current versions of those 3rd party software could be re-used. Now, when a new architecture comes along that is so radically different that it absolutely requires (for competitiveness) the latest and greatest, well that would be another story.

GMP is moving towards GPL with some new modularized version, I think. (One plugs in the module, for a new architecture, or something.) So that could be interesting. Never totally catastrophic though, as Maple had its own proprietary scheme (in use until Maple 8, though not as good a performer in the limit). But if machines started to have 100s of cores, and GMP had great multicore support... then who knows? Maplesoft had the skill to implement a proprietary scheme once (relatively good, when it first arrived), and maybe they could do so again, but threaded.

For fast vendor BLAS, there seems to always be someone selling one. If you check out the MKL cost, it's not prohibitive if I recall correctly. Maple already uses MKL on Windows, and I've heard (or read) that that platform is by far the biggest part of the Maple customer base.

I'm not sure that it's accurate to say that most of Maple's performance relies on such things. But the portion that does is becoming more important, from a pure number crunching point of view.

The MKL part on Windows, already in use, is not free software. And ATLAS is not under LGPL, is it?

acer

alec's picture

ATLAS

Acer,

For some reason, I thought that it was LGPL. It is BSD - wow, that's much better! Great that you mentioned that.

Thinking that it was LGPL, I didn't use it in one of my recent projects. I should have checked that. Now I'll get some improvements there (I hope.)

Alec

BSD vs. GPL

I have always found BSD-style licenses refreshingly simple compared to the GPL.

Ideological issues aside,  BSD licenses also seem much more in the spirit of academic work.

alec's picture

Licensing

Personally, I prefer BSD type licensing, too. As well as many other people in academia.

For math software, people usually choose GPL specifically to prevent including their work in commercial CASs.

Actually, what I thought about that - Maple could use it in its own interests - it could become GPLed itself, include all free GPLed software, and still continue being commercial. If there were many useful GPLed packages, that would make sense - that would give it an advantage comparing to other CAS (the same advantage that SAGE has now, being GPLed.)

Alec

PS After reading that, I realized that I am following Mehran Basti more and more. I already give advices to Maple owners and executives. The next step, probably, would be to start giving advices to Canadian goverment, and then, gradually, I might rise to advising Vatican and Turkey. -Alec

Axel Vogt's picture

on & off topic

nice sense of humor :-)

for licensing: that open source licensing is a pain i.t.a. for commercial companies, for
every piece of shit you will need a laywer then and documentation or maintanance is
something to be thought before as well

SAGE is a bit of exception, I think - if you look at the GNU GSL you see a kind of converse
(certainly it is carefully maintained): if you are a Windows user you are left alone ...

BTW: I think it is already non-trivial to be sure, that you can provide a commercial interface
from a commercial SW to a GPLed SW *without* opening beyond the interface.

But personally you are free to give an interface Maple <---> SAGE.

 

Still not quite understand the origin of the question ...

lemelinm's picture

The starting point was

 How a calculator like TI83 calculate to give the answer of exp(5.2) or ln(3.4) etc.  For what I understand on this long exchange, is that it seems that there is a look-up table and with a hardware code, can give the exact answer starting with the table.  I was more interested in a simple way to show an exemple to the students.

 

I thought , and you show me that itI was false, that you could have a serie in the form of:

exp(n) = Sum(term containing "n") and that the more precise you want, you only have to take a further number of term.

But the level of your answer is far too high level for the students I was working with.

Anyway, thanks for those precises anwers.

acer's picture

remez

Maybe the students could appreciate the exp() example from the ?numapprox[remez] help-page?

I notice, in passing, that it's not obvious how to get the help-page ?array in the commandline and Classic interfaces. Issuing ?array gets to the ?Array help-page. It turns out that it can be obtained by instead querying for the help-topic,

array(deprecated)

There doesn't appear to be a link to ?array(deprecated) from ?Array. The only mention of the deprecated array in ?Array is not an active help-link.

But numapprox[remez] still needs an array, and doesn't accept an Array, for the critical points argument. There's no link from ?numapprox[remez] to ?array(deprecated) either.

acer

alec's picture

good old thing

remez is another one good old thing practically getting deprecated because arrays got deprecated. If I am not mistaken, it was developed by Keith Geddes and/or his students (I remember a couple of articles about that algorithm written by him/them.) Is there an analog of that for Arrays?

Alec

acer's picture

simple update

Yes, numappox[remez] needs to be updated to accept both array or Array, for its 'crit' parameter.

I wouldn't be suprised if its access of array elements is straightforward enough that it's just a question of argument checking adjustment.

For now, if one has an Array, then passing it as convert(...,'array') should suffice.

I believe that you are right, that it was implmented in Maple by K.Geddes and/or his grad student(s). As you probably know, Remez was Russian.

acer

alec's picture

K. Geddes

I learned a lot from K. Geddes when I used to post in the Maple newsgroup. He didn't post often, but everything that he posted was very useful.

In particular, I started using eval instead of subs after his post with an explanation why it is better.

Also, I used to end procedures with evaluating the returned value. That was necessary for arrays, in particular. He explained to me that it is not necessary for Arrays, and provided some additional information about Arrays which was not in the help pages, I think.

There were many other cases - these 2 were the first that came to mind - and his name comes often to my mind when I use eval.

Alec

Axel Vogt's picture

may be like this?

May be the following is towards what you have in mind, I once did that
in Visual Basic (for Excel to get values for negatives more exact), it
should be understandable: to get exp(x) one takes a presentation in
base 2, for higher powers one uses stored, pre-computed values and for
the rest - which is close to 0 - the Taylor series should do.

So it is done by a quite brute argument reduction.

  Attribute VB_Name = "Modul2"
  Option Explicit
  Option Base 0
  
  Function ExpExcel(x As Variant) As Variant
  ExpExcel = CStr(CDec(Exp(CDec(x)))) ' hat nur 15 Stellen
  End Function
  
  Function localExp(x As Variant) As Variant
  Dim i, j As Integer
  Dim absx As Variant
  Dim intx, fracx As Variant
  Dim binx(0 To 5) As Integer
  'Dim eps(0 To 5) As Integer
  Dim z, b, pow As Integer
  Dim v(0 To 6) As Variant
  Dim expintx As Variant
  Dim F(0 To 32) As Variant
  Dim sum As Variant
  Dim tst
  
  If (0 < x) Then
    localExp = Exp(x)
    Exit Function
  End If
  If (x <= -64) Then
    localExp = Exp(x)
    Exit Function
  End If
  
  ' -64 < x <= 0
  
  pow = Int(5)
  
  v(0) = CDec(0.367879441171442) + CDec(0.3215955237702 * 0.000000000000001)
  v(1) = CDec(0.135335283236612) + CDec(0.691893999495 * 0.000000000000001)
  v(2) = CDec(0.018315638888734) + CDec(0.1802937180213 * 0.000000000000001)
  v(3) = CDec(0.000335462627902) + CDec(0.5118388213891 * 0.000000000000001)
  v(4) = CDec(0.000000112535174) + CDec(0.7192591145138 * 0.000000000000001)
  v(5) = CDec(0.000000000000012) + CDec(0.6641655490942 * 0.000000000000001)
  v(6) = CDec(0#) + CDec(0.0000000000002 * 0.000000000000001)
  
  absx = -CDec(x)
  intx = Int(absx)
  fracx = CDec(absx - intx)
  
  ' binary
  z = intx
  b = 32 ' Int(2 ^ pow)
  tst = ""
  expintx = CDec(1)
  For i = pow To 0 Step -1
    binx(i) = Int(z / b)
    If (binx(i) = 1) Then
      expintx = expintx * CDec(binx(i)) * v(i)
    End If
    'tst = tst & CStr(i) & ": " & CStr(binx(i)) & " "
    z = z - binx(i) * b
    b = Int(b / 2)
    'tst = tst & CStr(binx(i))
  Next i
  'MsgBox (tst)
  
  F(0) = CDec(1)
  For i = 1 To 32
    F(i) = -fracx * CDec(F(i - 1)) / CDec(i) ' Mist: 7<a: berechnen!
    'sum = sum + F(i) * h ^ i
  Next i
  
  'Horner Form
  sum = CDec(0)
  For i = 0 To 32
    sum = CDec(F(32 - i) + sum)
  Next i
  
  
  localExp = CStr(expintx * sum)
  
  End Function

CDec is a data type, which is more precise than usual floats, but the
use is a bit limited - especially one has to convert to strings to see
it in full length in Excel sheets.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}