[9fans] circular fonctions: precision?

[9fans] circular fonctions: precision?

[tlaronde]

Hello,

Is there some documentation about the precision of the circular (i.e
trigonometric) fonctions, depending on the (plan9) implementation and
the hardware?

To my limited knowledge, an OS is integer based, so the floating
point support is mainly "user space" and is, despite IEEE754 and due to
the interaction between hardware, software, and programmer, really
floating, but is there a range given for the association of OS/hardware
telling that say sin(r) or asin(s) is accurate, at worst, at some
epsilon near?

To give a context, say you have arcs connected to nodes, and each node
has information about its connected arcs sorted by angle (2D). If I
want to
find the "straightest" arc continuing arc A through node N, I look for
an arc B so that the angle between A and B is nearest to M_PI. But if
the angles (from the node) had been computed by some circular fonction,
even two originally "straight" arcs may present an angle not exactly
M_PI, due to precision. Hence the question.

Cheers,
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Sun, 02 Oct 2011 18:38:00 +0200 tlaronde@polynum.com  wrote:
> Hello,
>
> Is there some documentation about the precision of the circular (i.e
> trigonometric) fonctions, depending on the (plan9) implementation and
> the hardware?

Do you mean precision (number of significant bits) or accuracy
(closeness to true value)? For a double the precision is 52
bits, for a float 23.

> To my limited knowledge, an OS is integer based, so the floating
> point support is mainly "user space" and is, despite IEEE754 and due to
> the interaction between hardware, software, and programmer, really
> floating, but is there a range given for the association of OS/hardware
> telling that say sin(r) or asin(s) is accurate, at worst, at some
> epsilon near?

It depends on the algorithm used, not on the OS. The C
standard leaves accuracy upto the implementation. If you care,
you can compare the result of a C function with what bc(1)
computes for the same function (by using a suitably large
scale).

Re: [9fans] circular fonctions: precision?

[erik quanstrom]

> > To my limited knowledge, an OS is integer based, so the floating
> > point support is mainly "user space" and is, despite IEEE754 and due to
> > the interaction between hardware, software, and programmer, really
> > floating, but is there a range given for the association of OS/hardware
> > telling that say sin(r) or asin(s) is accurate, at worst, at some
> > epsilon near?
>
> It depends on the algorithm used, not on the OS. The C
> standard leaves accuracy upto the implementation. If you care,
> you can compare the result of a C function with what bc(1)
> computes for the same function (by using a suitably large
> scale).

unless the hardware doesn't actually have floating point, doesn't
this depend only on the hardware?  (c.f. /sys/src/libc/386/387/sin.s)

754 defines the results to be accurate to within 1 bit.  obviously
that's as good as you can get.  minix's math(3) points to a collection
of detailed man pages on the subject.

- erik

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Sun, Oct 02, 2011 at 10:52:27AM -0700, Bakul Shah wrote:
> On Sun, 02 Oct 2011 18:38:00 +0200 tlaronde@polynum.com  wrote:
> > Hello,
> > 
> > Is there some documentation about the precision of the circular (i.e
> > trigonometric) fonctions, depending on the (plan9) implementation and
> > the hardware?
> 
> Do you mean precision (number of significant bits) or accuracy
> (closeness to true value)? For a double the precision is 52
> bits, for a float 23.

Sorry, I meant accuracy.

> 
> > To my limited knowledge, an OS is integer based, so the floating
> > point support is mainly "user space" and is, despite IEEE754 and due to
> > the interaction between hardware, software, and programmer, really
> > floating, but is there a range given for the association of OS/hardware
> > telling that say sin(r) or asin(s) is accurate, at worst, at some 
> > epsilon near?
> 
> It depends on the algorithm used, not on the OS. The C
> standard leaves accuracy upto the implementation. If you care,
> you can compare the result of a C function with what bc(1)
> computes for the same function (by using a suitably large
> scale).

Here, I mean by "OS" not the kernel, but the whole soft-system, i.e.
here the implementation of libc and the direct use of sin(3) etc.

It seems you've answered my badly formulated question: if I want
to know exactly what I use, I must rely on some defined library
linked against my software that implements directly the fonctions.
(Testing against bc(1) is probably worth for having an idea; but
the problem is that 1) the results depend on the system/implementation;
2) there may be singularities and testing the whole range with a
small granularity is probably not an option.)

I sometimes wonder if the more common 64bits will not someday see
CAD or related software go back to scaled integer arithmetic à la
Intergraph dgn, where 64bits is enough for the range of coordinates
and precision used...

Thanks for the answer.
-- 
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Sun, 02 Oct 2011 14:06:48 EDT erik quanstrom <quanstro@labs.coraid.com>  wrote:
> > > To my limited knowledge, an OS is integer based, so the floating
> > > point support is mainly "user space" and is, despite IEEE754 and due to
> > > the interaction between hardware, software, and programmer, really
> > > floating, but is there a range given for the association of OS/hardware
> > > telling that say sin(r) or asin(s) is accurate, at worst, at some
> > > epsilon near?
> >
> > It depends on the algorithm used, not on the OS. The C
> > standard leaves accuracy upto the implementation. If you care,
> > you can compare the result of a C function with what bc(1)
> > computes for the same function (by using a suitably large
> > scale).
>
> unless the hardware doesn't actually have floating point, doesn't
> this depend only on the hardware?  (c.f. /sys/src/libc/386/387/sin.s)
>
> 754 defines the results to be accurate to within 1 bit.  obviously
> that's as good as you can get.  minix's math(3) points to a collection
> of detailed man pages on the subject.

IEEE754-1985 didn't specify circular, hyperbolic or other
advanced functions. You can have 754 compliant hardware and
not implement these functions. In any case the standard can
not dictate the accuracy of functions not specified in it. An
iterative algorithm may lose more than 1 bit of accuracy since
iterations won't be done in infinite precision. One can not
assume accuracy to a bit even where these functions are
imeplemented in h/w.  For x86, accuracy may be specified in
some Intel or AMD manual.

Re: [9fans] circular fonctions: precision?

[erik quanstrom]

> IEEE754-1985 didn't specify circular, hyperbolic or other
> advanced functions. You can have 754 compliant hardware and
> not implement these functions. In any case the standard can
> not dictate the accuracy of functions not specified in it. An
> iterative algorithm may lose more than 1 bit of accuracy since
> iterations won't be done in infinite precision. One can not
> assume accuracy to a bit even where these functions are
> imeplemented in h/w.  For x86, accuracy may be specified in
> some Intel or AMD manual.

that wasn't my reading of the spec.  so you're saying that if
the iterative algorithm loops 53 times, it's free to return any
answer whatever and still be compliant?

- erik

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Sun, Oct 02, 2011 at 02:06:48PM -0400, erik quanstrom wrote:
>
> 754 defines the results to be accurate to within 1 bit.  obviously
> that's as good as you can get.  minix's math(3) points to a collection
> of detailed man pages on the subject.

Does 754 define the precision of circular functions? I have only, on a
draft copy, the algebraic operations?

--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Sun, Oct 02, 2011 at 08:44:59PM +0200, tlaronde@polynum.com wrote:
>
> Does 754 define the precision of circular functions? I have only, on a
                      ^^^^^^^^^
> draft copy, the algebraic operations?

accuracy... My english wording is not accurate enough...

--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[andrew zerger]

[-- Attachment #1: Type: text/plain, Size: 1038 bytes --]

 havent read any of these specs but im sitting here thinking that bits on a
processor that can subtract == more preicision ..

On Sun, Oct 2, 2011 at 12:44 PM, erik quanstrom <quanstro@quanstro.net>wrote:

> > IEEE754-1985 didn't specify circular, hyperbolic or other
> > advanced functions. You can have 754 compliant hardware and
> > not implement these functions. In any case the standard can
> > not dictate the accuracy of functions not specified in it. An
> > iterative algorithm may lose more than 1 bit of accuracy since
> > iterations won't be done in infinite precision. One can not
> > assume accuracy to a bit even where these functions are
> > imeplemented in h/w.  For x86, accuracy may be specified in
> > some Intel or AMD manual.
>
> that wasn't my reading of the spec.  so you're saying that if
> the iterative algorithm loops 53 times, it's free to return any
> answer whatever and still be compliant?
>
> - erik
>
>


-- 
⎼⎺⎺├@┼␊├├≤-␍⎼␊▒␍:/␤⎺└␊/⎼␤⎺#

[-- Attachment #2: Type: text/html, Size: 1444 bytes --]

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Sun, Oct 02, 2011 at 02:44:35PM -0400, erik quanstrom wrote:
> > IEEE754-1985 didn't specify circular, hyperbolic or other
> > advanced functions. You can have 754 compliant hardware and
> > not implement these functions. In any case the standard can
> > not dictate the accuracy of functions not specified in it. An
> > iterative algorithm may lose more than 1 bit of accuracy since
> > iterations won't be done in infinite precision. One can not
> > assume accuracy to a bit even where these functions are
> > imeplemented in h/w.  For x86, accuracy may be specified in
> > some Intel or AMD manual.
>
> that wasn't my reading of the spec.  so you're saying that if
> the iterative algorithm loops 53 times, it's free to return any
> answer whatever and still be compliant?

There is a document titled "What Every Computer Scientist Should know
About Floating Point Arithmetic", by David Goldberg that states
precisely this: IEEE754 standardized what could be standardized, and
only that. There are many lengths of rope left...

Hence my question to know if "someone" has specified that, for the plan9
implementation, even if the implementation of the circular functions
has no uniq accuracy, at least for the domain of definition and whatever
hardware, the answer is not inaccurate of more than some defined
epsilon. (That could be enough for the range of geographic coordinates,
in my case.)

--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Sun, 02 Oct 2011 20:28:46 +0200 tlaronde@polynum.com  wrote:
>
> Here, I mean by "OS" not the kernel, but the whole soft-system, i.e.
> here the implementation of libc and the direct use of sin(3) etc.

I meant only the kernel but with your definition, yes.

> It seems you've answered my badly formulated question: if I want
> to know exactly what I use, I must rely on some defined library
> linked against my software that implements directly the fonctions.
> (Testing against bc(1) is probably worth for having an idea; but
> the problem is that 1) the results depend on the system/implementation;
> 2) there may be singularities and testing the whole range with a
> small granularity is probably not an option.)

Portability, accuracy and speed. Can't have all three!  If you
are lucky you get two out of three :-)

Alternatively you can figure out what accuracy you can live
with and see if you can get it cheaply and efficiently.

Comparison with bc for a few (random) values only to tell you
how good are the libraries. There are probably numerical
analytical papers on such things if you are so inclined...

> I sometimes wonder if the more common 64bits will not someday see
> CAD or related software go back to scaled integer arithmetic =E0 la
> Intergraph dgn, where 64bits is enough for the range of coordinates
> and precision used...

double precision seems enough for most things. ieee754-2008
has quad precision... Symbolic math package Macsyma (& Maxima)
has had bigfloats (arbitray precision floating point) for
decades.  Supposedly some Common Lisp implementation have
those as well.  Mechanical CAD packages would probably get
more benefit from symbolic math capabilities than just scaled
integers (keep everything in formulas until when you
absolutely need numerical results!).

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Sun, 02 Oct 2011 14:44:35 EDT erik quanstrom <quanstro@quanstro.net>  wrote:
> > IEEE754-1985 didn't specify circular, hyperbolic or other
> > advanced functions. You can have 754 compliant hardware and
> > not implement these functions. In any case the standard can
> > not dictate the accuracy of functions not specified in it. An
> > iterative algorithm may lose more than 1 bit of accuracy since
> > iterations won't be done in infinite precision. One can not
> > assume accuracy to a bit even where these functions are
> > imeplemented in h/w.  For x86, accuracy may be specified in
> > some Intel or AMD manual.
>
> that wasn't my reading of the spec.  so you're saying that if
> the iterative algorithm loops 53 times, it's free to return any
> answer whatever and still be compliant?

That was my reading (but it was a long time ago and I am not a
numerical analyst lawyer. So caveat emptor. You get what you
pay for. etc.) But if you expect to sell your library
presumably you'd care about the quality of impementation!

Re: [9fans] circular fonctions: precision?

[erik quanstrom]

> > that wasn't my reading of the spec.  so you're saying that if
> > the iterative algorithm loops 53 times, it's free to return any
> > answer whatever and still be compliant?
>
> That was my reading (but it was a long time ago and I am not a
> numerical analyst lawyer. So caveat emptor. You get what you
> pay for. etc.) But if you expect to sell your library
> presumably you'd care about the quality of impementation!

F00F!

- erik

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Sun, Oct 02, 2011 at 12:06:18PM -0700, Bakul Shah wrote:
>
> > I sometimes wonder if the more common 64bits will not someday see
> > CAD or related software go back to scaled integer arithmetic =E0 la
> > Intergraph dgn, where 64bits is enough for the range of coordinates
> > and precision used...
>
> double precision seems enough for most things. ieee754-2008
> has quad precision... Symbolic math package Macsyma (& Maxima)
> has had bigfloats (arbitray precision floating point) for
> decades.  Supposedly some Common Lisp implementation have
> those as well.  Mechanical CAD packages would probably get
> more benefit from symbolic math capabilities than just scaled
> integers (keep everything in formulas until when you
> absolutely need numerical results!).

To resort to algebra (infinite precision by symbol combinations) is,
indeed, a general rule. For symbolic math capabilities, I have wandered
around the concept for geometrical description (like METAFONT/MetaPost,
where there is this distinction that is mostly blurred in programming
languages---except for basic conditionnals--- : the distinction between
an assignation and an equation).

But to come back to programming, when calculus is the crux, the more
common/known even new! programming languages are not great tools, and
"portability" i.e. proved accuracy of the implementation for a wide
range of hardware/software is fuzzy. And it's amazing to see how one can
rapidly face errors even with very basic computations. And even with
integer arithmetic, not much help is guaranteed by languages.
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[Russ Cox]

On Sun, Oct 2, 2011 at 12:38 PM,  <tlaronde@polynum.com> wrote:
> Is there some documentation about the precision of the circular (i.e
> trigonometric) fonctions, depending on the (plan9) implementation and
> the hardware?

They are not terribly accurate.

If you need accurate versions, the best I know are the ones
that were written at Sun and included in the FreeBSD math library.
There are copies on any FreeBSD machine and also in the
vx32 distribution: http://code.swtch.com/vx32/src/tip/src/libvxc/msun.

For Go, we started with implementations of the Plan 9 library
algorithms but have been slowly replacing them with implementations
of the Sun/FreeBSD algorithms for the improved accuracy.

Russ

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Oct 3, 2011, at 4:41 AM, tlaronde@polynum.com wrote:
>> 
> But to come back to programming, when calculus is the crux, the more
> common/known even new! programming languages are not great tools, and
> "portability" i.e. proved accuracy of the implementation for a wide
> range of hardware/software is fuzzy. And it's amazing to see how one can
> rapidly face errors even with very basic computations. And even with
> integer arithmetic, not much help is guaranteed by languages.

Integer & rational arithmetic is guaranteed in Scheme and some other languages. In an R5RS compliant Scheme implementation you have for example (/ 5 7) => 5/7. (If only people get over their irrational fear of prefix syntax they would discover a great little language in Scheme.) But most prog. languages do not specify minimal required accuracy on standard floating pt. functions. May be because most language hackers are not numerical analysts! 

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Oct 3, 2011, at 6:03 AM, Russ Cox <rsc@swtch.com> wrote: 
> For Go, we started with implementations of the Plan 9 library
> algorithms but have been slowly replacing them with implementations
> of the Sun/FreeBSD algorithms for the improved accuracy.

Why not just use sun/FreeBSD functions in C? Unless of course go authors are planning to specify guaranteed minimum accuracy!

Re: [9fans] circular fonctions: precision?

[erik quanstrom]

> On Oct 3, 2011, at 4:41 AM, tlaronde@polynum.com wrote: >>
> > But to come back to programming, when calculus is the crux, the more
> > common/known even new!  programming languages are not great tools,
> > and "portability" i.e.  proved accuracy of the implementation for a
> > wide range of hardware/software is fuzzy.  And it's amazing to see
> > how one can rapidly face errors even with very basic computations.
> > And even with integer arithmetic, not much help is guaranteed by
> > languages.
> >
> Integer & rational arithmetic is guaranteed in Scheme and some other
> languages.  In an R5RS compliant Scheme implementation you have for
> example (/ 5 7) => 5/7.  (If only people get over their irrational
> fear of prefix syntax they would discover a great little language in
> Scheme.) But most prog.  languages do not specify minimal required
> accuracy on standard floating pt.  functions.  May be because most
> language hackers are not numerical analysts!

i think you've got it there.  how do i stuff 5/7 in a 32-bit ethernet register?
if you're close to the h/w, it's probablly just confusing to fight it.

- erik

Re: [9fans] circular fonctions: precision?

[Russ Cox]

On Mon, Oct 3, 2011 at 10:44 AM, Bakul Shah <bakul@bitblocks.com> wrote:
> Why not just use sun/FreeBSD functions in C?

Because we are writing in Go.

Russ

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Oct 3, 2011, at 7:46 AM, erik quanstrom <quanstro@quanstro.net> wrote:

>> On Oct 3, 2011, at 4:41 AM, tlaronde@polynum.com wrote: >>
>>> But to come back to programming, when calculus is the crux, the more
>>> common/known even new!  programming languages are not great tools,
>>> and "portability" i.e.  proved accuracy of the implementation for a
>>> wide range of hardware/software is fuzzy.  And it's amazing to see
>>> how one can rapidly face errors even with very basic computations.
>>> And even with integer arithmetic, not much help is guaranteed by
>>> languages.
>>> 
>> Integer & rational arithmetic is guaranteed in Scheme and some other
>> languages.  In an R5RS compliant Scheme implementation you have for
>> example (/ 5 7) => 5/7.  (If only people get over their irrational
>> fear of prefix syntax they would discover a great little language in
>> Scheme.) But most prog.  languages do not specify minimal required
>> accuracy on standard floating pt.  functions.  May be because most
>> language hackers are not numerical analysts!
> 
> i think you've got it there.  how do i stuff 5/7 in a 32-bit ethernet register?
> if you're close to the h/w, it's probablly just confusing to fight it.

Ethernet ctlrs have FP registers these days? Wow! It is just a different fight. Scheme has conversion functions + macros to do what you want. Also note that most people do not work as closely to h/w as perhaps you or I do. And of course, you don't have to use just one language.

Funny you mention h/w. I have used scheme in the past for h/w testing as well as for generating code for a custom network processor. This NP had a 512 bit barrel shifter (could hold an entire 64 byte pkt and we could poke at any bitfield upto 32 bits in length). In my test library a 'shift' was (+ (quotient 512-bit-reg 2^32) new-32-bit-value)). Could've done in C but this was more fun and far fewer lines of code and far quicker to develop! I could represent an entire test pkt as a single number and shift into the barrelshifter etc. No need to worry about grotty indexing or off by 1 errors! 

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Oct 3, 2011, at 7:57 AM, Russ Cox <rsc@swtch.com> wrote:

> On Mon, Oct 3, 2011 at 10:44 AM, Bakul Shah <bakul@bitblocks.com> wrote:
>> Why not just use sun/FreeBSD functions in C?
> 
> Because we are writing in Go.

I don't get it. Surely go has a FFI? Or Are you planning to reimplement many libraries in go?

Re: [9fans] circular fonctions: precision?

[Russ Cox]

On Mon, Oct 3, 2011 at 11:34 AM, Bakul Shah <bakul@bitblocks.com> wrote:
> I don't get it. Surely go has a FFI? Or Are you planning to reimplement many libraries in go?

Using FFI for square root is overkill.

Russ

Re: [9fans] circular fonctions: precision?

[Bakul Shah]

On Mon, 03 Oct 2011 08:29:40 PDT Bakul Shah <bakul@bitblocks.com>  wrote:
>  In my test library a 'shift' was
> (+ (quotient 512-bit-reg 2^32) new-32-bit-value)).

Oops. I meant:
  (+ (* (quotient 512-bit-reg 2^32) 2^32)) new-32-bit-value)
In one clock the top 32 bits shift out and new 32 bits shift
in.  It has been a while.

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Mon, Oct 03, 2011 at 07:39:16AM -0700, Bakul Shah wrote:
>
> Integer & rational arithmetic is guaranteed in Scheme and some other languages. In an R5RS compliant Scheme implementation you have for example (/ 5 7) => 5/7. (If only people get over their irrational fear of prefix syntax they would discover a great little language in Scheme.) But most prog. languages do not specify minimal required accuracy on standard floating pt. functions. May be because most language hackers are not numerical analysts!

Thanks for your comments. I must really tackle Scheme some day!
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C

Re: [9fans] circular fonctions: precision?

[tlaronde]

On Mon, Oct 03, 2011 at 09:03:50AM -0400, Russ Cox wrote:
> On Sun, Oct 2, 2011 at 12:38 PM,  <tlaronde@polynum.com> wrote:
> > Is there some documentation about the precision of the circular (i.e
> > trigonometric) fonctions, depending on the (plan9) implementation and
> > the hardware?
>
> They are not terribly accurate.
>
> If you need accurate versions, the best I know are the ones
> that were written at Sun and included in the FreeBSD math library.
> There are copies on any FreeBSD machine and also in the
> vx32 distribution: http://code.swtch.com/vx32/src/tip/src/libvxc/msun.
>
> For Go, we started with implementations of the Plan 9 library
> algorithms but have been slowly replacing them with implementations
> of the Sun/FreeBSD algorithms for the improved accuracy.

Thanks for the tips. I will put the various clues given in the thread at
least to have a better understanding about what my code relies upon.
--
        Thierry Laronde <tlaronde +AT+ polynum +dot+ com>
                      http://www.kergis.com/
Key fingerprint = 0FF7 E906 FBAF FE95 FD89  250D 52B1 AE95 6006 F40C