bug#22567: Factoring 38 nines

[Jim Meyering]

On Fri, Feb 5, 2016 at 11:29 AM, Eric Blake <address@hidden> wrote:
> On 02/05/2016 11:30 AM, SasQ wrote:
>
>>
>> OK, this convinces me this is not a bug. 4m30 on my machine.
>> But it's definitely a user-interface fail ;)
>> It should at least output some warning that the computations might
>> take longer, or display some progress status / estimated time along
>> the way.
>
> Estimated status is very hard to produce. I guess with trial division,
> you could output a progress indicator comparing what number you are
> trying in relation to the square root of the number being factored, as a
> rough estimate; but there's still the annoying problem that any estimate
> bar will not progress smoothly (once a factor is found, the time
> remaining changes).  Progress indications should not be issued by
> default, unfortunately, because it might break expectations of
> applications that have grown used to no progress, so you'd have to make
> it a new command line option - but then, how will people know to use the
> new option?
>
>> Because otherwise the user can think it simply hangs.
>
> If a user is naive enough to think it is hanging on large input, how can
> we expect them to also be aware that they can turn on an option to track
> progress? And how will we explain that the progress meter may have no
> bearing on the real amount of time required?
>
>>
>>> The source code is there for you to peruse.
>>
>> There sure is, but analyzing it just to figure out the algorithm takes
>> much more time than refering the maual to see which particular
>> factorization algorithm or its variation is in use.
>>
>> It took me a while to find the answer on StackOverflow:
>> http://stackoverflow.com/questions/11155331/what-is-the-algorithm-behind-the-factor-command-in-linux
>> so mentioning it in the man page wouldn't hurt.
>
> Well, it IS mentioned in the documentation (the info page, as the
> preferred documentation for a GNU project); and the point of the man
> page is to be a terse summary, not the full documentation.  But maybe
> you have a valid point that adding a one-line blurb mentioning the
> Pollar Rho algorithm in 'factor --help' (which in turn feeds the man
> page) might be a useful change.

There is a deliberately hidden, three-hyphen ---debug
option that does provide a minimal progress indicator
(albeit still feels inadequate). This shows that it took
GNU factor 15 minutes to factor the 46-digit product
of two pretty large primes, M9 and M10:

$ M9=$(echo 2^61-1|bc) M10=$(echo 2^89-1|bc)
$ n=$(echo "$M9 * $M10" | bc)
$ env time -f '%U' factor ---debug $n
[using arbitrary-precision arithmetic] [trial division] [is number
prime?] [pollard-rho (1)] [trial division] [is number prime?] [trial
division] [is number prime?] [trial division] [is number prime?]
1427247692705959880439315947500961989719490561: 2305843009213693951
618970019642690137449562111
899.28