Project

General

Profile

Slug #1170

SmoothFactor: slow when a factor is found

Added by John Abbott over 6 years ago. Updated over 3 years ago.

Status:
Closed
Priority:
Normal
Assignee:
John Abbott
Category:
Tidying
Target version:
CoCoALib-0.99800
Start date:
28 Mar 2018
Due date:
% Done:

100%

Estimated time:
1.01 h
Spent time:
1.05 h

Description

Consider the following:

N := (281^NextPrime(12000)-1)/280;
NoPrint := SmoothFactor(N, 840000); --> less than 1 sec
NoPrint := SmoothFactor(N, 850000); --> about 58s, finds 1 factor
NoPrint := SmoothFactor(N, 1000000); --> about 58s, finds 1 factor

Why is it suddenly slow when a factor is found?

Related issues

Related to CoCoALib - Design #950: factor and SmoothFactor for integers --> FactorINT, FactorINT_TrialDiv, FactorINT_PollardRhoClosed2016-10-20

History

#1 Updated by John Abbott over 6 years ago

  • Related to Design #950: factor and SmoothFactor for integers --> FactorINT, FactorINT_TrialDiv, FactorINT_PollardRho added

#2 Updated by John Abbott about 6 years ago

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

I have found the slug: I had activated the "clever idea" of testing for IsProbPrim after a factor has been bound, but for larger integers IsProbPrime can be quite costly (e.g. about 58s in the example above).

I'm thinking about how to resolve the matter...

#3 Updated by John Abbott about 6 years ago

  • Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019

#4 Updated by John Abbott almost 5 years ago

An idea (in C++) is to have a sort of SmoothFactor iterator which can be told to continue from where it has reached.
Here is a very rough outline:

  BigInt N = ...
  SmoothFactorIter SFI(N, 100);
  if (cond)  SFI.myContinue(1000);

Maybe this makes things too complicated for the caller? Also the caller then gets the responsibility of calling IsProbPrime.

Another approach could be to estimate how much a call to IsProbPrime would cost (assuming not prime), and then call it only
when time spent trying factors is roughly equal to the estimated cost... This does mean that there will be a sudden jump in
computation time if we make repeated calls with increasing upper limit.

#5 Updated by John Abbott almost 5 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99700

#6 Updated by John Abbott over 4 years ago

  • Target version changed from CoCoALib-0.99700 to CoCoALib-1.0

#7 Updated by John Abbott about 4 years ago

  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99800
  • % Done changed from 30 to 80

The given example is no longer slow.
The trick of testing for primality is used only when RemainingFactor is not too large.
Probably something cleverer could be done... is it really worth it?

#8 Updated by John Abbott over 3 years ago

  • Status changed from In Progress to Closed
  • % Done changed from 80 to 100
  • Estimated time set to 1.01 h

The current impl is acceptable for the time being; out efforts need to be directed elsewhere.

Closing.

Also available in: Atom PDF