Project

General

Profile

Slug #1769

FixedDivisor is sometimes surprisingly slow

Added by John Abbott 5 months ago. Updated 4 months ago.

Status:
Closed
Priority:
Normal
Assignee:
John Abbott
Category:
Improving
Target version:
CoCoALib-0.99850
Start date:
20 Nov 2023
Due date:
% Done:

100%

Estimated time:
2.22 h
Spent time:
2.25 h

Description

FixedDivisor can sometimes be unexpectedly slow.

f := product([c[1]*x-c[2] | c in (1..50)><(1..50) and gcd(c) = 1]);
FixedDivisor(f); -- a bit slow; much worse with 100 instead of 50

Maybe make the evaluation code in SparsePolyOps-cyclotomic.C publicly available & use it?

Related issues

Related to CoCoALib - Feature #1770: Evaluate polynomial function/classClosed2023-11-21

History

#1 Updated by John Abbott 5 months ago

  • Related to Feature #1770: Evaluate polynomial function/class added

#2 Updated by John Abbott 5 months ago

  • Status changed from New to Resolved
  • Assignee set to John Abbott
  • % Done changed from 0 to 60

I have changed the code to use the new prototype evaluation code (see issue #1770), and it is now usefully faster :-)
[for the example in the description: previously about 15s; now about 1s]
This is probably good enough: most of the time is spent evaluating the polynomial...
Not sure if we can be cleverer about which points to evaluate at? [ i.e. just use a subset of the points we actually use]

#3 Updated by John Abbott 5 months ago

  • Status changed from Resolved to Feedback
  • % Done changed from 60 to 90

I regard this as fixed: the remaining work is in issue #1770

#4 Updated by John Abbott 4 months ago

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

It is now good enough to be closed.

Also available in: Atom PDF