Project

General

Profile

Bug #853

NearestInt can needlessly throw InsufficientPrecision

Added by John Abbott almost 2 years ago. Updated over 1 year ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Buggy Maths
Start date:
23 Mar 2016
Due date:
% Done:

100%

Estimated time:
7.70 h
Spent time:

Description

The current impl of NearestInt with an arg from a RingTwinFloat can throw InsufficientPrecision when it should not.

The cause is a speculative call to IsRational which does not catch the error.

Fix impl of NearestInt.


Related issues

Related to CoCoALib - Support #696: test-OrderedRing: activate or eliminate?Closed2015-05-08

Related to CoCoALib - Bug #858: floor for TwinFloat can produce ERR::SERIOUSClosed2016-03-26

History

#1 Updated by John Abbott almost 2 years ago

  • Related to Support #696: test-OrderedRing: activate or eliminate? added

#2 Updated by John Abbott almost 2 years ago

  • Status changed from New to In Progress
  • Assignee set to John Abbott
  • % Done changed from 0 to 10
What properties should the result of NearestInt have?
  • an obvious property is abs(NearestInt(X) - X) <= 1/2

What should happen to halves?

Recall that there is a function called RoundDiv(N,D) and a closely related function round(q) for a rational number. It seems reasonable to expect that NearestInt(X) = round(Q) if IsRational(Q,X); or equivalently, given a rational number Q then round(Q) = NearestInt(RingElem(R,Q)) for any ring R where NearestInt(R,Q) is defined.

How to implement NearestInt so that it is surely compatible with round?
The hard case is when the ring is RingTwinFloat.

#3 Updated by John Abbott almost 2 years ago

Which is the better design?
  • (A) A normal C++ fn (as currently implemented), or
  • (B) mem fns for the rings which actually need to implement it.

An advantage of (A) is that all the code is together so it should be (relatively) easy to see that halves are rounded consistently for all rings.
An advantage of (B) is that the impls can exploit knowledge of the explicit internal representation of the values.
A disadvantage of (B) is that every ring must have an impl of myNearestInt even when this makes no sense; of course, there can be a default impl which gives an error (but that is a bit ugly).

#4 Updated by John Abbott almost 2 years ago

Currently the only ordered domains are: RingZZ, RingQQ (since a FractionField of an ordered domain is an ordered domain), and RingTwinFloat.

A disadvantage of implementation approach (A) in the previous comment is that the function must (really ought to be) be reviewed every time a new ordered domain is added to make sure that it works properly also for the new ring. JAA is now inclined to think that this disadvantage outweighs the disadvantages of approach (B).
[of course this means rewriting the current implementation]

#5 Updated by John Abbott almost 2 years ago

I am thinking of making the test for NearestInt of twin float values work as follows:
fix an integer N, for ever smaller positive values of eps verify that after setting x = N+eps we have that NearestInt(x) == N gives exactly the same response as N <= x && x < N+1. Repeat also for values of eps = 1- eta where eta is small and positive.

Do the test for N small and positive, large and positive, small (abs val) and negative, large (abs val) and negative.

#6 Updated by Anna Maria Bigatti almost 2 years ago

John Abbott wrote:

Which is the better design?
  • (A) A normal C++ fn (as currently implemented), or
  • (B) mem fns for the rings which actually need to implement it.

can't we have a member function with an abstract implementation (or error), and concrete implementations only for special cases (i.e. TwinFloat)?

#7 Updated by John Abbott almost 2 years ago

I think I have fixed the problem. I have completely rewritten the code to do with floor, ceil and NearestInt.

Part of the problem was a test something like abs(x-N) <= 1/2 where the problem was x-N would throw InsuffPrec because the result could not be calculated with the precision required by the twin-float ring (even though it could be calculated quite accurately enough to recognize that the difference was less than 1/2.

A new, clearer test now passes as I expect it to. So marking this as in feedback.

#8 Updated by John Abbott almost 2 years ago

  • Status changed from In Progress to Feedback
  • % Done changed from 10 to 90

I followed design (B); we just have to be careful if we want to change policy about how halves are handled. Perhaps some vagueness in exactly how they are handled is not such a bad thing?

#9 Updated by John Abbott almost 2 years ago

  • Related to Bug #858: floor for TwinFloat can produce ERR::SERIOUS added

#10 Updated by John Abbott almost 2 years ago

  • Estimated time set to 7.70 h

I have cleaned the impl considerably; it is now obviously correct (but possibly slower than necessary as a wasteful temporary is created).

Maybe I'll try a version without the temporary to see if it is usefully faster (but the code will be less clear).

#11 Updated by John Abbott over 1 year ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100

This has been in feedback for 3 months without any reports of problems.
Apparently the (new-ish?) test test-OrderedRing2.C covers the problems reported here.
Closing!

#12 Updated by John Abbott over 1 year ago

  • Target version changed from CoCoALib-0.99560 to CoCoALib-0.99550 spring 2017

Also available in: Atom PDF