|
Karim Belabas on Wed, 20 Mar 2024 13:04:44 +0100
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: How to efficiently count Proth primes with GP parfor?
|
- To: hermann@stamm-wilbrandt.de
- Subject: Re: How to efficiently count Proth primes with GP parfor?
- From: Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>
- Date: Wed, 20 Mar 2024 13:04:37 +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=1710936278; c=relaxed/relaxed; bh=P6nC4286hZy5X3DprxkWp9LSgHAJcRCM+aSQFd0E1O4=; h=DKIM-Signature:Date:From:To:Cc:Subject:Message-ID: Mail-Followup-To:References:MIME-Version:Content-Type: Content-Disposition:Content-Transfer-Encoding:In-Reply-To; b=Nzvgy6lIzSIP1YZ5ETW/3zGfTdHwlbjPG2BGnk1q/Y5+FU787qYT/QgiUgDNdL24ii4Az51Dh4e/7T8fvaDymfIdZcV28aQHiKMBfKgxqRCxjd5wnFLqlZ8WZPz0ZixVh2pF42RTYmyXB78edziJDihW+w9v/1/3Cu9yacZixlZO2a//ubmSpxO0X93Gn29eKS/koxgbpedJdwYigxjFmwqTiTcQcuYUrNKYHtubGxeoSABHaOVclqmq0SztZXUQF2cUj0L5EvrjHwsUtb7seaLmGdLgSZ3gUP9LuDVrvPo7Ss8xjW/8NYUNBMwSkZOG67pjogwwHX8AwjX5+stgW+irKY9VjHkllUIlp13ID+P/NRKt1T5xLkbDwDLdmTVqnsk70mVyYJ3h0X514FQDz0w9CP0McLeU5KMmk5yrszT4/FWxcb12t/ikbIrYqz7HhXO34xlR2XixJQIXBFzyV/Em9CBp2E2lS72j90GXZMkA3Yha+w6ziUxZAKnIEoTqHXJjqgZnHPv4h0H25XFSx7C+4g17EYbpoZalLb6oIHvHDA6gQoTqgewCAslzumEHrtjjfHlBwlxI4BU3PUDICJWStJa6QltSTn+F9f6t+oGDzEtff3179VZDzKJlHMSxdHHg3ltqKrVqrd6ogUS5qMqH823pUyK8FM4ZxZmz+d8=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1710936278; cv=none; b=2HH+nKz1xYztXHWccQD0UpKm9g4qedFH5Jiy5VenMCny1bFIdsn+YtqfpQT//5wCo/vPz1UHZ9wh3ALi6iZ4be1yZdESi1SEN/rpzb0uf4oTZSfh0HddCuKbH35h/nNgbrdaEZbVrm+hPuJMQjsCQR4UrR7PCU9NzESyY1rpR8PSQ0ehw3o2fUPu3VafPSjr2D/c4anBlhNuCdjrWQYLexXs/GDp8Q78sBTVP+LilwTTwMkZLEOlHkNigrdyXWrNuGgUHevZkf2Q4JtguRX1PD3x7/2XpZDfl8OlR2OP6WtGntFc5JwxIch3+fJgv6MPpPoFA1PD8wvSrdQMdacdVOsNUUNBx9mENbpcDnDdmPSDbrLGT8E2b1OJsMTsa172zF3Ruj+EY80/+GlN4+FOfBuImTe8kypRWt+NocMJnI/l/3w2cS1Yhh0+w43fyvlC9ZwMJ9T9txlORckmCtJTDegXDv88VvCn7DrKIdfUn8MlOg1Fq+Eufc8pUPF8kDUlDhAoWjRKthhPG5OCR7FTDBqPm0twVcFUNghL081B5dmcuFQHdG/RNQHHCA1DRxbXQnaOrG9xhZ168MWyxcYcRlB1bS+hsZyCeFCFr10gT7Xjbw0Ty5CIlprcOf3zcwOkt58+eFneyK12HOeTQhK6nLedVs9jjp4q5U77u/m8zKw=
- Authentication-results: smail; dmarc=none header.from=math.u-bordeaux.fr
- Authentication-results: smail; arc=none
- Cc: pari-users@pari.math.u-bordeaux.fr
- Delivery-date: Wed, 20 Mar 2024 13:04:45 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1710936278; bh=P6nC4286hZy5X3DprxkWp9LSgHAJcRCM+aSQFd0E1O4=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=OHTQQnB4l4Z0aA1/GuWR/JEM52jKzIW87PLrYcek8rYHXwbQ4gzXk9NflOi+CMVrb qqHAHqlxaUafGa6sDcSzJBNFdBxdi+LI10VwCFikpssDmCCpor25oPeEwdFznRw6+2 g6m2Y/GQYpMSRM3+9u4JqofjrzJmzyeX5NLnv1pdmN4egHeWNK9vs7VOg2iyh5fM9u ovNQ+pTydWNn6+vtGVSVzwC6XTxeOX1B7h1gY82cqNGpXd9682Swhgg96OzqLjDhKb O2bHYb4uXWjO8mybyKemv3QuoYunfL8nsJmATIPjKMYhDMNl6JcC6YfbinT/79eUou psKzX3PFiFDRogtRTUwSF6c3bnhdjdiCLZPI1IVYLLVTJ9DKVviY2yAurGDw9CG/39 b1xwL3guFxw0h2es6DW7bf6D8nB0J517Zyq08GrRq/qWqdSh/7Dq2/NOLnbIAU/Vu4 ZjcFBbWPpPmNGQPuwgF2bZRR1mYJ+LH53+JEfswvXAJ/HqdkCtax7Spq2ePbtION81 AHcsitGBp+U+mbQFS2tgSCmwmf6uVVKyO3+SNZ+NAQQxgA4WSjM/e4jkb2EGHulXIA vaWY153Sp4eHy6IJbT2iikCJSljaKWXj+KmX5QGCVBKI9ADqqjENRpw1APtDuz8NEV MtA8sMTEdYhls9k21n5Jb3sU=
- In-reply-to: <78df8c6fb5e60216469075d862f79735@stamm-wilbrandt.de>
- Mail-followup-to: hermann@stamm-wilbrandt.de, pari-users@pari.math.u-bordeaux.fr
- References: <78df8c6fb5e60216469075d862f79735@stamm-wilbrandt.de>
* hermann@stamm-wilbrandt.de [2024-03-20 01:53]:
[...]
> ? isProth(p)=v=valuation(p-1,2);p>>v<2^v;
[...]
> ? c=0;forprime(p=3,4636016641,c+=1);c
> 218629816
> ? ##
> *** last result: cpu time 28,710 ms, real time 28,711 ms.
> ? c=0;forprime(p=3,4636016641,c+=isProth(p));c
> 10000
> ? ##
> *** last result: cpu time 1min, 25,406 ms, real time 1min, 25,408 ms.
> ? c=0;forprime(p=3,4636016641,if(isProth(p),c+=1));c
> 10000
> ? ##
> *** last result: cpu time 1min, 9,411 ms, real time 1min, 9,416 ms.
> ?
>
> So the last two do count Proth primes correctly.
> Can it be done faster sequentially?
Sure. Less readable, though:
isProth2(p) = !(p >> (valuation(p-1,2)<<1))
On my (slow) laptop:
(12:55) gp > c=0;forprime(p=3,4636016641,c++);c
time = 36,980 ms.
%1 = 218629816
Your version:
(12:56) gp > c=0;forprime(p=3,4636016641,if(isProth(p),c++));c
time = 1min, 15,760 ms.
%2 = 10000
Mine:
(12:57) gp > c=0;forprime(p=3,4636016641,if(isProth2(p),c++));c
time = 48,292 ms.
%3 = 10000
Cheers,
K.B.
--
Pr. Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique
Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77
http://www.math.u-bordeaux.fr/~kbelabas/