flat assembler
Message board for the users of flat assembler.

Index > Main > transcendental functions

Author
Thread Post new topic Reply to topic
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
Hi,

I am into natural logarithm and trigonometric tan function approximations for normal f64 numbers, assembly implemented ofc (probably AVX2 FMAs for polynomial calculations).

I had a look at glibc libm, and IBM(redhat) did so bad at documenting it, I would like to avoid to reverse engineer their maths from the source (their tan is scary, and I prefer not to talk about their abuse of GNU symbol versioning).

Is there an international "something " which maintains the "best" way to approximate transcendental functions for normal f64 numbers? IEEE does not do that for their number formats???

I may end-up hand-compiling parts of mpfr and/or parts of libbf(bellard) namely go multiprecision with a f64 conv at the end.
Post 13 Jan 2022, 21:34
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 18643
Location: In your JS exploiting you and your system
revolution
Are you aware of fptan?

It doesn't give the full four quadrant result. Some extra processing is required if you need that.
Post 14 Jan 2022, 00:53
View user's profile Send private message Visit poster's website Reply with quote
Hrstka



Joined: 05 May 2008
Posts: 33
Location: Czech republic
Hrstka
You can take a look at the SLEEF Vectorized Math Library, if that's what you mean.
Post 14 Jan 2022, 08:51
View user's profile Send private message Reply with quote
Ville



Joined: 17 Jun 2003
Posts: 253
Ville
SLEEF is also available in Menuet64 in assembly.

System call 151.
http://menuetos.net/syscalls.txt
http://www.menuetos.net/sc151.html
Post 14 Jan 2022, 11:13
View user's profile Send private message Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
@revolution: yeah, range reduction. It seems IBM is doing many range reductions in their glibc/libm tan over [0,PI/2[. For trigonometric functions, no worries, but for the natural logarithm I guess I may need to find papers about good range reductions. I try to move away from x87.

@hrstka,@villeBut: menuet64 is "close" source then is their assembly port of SLEEF.

I would like to be able to "check" their maths, namely double check the proof of their precision ("ulp" related).
Namely for each approx methods: Chebychev(Remez), Padé, raw Taylor, arithmetic/geometric mean, I would need to get my eyes on papers on proof of their precisions ("ulp"). I think it is more maths than assembly, but to see explicitely those maths applied for some code, you know, to understand where it comes from. I recall vaguely in the case of raw Taylor, the "remainder" theorem which allows to do just that.

Why such important stuff is so hard to find on internet???

Yep, after furter investigation, before going assembly port/hand-compilation of the code of a tan/log approximant, I need to double check their "ulp" mathematical proof. Getting my hands on sleef to see if I can do just that: for the moment, sleef documentation is the less worse I could read, but it still throws a lot at our face. It seems there is no proof, just "good enough"/empirical polynomial coefficients computed via many points over a "reduced" range using the simplex (linear programming) algorithm to minimize the relative error to the output of very high precision numbers from mpfr.
It seems to explain why many math libs are doing "their own thing".
The elephant in the room is they are doing a huge mistake by being very dependant on the worst part of optimizing compilers. This project should be pure assembly for each targeted arch with at best a generic simple C89 with benign bits of c99/c11 implementation.
ofc, I did forget about the numerical stability discussion of their approximant, nowhere to be found... wild guess: this is "common knowledge" in the numerical analysis field.
Post 14 Jan 2022, 15:21
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 227
donn
If you're looking to test out some transcendental functions, I made a couple a while ago just for my own purposes. They're not optimized and were only meant for me to get answers that matched a calculator to a certain precision.

If you are familiar with Calculus, Gregory's Series, Maclaurin's Series, they are just derived from that, and I could definitely explain them. Think arctan contains a comment of the formula it's modelling.

https://github.com/hpdporg/datap/blob/master/src/main/asm/Numeric/Transcendental.inc
Post 20 Jan 2022, 05:53
View user's profile Send private message Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
well, I am looking for the following proofs: the proof of the numerical stability of their approximant of tan/log transcendental functions and the proof of their accuracy at a specific precision.

Since those proofs do not seem to be provided, I was expecting those as common knowledge then easy to find on internet.

Well, I am wrong or bad at searching because I am unable to find those.
Post 23 Jan 2022, 17:41
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 227
donn
OK, so not so much 'how calculating transcendental functions work,' but more 'prove to me their accuracy and error.'

Taking just the Taylor Series and related variants i.e. Maclaurin, you have a convergent series, and the error is pretty obvious if you calculate separately by hand, there are obvious decimal places which differ. The accuracy will noticably increase as you add more terms in the infinite expansion.

So, proofs to calculate the error and precision analytically can be found by searching things like 'convergence of taylor series:'

Last page, 'Estimating the Remainder':
https://users.math.msu.edu/users/gnagy/teaching/12-spring/mth133/L34-133.pdf

Page 21 Proof of Taylor Series:
https://sam.nitk.ac.in/courses/MA111/Convergence%20of%20Taylor%20Series.pdf

Similar proofs of Chebyshev should be searchable.

In practice, there are ways to speed up the calculations by doing things like caching values, using lookups. This diverges a bit from the pure mathematical theory and yeah, is harder to find. More pure math theory answers may be easier to obtain on physicsforums if there are particulars you are trying to understand. Not sure if they answer pure math questions, but they're pretty good and responsive on analytic physics of any subject.


Description:
Filesize: 282.01 KB
Viewed: 2625 Time(s)

ProofTaylor.JPG


Description:
Filesize: 284.05 KB
Viewed: 2625 Time(s)

EstimatingRemainder.JPG


Post 23 Jan 2022, 18:34
View user's profile Send private message Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
This is the proof of the mathematical pure taylor series convergence, this is not what I have been looking for.

I am talking about proofs about their approximant using floating point numbers. Namely, proof that their approximant is numericaly stable, and proof about the accuracy of their approximant towards the original transcendental function.

Those proofs are probably specific to each math lib because most math libs do their own thing.

In other words:

Proof that, for all floating point numbers in "this" range (range reduction), "this" very polynomial, with those _floating point coefficients_, will provide an approximant of "this" transcendental function for a floating point number in our "range" to the "best" "this" floating point format can do.
Post 23 Jan 2022, 21:12
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 227
donn
Scanning over your questions, thought you were asking for precision of "raw Taylor." Trigonometric functions can be directly derived from this series as I sent previously.

Quote:
Namely for each approx methods: Chebychev(Remez), Padé, raw Taylor, arithmetic/geometric mean, I would need to get my eyes on papers on proof of their precisions ("ulp").


If you want more efficient algorithms, the GNU Scientific Library provides their list of references:

https://www.gnu.org/software/gsl/doc/html/specfunc.html#references-and-further-reading

Which contains a link to a book that has Matlab of trigonometric functions:

W.J. Thompson, Atlas for Computing Mathematical Functions, John Wiley & Sons, New York (1997).

https://www.amazon.com/exec/obidos/ASIN/0471181714/acmorg-20

With extensive references and indexing, this integrated package is superbly designed and easy to use--ideal for anyone who works with special functions. Contents include:
* Elementary Transcendental Functions


Math functions are calculated from theory. If you're looking for an even more tailored explanation of an implementation's precision:

https://www.mpfr.org/algorithms.pdf

And further efficiency gains:

https://fredrikj.net/blog/2017/09/faster-exp-sin-and-cos-at-high-precision/
Post 23 Jan 2022, 23:48
View user's profile Send private message Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
Yep, I was refering to approximants based on raw Taylor series, not pure maths raw Taylor series. Good we are now on the same page.

I was already lurking on the GNU scientifc library and mpfr in order to get such approximants numerical stability and accuracy proofs. Usually, we get thrown at our face the approximant algorithms without any rigorous proofs or references to proofs.
Going to have a look, hope I'll be able to easily find those (yes, it should be very ez).
I don't want to hand compile approximant algorithms without those proofs, kind of obvious common sense I guess.

[offtopic: I have been too often disappointed by the knowledge system based on physical books (very limiting, too few alternatives and astonishly expensive for a individual).
Browsing PDF files (version max 1.4, 1.7, yes microsoft, them again, f****ed version 2.0 with script) with proper indexe(S) to search into, and noscript/basic (x)html web pages (aka wikipedia) is the way to go.]

I started with mpfr proofs, 2nd paragraph, Exp not rigorously defined right away: you have to search the pdf to find 2 contradicting definitions (one is the right one). Missing explanations (bijection proof I guess) of the "exponent based value" of a non-zero x.This should not be that hard, but since *EVERYTHING* is based on that, it should have been explicit and accurately detailed immediatly in this paragraph. I am lucky to vaguely remember that from my maths lectures decades ago.
Those 70 pages are probably going to be an accute pain to go thru, rigorously.
Post 24 Jan 2022, 16:02
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 227
donn
OK, yeah I wasn't expecting them to list the performance and precision of their functions in this much detail. Projects like Blender seem to have very little documentation in their physics solvers, but maybe mpfr is more serious or the docs actually exist if I looked.

Definitely useful to understand, I might read up on these some day in the future (page 16):

Quote:

.1. The cosine function. To evaluate cos x with a target precision of n bits, we use the
following algorithm with working precision m, after an additive argument reduction which reduces x in the interval [−π, π], using the mpfr remainder function:
k ← ⌊pn/2⌋ r ← x2 rounded up r ← r/2 2k s ← 1, t ← 1 for l from 1 while exp(t) ≥ −m
t ← t · r rounded up t ← t (2l−1)(2l) rounded up s ← s + (−1)l t rounded down 16
do k times s ← 2s 2 rounded up s ← s − 1 return s The error on r after r ← x 2 is at most 1ulp(r) and remains 1ulp(r) after r ← r/2 2k since that division is just an exponent shift. By induction, the error on t after step l of the for-loop is at most 3lulp(t). Hence as long as 3lulp(t) remains less than ≤ 2
−m during that loop (this is possible as soon as r < 1/
√ 2) and the loop goes to l0, the error on s after the for-loop is
at most 2l02 −m (for |r| < 1, it is easy to check that s will remain in the interval [ 1
2 , 1[, thus ulp(s) = 2−m). (An additional 2−m term represents the truncation error, but for l = 1 the value of t is exact, giving (2l0 − 1) + 1 = 2l0.) Denoting by i the maximal error on s after the ith step in the do-loop, we have 0 = 2l02
−m and k+1 ≤ 4k + 2−m, giving k ≤ (2l0 + 1/3)22k−m.
Post 26 Jan 2022, 04:56
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 18643
Location: In your JS exploiting you and your system
revolution
That looks similar to the CORDIC algorithm.
Post 26 Jan 2022, 05:11
View user's profile Send private message Visit poster's website Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
Ok, I got back on mpfr paper of "proofs". This is probably mathematically correct but this is disgusting maths work. Some "proofs" are bluntly missing, not reasonably complete, or hidden behind an "obvious" ("obvious" is forbidden in a maths paper since something is "obvious" only with the same amount of practice and experience of this very math domain).
Post 04 Feb 2022, 14:01
View user's profile Send private message Reply with quote
donn



Joined: 05 Mar 2010
Posts: 227
donn
https://www.mpfr.org/#mpfr-links
Mailing-list for users and developers. Note: to post to the list, you cannot use the web interface, just send a mail to mpfr at inria.fr (and please, for a new thread, do not reply to an existing message; changing the subject is not sufficient).

They have a mailing list in link above. Not sure how active their list is, but maybe they can provide more info on certain topics of their proofs. Scanned through the mpfr doc, could have good info in it, hard to tell so far though.
Post 04 Feb 2022, 19:01
View user's profile Send private message Reply with quote
sylware



Joined: 23 Oct 2020
Posts: 125
Location: Marseille/France
sylware
Dunno what I going to do. I want to throw the baby with the water: I don't want to keep reading this paper. Maybe it is because I am too lazy/bad and this gives me an excuse not to re-proove the very little maths they use.
At least, there is no "javascript only web page" to interact with them. Hope they don't use spamhaus block list and provide at least grey listing on their email server (as it should be).

edit:
I cannot do it. This piece of "work" disgusts me too much, my "lazy/bad at maths" me won. But I know that all maths teachers I had would send to hell such "paper".
I guess I'll choose an implementation and trust it, that without a document of "explicit-enough-for-me" and clean maths proofs.
Post 04 Feb 2022, 19:13
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.