On Fri, Feb 5, 2016 at 11:29 AM, Eric Blake <[email protected]> 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
