|
Bill Allombert on Mon, 15 Jan 2024 19:21:33 +0100
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Implementation of forprime() and unextprime()
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: Re: Implementation of forprime() and unextprime()
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Mon, 15 Jan 2024 19:21:29 +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=1705342891; c=relaxed/relaxed; bh=L33L44wMeaw1zdWdGqqXseIMCbS2KLHYoXS9AqvWFUk=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: Content-Transfer-Encoding:In-Reply-To; b=ClofpK9K2ZJqWFFCEdDYeCUqlb2x4ldBdDvYKcMI1Iy91Mk2m7GnW5cHktVZ/VYSUDiEMo5NJaZFEDeyr/0criorMQYdYl/EUrWNtKPpBBauJMYtOgqURo+FWD1OOIWn1EBK9NxL/qgmn1MZR4KkiTMSYRv4fV4ieQ7azjKPrKiBQAfiNdg/rPVi14t3eHYZ2vYXQNdVAYzlh51xdx+2n1JSj6PzAvCEBGAC5q3pIB3ICuT95MQ9s2KXtTes5aboOpvpOGTVLwV01yQaOc5hdOLxAAsvSCFI5EK3RpGk9Et+7Urah6UpFFvj43CbcrOXfk+G9OwAFjH8u2OkZ5OQHBLWoYlvd0S5bTjYCVZS0VHplE22jhUOuy5pcjb+wnEDWfEb/XEjR7uSHQaZxSl7j3lDurDWvZiIv/gl1E63n2h1bfnDbaeBeeal6yJL8s+D0oC3yDLrTvQayM2D/6TjOmpsp4ZHgNWrBCom26FpO9CaRY5Mw4ZqVBLkbcMwtp9nz+K6A43pBOWUthY5nAi9ptkVg07BSEANciWy2ursEYfQkAXr4arDR16SmmzcIgVQE4je+6QqXe7pWABhkPwlqq5lfc8WYxQYLbjmcwqhYs9Wiujt9Q9x3J0/Lh1yxWXtfwH4AA3pHyx2Ki7VrHE7lLLlNNNGWaJKGoLG32ukHMs=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1705342891; cv=none; b=SgKzi+8l6iLm3tVaFsnnIyDN1PjEVAAtOY416Kd24KU3k1lhtIr/RWpNpNQz8882+cSXWDru50gyp81CFn6EtL7GGwjIoKZPO3twNjpqR16iwCFMPV83oBFplBSYM0pM93HSIpe6DKE/1+2fHhvvcB+IGMI1DZNv8AvWqDsALfUEUZPVWifN54qtjBSJ2Q8Imabp50t6K7CsAiTBA8VqVa3vDQ/pUTQ8rPIwv0lZZ9jxw42Iep7KICFis6yZJ+HEa99+nVLTkWF5VOmm2EQTMIf9cXwtlyiDuk6tWpNJy+dMtsX5L9Y5k7Jyi/4FcHHUiQqTkvjy/tCFONEVSRQRwUaVLM4UZoJdJLPZPT6qvln1O+DVaYY9GgTcm06OYQYZXM7pFykRaez3FNUwl0bB0qhbJpkJhauiepEh8Kwuu6QBJR7x8YqU9DtK7ZH4AhIrOLa0+U1tzwhZlCei26KYxh4tIpz84lRMdD4v0kK0W35t1EiuUYjqCmrogSVXCGr28EhoQ2j/VGYvc/fdAqDSXuSz9P+CVwgevVkCixlxCP64bxdkK6L+4BtyUYVIQHG/ciwjBVAwzLNSo9nrepm7ouD+ZiQQcmlSZCp3URgclaYdya95pBdJXtJyL3+a41L7MZzvaTIcPrN3pC0uq0SfD65aUl2dg+FJijln8el30Eg=
- Authentication-results: smail; arc=none
- Delivery-date: Mon, 15 Jan 2024 19:21:33 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1705342890; bh=L33L44wMeaw1zdWdGqqXseIMCbS2KLHYoXS9AqvWFUk=; h=Date:From:To:Subject:References:In-Reply-To:From; b=N9mvIqLC5Ll+WuDTmXWZbXOADD/OWGBqmrIsuqSocNThlEXMWBRs/Q+HxjhgHacq+ RxyOPy6p5Un2tJHw96zlwukCwCA0/09T8/9Ca7UlbjvMvdfCbtBvTgSlXVYxowTDiB WxNr5DjjJGQz81m48SmJtCPCulA+nT4D7RrFQ8oIifH0z9aPkBXFIjDxgizxUsKwyz bZb1WrQvrZRBJ3n0n/q4qqtDK0yOjdzsBTZerNQ7mUuCFHKffU/iD7ejKKygJOfZZi vuVleid96gn06YYoJvxVOcAik8DqXMFFMuIATxWEIe4AUBxKJzH7f3w4aBdIcRQoya 34B2KVEWwFfPJbffiXfSgPbIC6E/EC8biBVZ45AtEexd45a6q7RHsbC5DEDxKt1XST NSpLBan9AMWdpfJDOE4dscK5C3NiSm40NCJvHZfeDEcuS4Lwi2n7n+sGHY/LRze+zF DUvxYc1Uc+jKYvN5m0OWfp8HuRPt7VRV4GUXgYYSH2AgyD/Egx9ZIjalOwNX3Fy6s4 MCEqe1KBKfOjb+dzeNucyN3R1wvUUsB9KrUuKjCqdHcTeumm0+E65dnWy2l5Ymnedx Mn/KQ1ApP6RgOUxdyLt1kiJyOGn6OAZ0OHrPqvzFq3bQ3jAxIGlvu0N3ROaMUC8xF9 pGijLdFch9SHN2BBfKPmW1lo=
- In-reply-to: <ZaCtf8u8D+gSGbj+@login.math.berkeley.edu>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <ZaCtf8u8D+gSGbj+@login.math.berkeley.edu>
On Thu, Jan 11, 2024 at 07:09:51PM -0800, Ilya Zakharevich wrote:
> B) unextprime() (the ulong version of nextprime() from
> basemath/ifactor1.c) has a rather convoluted code to sieve mod
> 210. Why not:
>
> • just store tables with a bitmap of a few (say 8) next odd
> residues mod N which are mutually prime with N. (Indexed by
> “an odd” residue mod N.)
> • For a given odd number, extract the corresponding bitmaps from
> the tables for a few values of N (such as 210, 11*19, 13*17, 23 and 29).
> • “bit-AND” these bitmaps.
> • Use the count of trailing/leading 0 bits (should be cheap) to
> jump ahead.
>
> I would not be surprised if this can speedup the code by 20%
> (maybe even a bit more for numbers closer to 2^64).
I have made a branch bill-unextprime with a simpler algorithm,
but the speed is exactly the same, which means that all the time is
spent in uisprime.
Cheers,
Bill.