Help with some basic questions about Log[] and x^y

Help with some basic questions about Log[] and x^y

Post by Nick Maclar » Tue, 16 Dec 2003 17:26:08





|>
|> The latter is the point.  When constrained to floating point you can *not*
|> come arbitrarily close to the 0.5 ulp rounding point.  However it will
|> take a lot of time to find the closest function value for a transcendental
|> function.  For algebraic functions (like square root and cube root) it
|> is easier because Liouville's theorem specifies lower bounds on the
|> closeness.  Note however that with transcendental functions you will never
|> get the 0.5 ulp rounding point exactly (unless you have some special
|> argument).  For instance, when x is a floating point number, sin(x) is
|> rational if and only if x == 0.

Yes and no.  All of what you and Terje say is true, but it is possible
to do the same analyses for trigonometric functions with more effort,
and even log and exp.  I am sure that you both know how, but here is
one method.

    IEEE double floating point values can be expressed in terms of
a couple of thousand discrete uniform ranges (i.e. one for each
exponent).

    pi has a known continued fraction with civilised properties,
so you can reduce those (purely algebraically) to known formulae
for the residual in the range 0-pi/2.

    sin has a civilised Taylor series, so you can reduce that (again
purely algebraically) to a floating-point representation plus a
correction.  Q.E.D.

This isn't pretty, but DOES enable a full analysis of the problem
cases, and is how the people (like Fred Gustafson) produced their
'perfect' implementations.  While writing the algebra (even using
an advanced package like Axiom) would take skill and effort, I
doubt that it would need all that much computer time to do the
above.

It is clearly possible for power, but we are probably talking about
another order of magnitude complication again (i.e. as much harder
than sin as sin is than sqrt).  I wouldn't know how to start with
erf and inverse erf short of brute force, which is way beyond
current technology.

I don't think that it is reasonable for a standard to require it
even for sin, let alone other functions.  But it ISN'T impossible
at least for the trigonometric functions.

Regards,
Nick Maclaren.

 
 
 

Help with some basic questions about Log[] and x^y

Post by Mike Cowlisha » Tue, 16 Dec 2003 18:35:01


Quote:> I was responding to your posting, and I included the appropriate
> context.  To repeat your statement:

>> From a standards-writer's point of view the difficulty is that the
>> only 'reasonable' result to standardize is that the result be
>> correctly rounded.  That is relatively easy to achieve for +-*/ and
>> sqrt, but
>> is very much harder for log and power, and is generally considered
>> to be too hard to implement in hardware.

> That is wrong.  Simply, factually, wrong.  As I pointed out, there
> are many other reasonable results to standardise.

Yes, that's exactly why I put 'reasonable' in quotes...

Mike Cowlishaw

 
 
 

Help with some basic questions about Log[] and x^y

Post by Nick Maclar » Tue, 16 Dec 2003 19:03:15



|> > I was responding to your posting, and I included the appropriate
|> > context.  To repeat your statement:
|> >
|> >> From a standards-writer's point of view the difficulty is that the
|> >> only 'reasonable' result to standardize is that the result be
|> >> correctly rounded.  That is relatively easy to achieve for +-*/ and
|> >> sqrt, but
|> >> is very much harder for log and power, and is generally considered
|> >> to be too hard to implement in hardware.
|> >
|> > That is wrong.  Simply, factually, wrong.  As I pointed out, there
|> > are many other reasonable results to standardise.
|>
|> Yes, that's exactly why I put 'reasonable' in quotes...

Well, I apologise for misunderstanding you, and contradicting what
you didn't mean, but I am totally baffled by what you did mean.

The problem is that there is a currently widespread dogma that the
'correctly rounded' is the only reasonable thing to standardise,
and that viewpoint has caused and is causing incalculable harm.
I thought that you were promoting it.

[ I put it in quotes to say that I do not necessarily agree that
there is a single best type of rounding, but that aspect is not
relevant to my point. ]

I have many times been told that no alternative forms of accuracy
standardisation (other than 'correct rounding' and 'you get what
you get') would be considered, because it is 'known' that no other
possibilities are 'reasonable'.

Regards,
Nick Maclaren.

 
 
 

Help with some basic questions about Log[] and x^y

Post by Nick Maclar » Tue, 16 Dec 2003 19:11:00



|> > I was responding to your posting, and I included the appropriate
|> > context.  To repeat your statement:
|> >
|> >> From a standards-writer's point of view the difficulty is that the
|> >> only 'reasonable' result to standardize is that the result be
|> >> correctly rounded.  That is relatively easy to achieve for +-*/ and
|> >> sqrt, but
|> >> is very much harder for log and power, and is generally considered
|> >> to be too hard to implement in hardware.
|> >
|> > That is wrong.  Simply, factually, wrong.  As I pointed out, there
|> > are many other reasonable results to standardise.
|>
|> Yes, that's exactly why I put 'reasonable' in quotes...

Well, I apologise for misunderstanding you, and contradicting what
you didn't mean, but I am totally baffled by what you did mean.

The problem is that there is a currently widespread dogma that the
'correctly rounded' is the only reasonable thing to standardise,
and that viewpoint has caused and is causing incalculable harm.
I thought that you were promoting it in that response.

[ I put it in quotes to say that I do not necessarily agree that
there is a single best type of rounding, but that aspect is not
relevant to my point. ]

I have many times been told that no alternative forms of accuracy
standardisation (other than 'correct rounding' and 'you get what
you get') would be considered, because it is 'known' that no other
possibilities are 'reasonable'.

Regards,
Nick Maclaren.

 
 
 

Help with some basic questions about Log[] and x^y

Post by glen herrmannsfeld » Wed, 17 Dec 2003 05:47:41


(snip)

Quote:> The latter is the point.  When constrained to floating point you can *not*
> come arbitrarily close to the 0.5 ulp rounding point.  However it will
> take a lot of time to find the closest function value for a transcendental
> function.  For algebraic functions (like square root and cube root) it
> is easier because Liouville's theorem specifies lower bounds on the
> closeness.  Note however that with transcendental functions you will never
> get the 0.5 ulp rounding point exactly (unless you have some special
> argument).  For instance, when x is a floating point number, sin(x) is
> rational if and only if x == 0.

How about for base pi floating point numbers?  Yes, I know there is no
base pi hardware, and never will be.  Or maybe base pi/6 or so?

I have heard suggestions for base e, but never for base pi.

-- glen

 
 
 

Help with some basic questions about Log[] and x^y

Post by Nick Maclar » Wed, 17 Dec 2003 17:19:46




|>
|> > The latter is the point.  When constrained to floating point you can *not*
|> > come arbitrarily close to the 0.5 ulp rounding point.  However it will
|> > take a lot of time to find the closest function value for a transcendental
|> > function.  For algebraic functions (like square root and cube root) it
|> > is easier because Liouville's theorem specifies lower bounds on the
|> > closeness.  Note however that with transcendental functions you will never
|> > get the 0.5 ulp rounding point exactly (unless you have some special
|> > argument).  For instance, when x is a floating point number, sin(x) is
|> > rational if and only if x == 0.
|>
|> How about for base pi floating point numbers?  Yes, I know there is no
|> base pi hardware, and never will be.  Or maybe base pi/6 or so?
|>
|> I have heard suggestions for base e, but never for base pi.

I invented it some 50 years back, to the surprise of my teacher.
Much later, I discovered how often it had been invented before :-)
It offers virtually no advantages, and all non-integer bases are
a real pain to handle in discrete arithmetic.

More plausibly, trigonometric functions do not necessarily need
their arguments in radians; if the arguments are degrees, grads
or revolutions, then there ARE exact results.  And, despite what
people are taught at school, there is nothing more mathematically
natural about using radians than using revolutions - you just make
different things more natural.

Regards,
Nick Maclaren.

 
 
 

Help with some basic questions about Log[] and x^y

Post by Terje Mathise » Wed, 17 Dec 2003 18:26:06



> |> How about for base pi floating point numbers?  Yes, I know there is no
> |> base pi hardware, and never will be.  Or maybe base pi/6 or so?
> |>
> |> I have heard suggestions for base e, but never for base pi.

> I invented it some 50 years back, to the surprise of my teacher.
> Much later, I discovered how often it had been invented before :-)
> It offers virtually no advantages, and all non-integer bases are
> a real pain to handle in discrete arithmetic.

> More plausibly, trigonometric functions do not necessarily need
> their arguments in radians; if the arguments are degrees, grads
> or revolutions, then there ARE exact results.  And, despite what
> people are taught at school, there is nothing more mathematically
> natural about using radians than using revolutions - you just make
> different things more natural.

Still used every day:

All Garmin GPSs use scaled revolutions: 32 bit signed integers for a
full circle. Range reduction becomes quite trivial. :-)

I.e. base 2pi

Terje

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

Help with some basic questions about Log[] and x^y

Post by Dik T. Winte » Wed, 17 Dec 2003 19:39:08


...
 > More plausibly, trigonometric functions do not necessarily need
 > their arguments in radians; if the arguments are degrees, grads
 > or revolutions, then there ARE exact results.

Indeed, see the Ada standard, which also puts constraints on the
accuracy of the functions.
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

 
 
 

Help with some basic questions about Log[] and x^y

Post by glen herrmannsfeld » Thu, 18 Dec 2003 05:17:16


(snip)

Quote:> More plausibly, trigonometric functions do not necessarily need
> their arguments in radians; if the arguments are degrees, grads
> or revolutions, then there ARE exact results.  And, despite what
> people are taught at school, there is nothing more mathematically
> natural about using radians than using revolutions - you just make
> different things more natural.

PL/I has the sind(), cosd(), and I believe other functions with
arguments in degrees.   There might be other languages that
do, but it doesn't seem to be as common as it should be.

With radians, it is difficult to get exact results for the easy cases.

It might be that it is fixed now, but I used to hear about problems
in doing a 90 degree or 180 degree rotation in postscript.  The
rotation matrix for 90 degrees should come out

   0   1
  -1   0

but those 0's didn't come out exactly 0, because they couldn't
multiply the degrees (supplied to the rotate command) to radians
and then to the cos function and get 0 out.

-- glen

 
 
 

Help with some basic questions about Log[] and x^y

Post by Dik T. Winte » Thu, 18 Dec 2003 09:12:34



 > > More plausibly, trigonometric functions do not necessarily need
 > > their arguments in radians; if the arguments are degrees, grads
 > > or revolutions, then there ARE exact results.  And, despite what
 > > people are taught at school, there is nothing more mathematically
 > > natural about using radians than using revolutions - you just make
 > > different things more natural.
 >
 > PL/I has the sind(), cosd(), and I believe other functions with
 > arguments in degrees.   There might be other languages that
 > do, but it doesn't seem to be as common as it should be.

Ada has two forms of those functions.  With a single argument (in that
case it is the standard function) and with two arguments.  The second
arcument is the measure of the complete circle.  So sin(x, 360) would
be in degrees.
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

 
 
 

Help with some basic questions about Log[] and x^y

Post by Terje Mathise » Thu, 18 Dec 2003 15:55:23





>  > > More plausibly, trigonometric functions do not necessarily need
>  > > their arguments in radians; if the arguments are degrees, grads
>  > > or revolutions, then there ARE exact results.  And, despite what
>  > > people are taught at school, there is nothing more mathematically
>  > > natural about using radians than using revolutions - you just make
>  > > different things more natural.

>  > PL/I has the sind(), cosd(), and I believe other functions with
>  > arguments in degrees.   There might be other languages that
>  > do, but it doesn't seem to be as common as it should be.

> Ada has two forms of those functions.  With a single argument (in that
> case it is the standard function) and with two arguments.  The second
> arcument is the measure of the complete circle.  So sin(x, 360) would
> be in degrees.

"Add everything _and_ the kitchen sink!"
:-)

So the regular function version (for radians) becomes a two-argument
call with a default second parameter of 2pi?

Terje

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

Help with some basic questions about Log[] and x^y

Post by Dik T. Winte » Thu, 18 Dec 2003 20:16:09




...
 > > Ada has two forms of those functions.  With a single argument (in that
 > > case it is the standard function) and with two arguments.  The second
 > > arcument is the measure of the complete circle.  So sin(x, 360) would
 > > be in degrees.
 >
 > "Add everything _and_ the kitchen sink!"
 > :-)
 >
 > So the regular function version (for radians) becomes a two-argument
 > call with a default second parameter of 2pi?

No.  On purpose they are different functions.  The two argument functions
must do exact range reduction mod the second argument.  The one argument
function is allowed to do range reduction with an extended precision
value of 2pi.
--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

 
 
 

Help with some basic questions about Log[] and x^y

Post by Mike Cowlisha » Fri, 26 Dec 2003 01:27:25


[And my apologies for slow response to this one .. somehow it got 'marked as
read' when it wasn't...]




>>>> I was responding to your posting, and I included the appropriate
>>>> context.  To repeat your statement:

>>>>> From a standards-writer's point of view the difficulty is that the
>>>>> only 'reasonable' result to standardize is that the result be
>>>>> correctly rounded.  That is relatively easy to achieve for +-*/
>>>>> and sqrt, but
>>>>> is very much harder for log and power, and is generally considered
>>>>> to be too hard to implement in hardware.

>>>> That is wrong.  Simply, factually, wrong.  As I pointed out, there
>>>> are many other reasonable results to standardise.

>>> Yes, that's exactly why I put 'reasonable' in quotes...

> Well, I apologise for misunderstanding you, and contradicting what
> you didn't mean, but I am totally baffled by what you did mean.

> The problem is that there is a currently widespread dogma that the
> 'correctly rounded' is the only reasonable thing to standardise,
> and that viewpoint has caused and is causing incalculable harm.
> I thought that you were promoting it in that response.

> [ I put it in quotes to say that I do not necessarily agree that
> there is a single best type of rounding, but that aspect is not
> relevant to my point. ]

OK.  I'm referring here not to what is 'technically plausible' but
more 'what a committee can agree to' (which is the basis of
just about all formal standards).   For a function such as multiply,
or add, or square root, it has been shown that 'correctly rounded'
is attainable efficiently.   It is therefore relatively easy ('reasonable')
for a standards committee to standardize these functions.

For other functions (such as power, x^y) the correctly-rounded
answer is hard to derive.  Therefore one ends up in a debate as
to how 'loose' an answer is acceptable (and for which rounding
modes this applies, etc.).  And others point out the difficulty of
testing, generating testcases, etc.

An individual can rapidly come to a conclusion as to the
'right' answer in any such case.  But in practice (in a
committee) there will be many varied views and none
of the individual suggestions will be clearly the 'best'.

And in this situation, the only 'reasonable' thing to do is
to not standardize.

Mike Cowlishaw

 
 
 

Help with some basic questions about Log[] and x^y

Post by Nick Maclar » Thu, 01 Jan 2004 01:28:42




>OK.  I'm referring here not to what is 'technically plausible' but
>more 'what a committee can agree to' (which is the basis of
>just about all formal standards).   For a function such as multiply,
>or add, or square root, it has been shown that 'correctly rounded'
>is attainable efficiently.   It is therefore relatively easy ('reasonable')
>for a standards committee to standardize these functions.

One can argue whether the performance penalty is worth the benefit,
but I agree that is debating what should be standardised.  It is
certainly reasonable to standardise 'perfect' accuracy in those cases,
though it is also reasonable not to.

Quote:>For other functions (such as power, x^y) the correctly-rounded
>answer is hard to derive.  Therefore one ends up in a debate as
>to how 'loose' an answer is acceptable (and for which rounding
>modes this applies, etc.).  And others point out the difficulty of
>testing, generating testcases, etc.

Um.  That IS so, but I think that it is overstating the case.  Such
debates are normal for any language facility.

Quote:>An individual can rapidly come to a conclusion as to the
>'right' answer in any such case.  But in practice (in a
>committee) there will be many varied views and none
>of the individual suggestions will be clearly the 'best'.

Ditto.

Quote:>And in this situation, the only 'reasonable' thing to do is
>to not standardize.

Definitely NOT.  Inter alia, that approach would eliminate all known
language standards, as well as most of the IEEE standard.  There are
AT LEAST two reasonable things to standardise in this case:

One is to standardise a known achievable bound, and say that an
implementation must achieve at least that.  For example, you could
require 1 ULP accuracy - where that accuracy could be taken up by
any argument was well as the results.  This would work for power,
sin, and so on.

Another is to standardise an accuracy metric (or at least a form of
description) and state that the achieved bound is implementation
defined.  This would provide users with the information they need
to make a reasonable 'contract' with the implementor.

Regards,
Nick Maclaren.