[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: factor and large prime numbers
From: |
Pádraig Brady |
Subject: |
Re: factor and large prime numbers |
Date: |
Mon, 22 Jul 2013 16:59:13 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130110 Thunderbird/17.0.2 |
On 07/22/2013 04:01 PM, Sami Kerola wrote:
> Hello,
>
> I were curious how quickly factor will process prime numbers, and
> found something rather strange. For example these five can be computed
> quite quickly.
>
> time factor 10333147966386144929666651337523199999999
> time factor 371993326789901217467999448150835199999999
> time factor 13763753091226345046315979581580902399999999
> time factor 523022617466601111760007224100074291199999999
> time factor 20397882081197443358640281739902897356799999999
>
> But much smaller numbers will take ages to give results (to be honest
> I gave up).
>
> time factor 8683317618811886495518194401279999999
> time factor 295232799039604140847618609643519999999
>
> Any idea what is going on?
Quantifying...
$ time factor-8.10 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71
3933440413546305645095794190149676437
real 0m0.014s
$ time factor-8.10 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real 0m0.006s
$ time factor-8.21 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71
3933440413546305645095794190149676437
real 0m0.356s
$ time factor-8.21 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real 1m44.693s
So the new factor is slower in both cases.
The difference between the two numbers in factor-8.21
is due to different code paths (GMP and not).
Note GMP is unexpectedly faster in this case.
Now I previously asked about slowdowns in the new factor code.
http://lists.gnu.org/archive/html/coreutils/2012-10/msg00030.html
There it was mentioned that factor now enables prime proving by default.
This sometimes takes a lot of time as it needs to factor p-1 for
each factor p found. Each factor of p-1 is also proven prime, recursively.
If I compile with "prime proving" disabled we get:
$ time factor 10333147966386144929666651337523199999999
10333147966386144929666651337523199999999: 37 71
3933440413546305645095794190149676437
real 0m0.004s
$ time factor 8683317618811886495518194401279999999
8683317618811886495518194401279999999: 8683317618811886495518194401279999999
real 0m0.004s
So nice and fast.
So I have questions too at this stage.
1. I get that prime proving takes longer, though is the above 1m44s
reasonable/expected?
2. "Proving" is done in the GMP case too. Why is that faster? Is it a weaker
check?
thanks,
Pádraig.