Project

General

Profile

Slug #722

valuation slow for large inputs

Added by John Abbott almost 9 years ago. Updated over 3 years ago.

Status:
Closed
Priority:
Low
Assignee:
John Abbott
Category:
Improving
Target version:
CoCoALib-0.99800
Start date:
31 May 2015
Due date:
% Done:

100%

Estimated time:
2.00 h
Spent time:
1.95 h

Description

I tried valuation(5,factorial(1000000)) and it took too long.

Make valuation faster if the prime is small (and the number big).

Related issues

Related to CoCoA-5 - Design #490: Duplicate fns: valuation and FactorMultiplicityClosed2014-03-21

History

#1 Updated by John Abbott almost 9 years ago

  • Estimated time set to 2.00 h

Source code is in NumTheory.C.
It is just a very simple loop. Presumably I could test divisibility by a small power of the prime. Might it be useful to compute gcd? Perhaps too costly to get the quotient?

#2 Updated by John Abbott almost 9 years ago

Probably QuoRem is a more sensible choice than gcd.

#3 Updated by John Abbott almost 9 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 30

I have implemented a version which divides repreatedly by the largest power of the prime which fits into unsigned long. This now takes about 45s for valuation(2,N) and 26s for valuation(5,N) where N=factorial(1000000).

Maybe a recursive "repeated squaring" version would be neater and faster?

#4 Updated by John Abbott almost 9 years ago

  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99540 Feb 2016

#5 Updated by John Abbott over 8 years ago

  • Assignee set to John Abbott

In issue #490 I decided to make the definition of FactorMultiplicity wider: the "base" need not be prime (just an integer greater than 1).

I'm accepting the current impl for the imminent release of C5.1.2 (tomorrow?), but will leave this issue open, so that someone will look at making a proper recursive impl.

#6 Updated by John Abbott over 8 years ago

Extra task: extend defn of FactorMultiplicity to RingElem (belonging to a TrueGCDDomain).

#7 Updated by John Abbott about 8 years ago

  • Target version changed from CoCoALib-0.99540 Feb 2016 to CoCoALib-1.0

#8 Updated by John Abbott about 4 years ago

The timings on my current machine (Fujitsu) are:
FactorMultiplicity(2, N) about 16s
FactorMultiplicity(5, N) about 9.7s

NOTE: source code is now in NumTheory-factor.C

#9 Updated by John Abbott over 3 years ago

  • Status changed from In Progress to Closed
  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99800
  • % Done changed from 30 to 100

The current impl is "good enough" for the moment. If a specific application comes up where more speed is needed then we can reconsider the impl.
I do not see any point in investing time now to make a rather more complicated version (which is perhaps a bit faster in certain rather artificial tests).

Also available in: Atom PDF