Project

General

Profile

Bug #666

RatReconstructByLattice fails in some simple cases

Added by John Abbott about 9 years ago. Updated almost 9 years ago.

Status:
Closed
Priority:
Urgent
Assignee:
John Abbott
Category:
Maths Bugs
Target version:
CoCoALib-0.99536 June 2015
Start date:
19 Feb 2015
Due date:
% Done:

100%

Estimated time:
2.10 h
Spent time:
1.65 h

Description

RatReconstructByLattice(1,1145) returns failure -- why??

History

#1 Updated by John Abbott about 9 years ago

I ran the following to compare when ContFrac and Lattice methods are better

for M := 1000 to 2000 do
  for X:=1 To div(M,2) Do
    CF := RatReconstructByContFrac(X,M);
    L := RatReconstructByLattice(X,M);
    if CF.failed and not(L.failed) then println "L wins for [X,M]=",[X,M]; endif
    if L.failed and not(CF.failed) then println "CF wins for [X,M]=",[X,M]; endif
  endfor;
endfor;

It seems that RatReconstructByLattice fails with input (1,N) for N=1145..2000.
Why??
Note range is N=1145..8192; N > 8192 works OK again!

#2 Updated by John Abbott about 9 years ago

It seems that both RatReconstructByContFrac and RatReconstructByLattice fail on (1,N) for N < 1145. Then the CF method starts to work, but the lattice method starts to work only for a larger modulus.

#3 Updated by John Abbott about 9 years ago

  • Status changed from New to In Progress
  • Assignee set to John Abbott
  • % Done changed from 0 to 10

I now think that the problem may really be imprecise documentation.

#4 Updated by Anna Maria Bigatti almost 9 years ago

  • Priority changed from Normal to Urgent

#5 Updated by John Abbott almost 9 years ago

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

I have added a comment to the documentation.

I discussed with Christof the possibility of throwing an exception when the modulus is too small, but we both think that it is pointless: there is already the boolean indication of "failure", and the risk of throwing an exception might force the caller to write try..catch blocks where they are practically never needed.

Regarding this matter as resolved, so moving it to feedback.

#6 Updated by John Abbott almost 9 years ago

  • Status changed from Feedback to Closed
  • % Done changed from 90 to 100
  • Estimated time set to 2.10 h

Modified C5 doc too.

Also available in: Atom PDF