|
Jean-Luc ARNAUD on Tue, 23 May 2023 12:44:41 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
factor and factorint performances
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: factor and factorint performances
- From: Jean-Luc ARNAUD <jl.arnaud@free.fr>
- Date: Tue, 23 May 2023 12:40:03 +0200
- Delivery-date: Tue, 23 May 2023 12:44:41 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/simple; d=free.fr; s=smtp-20201208; t=1684838404; bh=1WyBFUwfHbUsRsm4PQDRTcgrkaWqxV6OcbPBatOzAbQ=; h=Date:To:Reply-To:From:Subject:From; b=iObeBWNpfEVTN0Joa03f0nj65t36qWLHFhPmJU/Zz4HZowW+TwXY3y5JM24LkhpnJ hIXOpvw+5ZQrtvJmLTFtBt31k2+A4b1V8qRft5FSdrAidmn3Jt3c9VLI1rNlLT+4dC A3efz5W+tK9xLbKPKMqt+dN8UserMozEGdo+Y9eYy64F7LmJADJmmAWvgzhRoNyXbl +W+CiSZYzo+9BeqhndxStOvN6ZF5LtlkJJM5uepSO22N0aItHL6GpXPGzNGwmSI9k3 S9BZtxrGSEq9nxe1M5hlEYIocIT2pG4IVJwQHeS58m7Ogh8oI6LagagvDoD9Jo0OOx s3O3ppahTYc+g==
- Reply-to: jl.arnaud@free.fr
- User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.11.0
Hi everybody,
Playing with factor and factorint functions, I was amazed at their
performances (compared to other Math libraries), until I tried to
factorize 2^1003-1.
After more than 11 hours, no result ...
So I tried this Web tool
(https://www.dcode.fr/prime-factors-decomposition in English,
https://www.dcode.fr/decomposition-nombres-premiers in French) and
got a result in ... 2.25 seconds!!!!
Unless they use a supercalculator (and I don't think so), their
algorithm is very, very efficient.
Is it possible to get the same performance using PariGP? In a
previous message, Bill said that it could be possible to skip the
primality test with factor.
The reason PARI is slow is that it does a primality test each time it finds a factor.
Since the number is large with lots of factors, then it takes a long time.
(about 90s for each factor). So it should finish in about 54 hours.
If we expected that the number do not have prime factors larger than some bounds, we
could just skip the primality test.
Could this be a solution? How would you do that?
TIA for your help.
--
Jean-Luc Arnaud