|
Bill Allombert on Wed, 24 Jan 2024 12:22:30 +0100
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: `primepi()` is significantly slower that sage's `primepi()`
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: Re: `primepi()` is significantly slower that sage's `primepi()`
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Wed, 24 Jan 2024 12:22:14 +0100
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1706095336; c=relaxed/relaxed; bh=+oIcquHbsWYTH1S1FRjpBAXwZ80vYSe4f0agvE0H7cE=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=xmGIHQWjKKaTy0xLeqEO+/RRQd7PfJx1hShnCwSbvTawK/ltjleReilpwshvRUG/YdifzzaCDj97C6YoCeinARRm7c43UgaJmG+NX+uoeN+cZFRodNaPNdI+hTBBMY/CUI9qoU+5K2Vjb/qHdImCynYU8wOjt8KdoRZsAMYqIhbsqO68d49oriErHVCyUHLcHFFZuNnQ5MEvgFT2vC3qztdJGuZfZBiR4byBUw5wTpklulqLYmzOVT8I8yKT+U21fCDYDIRB9hG+ke21evU1Aqff5g5g8oo+LsDIi+ucLj7jmYE+6efiBjB1266EMSmaJ4/sBwVXomBlCe1s0Qt5yKuDveZcqeB/ChX7G/rxn7NSFLL08K6Xuuvd4YBEEkBLOgEgtmo4OlQ+aTRw1Q505jqji6NTZCt6cnwhxEOvfV3YQche/uF410iv8k9/2LV8L66HGeuYPH+puUJvkrT1lUlM0lT8f0YnfrfS4DqyOXoLtDfssj8pOiUEyabWWtbgI7UpO6rcnstM5zZ59EiR2vxEc6A8hs9zuyf4bHxqWzjKCyIHGD3fGC3AzkOXMeh9W+HmuTlJbZmDoNwAOa/YY76aw9V8nKU/B+akqHcYBr4IPfXvaXDfYhc1YPCu0Lm7nlWR9ch/dMPyx62RKst9FHLIkIowd4UH2XOPSfQQTQ4=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1706095336; cv=none; b=RNbiAlqxI6TJxvEq772NYQo+f/gpxJ+plSVCptCw6kqZqgB8JxX5uVuZbqwoYlAtSiezZ5WWvHAQ1Eur+xqq7ObNcn13sPGJoPyb1TAXwsIpLQXC19K70lsi0jXMk9Fk43RvPeRHEH4QTyTI3lJqDFxNLd0o+kq3htRqYjzAab58C6TbsrUQ+FMliMAeu3dZsJl6cdckuvKvVQjM8MSzNkcP9xou2w1V8Yd0glw/gOcyj3dqlNKfW7mjx0hIZEv9u1MK2y67nmAlrj7o0WfipnyS2EiLpVeQnTzkCHEgZpz1zFQ12yrTaeq61/Nkg6hhIip3GicA/y5RlcFP0YB9eulzbtF1GufZAnrpp8wV6HdDcUfuyJ7uv165ico/nyqutlP52iGNhrSP/oDzDHNEUydVCxnc9lVhxaS6FZXb9aELRqOvPOEPGKtMlq9bW56JD57Mmex2FjszeKD7u5qidbuDidOm/IT8h1eY7kEPQZBLV53cEOvh6OfRPMpl6Wkpz098lcOYhA04Y4ZsCOIjoPz1LD2PL7RIg8vu/R3ZOi6WtXbkJO4NieW/5X4sDu+JRcc/4VhOilGwXg70I0Y0EBBfzmjcZCAwq9TPABfpHe4Ue8rbGhvTUhqoBWaR9oBvDhJwDgBSM6AiBs83ydDXVCw9PEm3Zxcd6/virym80Oo=
- Authentication-results: smail; arc=none
- Delivery-date: Wed, 24 Jan 2024 12:22:30 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1706095336; bh=+oIcquHbsWYTH1S1FRjpBAXwZ80vYSe4f0agvE0H7cE=; h=Date:From:To:Subject:References:In-Reply-To:From; b=f9/YqCIMzZDH8eqjS+NyFNVAxMQUIl/7VaNIw0W5je0DjiVHimBeuCn+N4a8qkkYP fBbQcqAEFdKt5aG2TqKxO3W4pEbMhLNe3jKQfhrC5nQEogt8uu1BmwKMrGrmNic7QL JBRhY7U3sSWpSRpKsUGn8OZQHk2f77ZkwhdR/dq64KytzqHCh7u4nmDNnHVnKB0w0D kwnqAj69ra+SDfxsLtEezrxU35IAXcDT7XffGCQ6Ebmtslr3f7U92nSqeqhHrqU54/ fmiQnDz/NhZFkdQigopr9ahpdm2TRkfr9nz+M178668KwligeeKpoIVTAfQ8oYy2eR BuVtmaKGfmS5Tyxco2xcC6E0TyxypzXxQmRFuN5D/Fs6rElJS0c2STjNGxeYF1afmW sNl/DgJyQ+w3sUIOy6qJQCg/wc6xn1pOzYj5f9OhQpEKtzm7Se9VQ9GLElWsStmumb xmi1U4lAddjLw5WwIPY18Lu7K5h8hUA4/TXs/4jvDtU0dSdeVdR62JQUjYO/O5ZpFe jVm7QVN/OP28MgUdae9klvpb7XudqsqnvFIuLYZCfNR+ZAyC6uKYyFJwB65G3QvJ3D oiIJ1/xIwfjBwd4lsbmQFFJKmAmCLp07jd8/VvD5nWEoqxvvHw+LOKaqD2MeBMBj1d lVOy5R0YfNQe0Nqwm6s3EOrA=
- In-reply-to: <CAGUWgD883xOmVz9sAUMUAWDiON4Z71YDUYKwKG--gyy_nNK1qw@mail.gmail.com>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <CAGUWgD883xOmVz9sAUMUAWDiON4Z71YDUYKwKG--gyy_nNK1qw@mail.gmail.com>
On Mon, Jan 22, 2024 at 12:51:30PM +0200, Georgi Guninski wrote:
> `primepi()` is significantly slower that sage's `primepi()`
>
> ? primepi(10^11)
> %59 = 4118054813
> ? ##
> *** last result computed in 5,285 ms.
>
> in sage:
>
> sage: time prime_pi(10**11)
> CPU times: user 31.3 ms, sys: 0 ns, total: 31.3 ms
> Wall time: 48.3 ms
> 4118054813
This is true. Sagemath use primecount
<https://github.com/kimwalisch/primecount/releases>
which use fast algorithms while PARI use a standard sieve.
In your example, I understand it is using Gourdon's algorithm.
(Interestingly, Xavier Gourdon wrote the original polroots code in PARI).
Cheers,
Bill.