I'm using mpz_prevprime again this week and I'm so happy it's present as
part of the default libgmp-dev on my distro.
Thanks for being open to me adding this years ago and for everyone's help
getting the code to the place it is!
On Sat, Nov 28, 2020 at 9:08 AM Marco Bod
Ciao,
Il 2020-11-16 21:23 Seth Troisi ha scritto:
Thanks Marco! I'm really happy this is merged.
Your code was merged with a storm of new code that has been reversed.
But now it's in again!
Was there any specific things you thought could be improved? Happy to
look at those too.
Memory us
tprime.c.
> You are right, also the return value of the new function should be
> tested, but I think that we should find a way to check both the result
> and the return value of single runs of the function. E.g. test_largegap
> can check that mpz_prevprime always returns 1 or 2, and r
hould be
tested, but I think that we should find a way to check both the result
and the return value of single runs of the function. E.g. test_largegap
can check that mpz_prevprime always returns 1 or 2, and run_p may take
another parameter so that we can check (depending on the range) if
Ciao,
Il 2020-10-16 09:51 Seth Troisi ha scritto:
won't this cause m = 2*prime, instead of the original result, m = 0?
I used m = (diff > 0 && m) ? prime - m : m;
to make sure that p can be marked as composite.
Oops, you are right!
I fear that the short-circuit evaluation of && can force the
200
+++ b/doc/gmp.texi Thu Oct 15 01:13:43 2020 -0700
@@ -3563,8 +3563,19 @@
@deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op})
@cindex Next prime function
Set @var{rop} to the next prime greater than @var{op}.
-
-This function uses a probabilistic algorithm to identify p
Hi Niels,
> >>> mpz_add_si (p, p, diff * (odds_in_composite_sieve-1));
> >
> > We don't have such a function :-)
>
> Ooops.
>
> Maybe we should have? We do have both _ui and _si versions of other
> basic mpz functions, including mpz_set, mpz_mul, and mpz_cmp.
mpz_addmul_si and mpz_sub
Seth Troisi writes:
> I just figured out how to make it generic (but please let's do this in a
> 2nd change).
Cool! But I agree that should be a followup change. If nothing else, it
has a new failure mode, since it must fail if gcd(start, diff) > 1.
> I'd suggest "negative_mod_ui" or "distance_
"Marco Bodrato" writes:
>>> mpz_add_si (p, p, diff * (odds_in_composite_sieve-1));
>
> We don't have such a function :-)
Ooops.
Maybe we should have? We do have both _ui and _si versions of other
basic mpz functions, including mpz_set, mpz_mul, and mpz_cmp.
Regards,
/Niels
--
Niels Möller
Post scriptum:
Il Ven, 16 Ottobre 2020 7:13 am, Marco Bodrato ha scritto:
>m = mpz_tdiv_ui(p, prime);
>m = (diff > 0) ? prime - m : m;
I remember that, in this context, if p = 0 (mod prime), the result m =
prime is as good as the result m = 0. Because the next two lines are:
if (m &
Ciao,
Il Ven, 16 Ottobre 2020 1:47 am, Seth Troisi ha scritto:
> On Thu, Oct 15, 2020 at 10:44 AM Niels Möller
>> Seth Troisi writes:
>> > Technically I can restructure the code to make both use with
>> mpz_fdiv_ui
>> > static int
>> > findnext (mpz_ptr p,
>> > - unsigned long(*nextm
On Thu, Oct 15, 2020 at 10:44 AM Niels Möller wrote:
> Seth Troisi writes:
>
> > for nextprime sieving the interval 1,000,000 to 1,000,500
> > p is the start of the interval (1,000,000) in this case
> > let prime = 401
> > (-p) % prime = mpz_cdiv_ui(p, prime) = 94
> > the 94th number in the siev
Seth Troisi writes:
> for nextprime sieving the interval 1,000,000 to 1,000,500
> p is the start of the interval (1,000,000) in this case
> let prime = 401
> (-p) % prime = mpz_cdiv_ui(p, prime) = 94
> the 94th number in the sieve (p + 94 = 100094) is the first number
> divisible by 401 in the in
_add_ui);
+ findnext(p, 1, mpz_add_ui);
}
int
@@ -309,7 +320,7 @@
mpz_sub_ui (p, n, 2);
mpz_setbit (p, 0);
- return findnext(p, mpz_fdiv_ui, mpz_sub_ui);
+ return findnext(p, -1, mpz_sub_ui);
}
> > +int
> > +mpz_prevprime (mpz_ptr p, mpz_srcptr n)
>
> Interface looks goo
ent mod functions? I haven't
been following along closely, so I don't know why the current code uses
mpz_cdiv_ui rather than mpz_fdiv_ui. It would make things a bit simpler
if we could use mpz_fdiv_ui (the standard mathematical mod operation)
always.
> +int
> +mpz_prevprime (mpz_ptr p,
On Sat, Oct 3, 2020 at 2:40 AM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-10-03 03:58 Seth Troisi ha scritto:
> >> On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato
> >> Il 2020-03-25 02:25 Seth Troisi ha scritto:
> >> + t = diff > 0 ? ((t + 1) | (t > 1)) :
> >> + ((t == 3) ? 2 : ((t - 2) | 1));
> >>
>
Ciao,
Il 2020-10-03 03:58 Seth Troisi ha scritto:
On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato
Il 2020-03-25 02:25 Seth Troisi ha scritto:
+ t = diff > 0 ? ((t + 1) | (t > 1)) :
+ ((t == 3) ? 2 : ((t - 2) | 1));
Maybe move this to the caller side? Or partially, leaving here just
ASSERT (t >= 2
following.
@deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})
@cindex Previous prime function
Set @var{rop} to the greatest prime less than @var{op}.
If a previous prime doesn't exist (i.e. @var{op} < 3), rop is unchanged
and
0 is returned.
Return 1 if @var{rop} is a
peed -f 1.02 -s 10-260 mpz_prevprime -p1 -P time_prevprime`
> comparing with mpz_nextprime (before and after my change)
>
> On Fri, Mar 27, 2020 at 2:29 AM Seth Troisi wrote:
>
>> Thanks for the quick review and probing comments.
>>
>> On Thu, Mar 26, 2020 at 2:00
I made a few improvements.
tested with '--enable-assert' and verified no impact to timing with
`./tune/speed -f 1.02 -s 10-260 mpz_prevprime -p1 -P time_prevprime`
comparing with mpz_nextprime (before and after my change)
On Fri, Mar 27, 2020 at 2:29 AM Seth Troisi wrote:
&g
Thanks for the quick review and probing comments.
On Thu, Mar 26, 2020 at 2:00 PM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-25 02:25 Seth Troisi ha scritto:
> > I'm back with a new mpz_prevprime patch
>
> diff -r 805304ca965a doc/gmp.texi
> +@deftypefun int
Ciao,
Il 2020-03-25 02:25 Seth Troisi ha scritto:
I'm back with a new mpz_prevprime patch
diff -r 805304ca965a doc/gmp.texi
+@deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op})
+If previous prime doesn't exist (e.g. @var{op} < 3), rop is unchanged
and
+0 is
Thanks for committing this code!
I'm back with a new mpz_prevprime patch
I also added large negative tests for mpz_nextprime
and we can enable test_largegaps now that the default gap is smaller
On Tue, Mar 24, 2020 at 12:45 PM Seth Troisi wrote:
> Code looks great, I don't hav
Code looks great, I don't have any further comments
On Tue, Mar 24, 2020 at 12:21 PM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-24 18:54 Seth Troisi ha scritto:
> > On Tue, Mar 24, 2020 at 9:56 AM Marco Bodrato
> > wrote:
> >> I propose a variation of your patch, you find it attached, on my
>
Ciao,
Il 2020-03-24 18:54 Seth Troisi ha scritto:
On Tue, Mar 24, 2020 at 9:56 AM Marco Bodrato
wrote:
I propose a variation of your patch, you find it attached, on my
computer it's faster.
Couple of small notes but otherwise this looks good
+/* NP_SMALL_LIMIT = prevprime (LAST_PRIME ^ 2) *
On Tue, Mar 24, 2020 at 9:56 AM Marco Bodrato
wrote:
> Il 2020-03-24 01:10 Seth Troisi ha scritto:
> > (I'm don't think your ulong patch is needed but I can measure at a
>
> It's a small patch, but the speed-up it gives is probably too small to
> be worth adding.
>
> > My code doesn't use a sieve
Il 2020-03-24 01:10 Seth Troisi ha scritto:
(I'm don't think your ulong patch is needed but I can measure at a
It's a small patch, but the speed-up it gives is probably too small to
be worth adding.
My code doesn't use a sieve (and instead checks each number for
divisors similar to the old
I didn't see your proposed patch on the March 21st email, we use different
tricks which might be possible to combine.
You suggestion to avoiding miller_rabin by using trial division is where
the core of the speedup for both of our code is coming from.
We both use int instead of mpz_t to avoid the
Il 2020-03-23 22:38 Marco Bodrato ha scritto:
Using unsigned long to compute the modulus is obviously faster than
many calls to mpz_cdiv_ui. I tried a patch that surely is not as fast
as yours, but should speed-up all numbers that fits in a single
unsigned long. The speed-up seems small, I'm not
Ciao,
Il 2020-03-22 10:00 Seth Troisi ha scritto:
I measure the regression as ~5-15% for input < ~10,000
And no regression for larger input? Good.
I have a proposed patch which uses int, and trial div up to some
threshold this appears to be 5x faster.
A couple of question arises.
5x faster
Il 2020-03-21 11:42 Seth Troisi ha scritto:
I see this was pushed, with a few more polishing tweaks.
Yes, but there are bad news, it introduces a speed regression for small
numbers.
I see you also added more testing in tests/devel/primes.c which is a
great triple check.
It looks like the us
Now that this is in I have a much smaller patch to add mpz_prevprime()
My patch includes t-nextprime-tune.c and Makefile.am which should not be
committed but I used
for internal testing and might be useful.
On Tue, Mar 17, 2020 at 10:53 PM Seth Troisi wrote:
>
>
> On Tue, Mar 17, 2020 at
On Tue, Mar 17, 2020 at 3:04 PM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-16 02:23 Seth Troisi ha scritto:
> > On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato
> > wrote:
> >> May I write a few more comments?
>
> > Always, my opinion about being ready is just that it's passed
> > the bar of being
Ciao,
Il 2020-03-16 02:23 Seth Troisi ha scritto:
On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato
wrote:
May I write a few more comments?
Always, my opinion about being ready is just that it's passed
the bar of being good enough not that it's perfect.
I'm tempted to simply commit your propo
On Sun, Mar 15, 2020 at 4:38 PM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-15 00:07 Seth Troisi ha scritto:
> > New patch which is cleaned up and IMO ready to commit
>
> May I write a few more comments?
>
Always, my opinion about being ready is just that it's passed the bar of
being good enough
Ciao,
Il 2020-03-15 00:07 Seth Troisi ha scritto:
New patch which is cleaned up and IMO ready to commit
May I write a few more comments?
On Mon, Mar 9, 2020 at 5:15 PM Seth Troisi wrote:
I also dislike the boiler plate of the macros but I didn't
Those macros should probably be moved to
New patch which is cleaned up and IMO ready to commit
On Mon, Mar 9, 2020 at 5:15 PM Seth Troisi wrote:
>
>
> On Mon, Mar 9, 2020 at 5:03 AM Marco Bodrato
> wrote:
>
>> Ciao,
>>
>> Il 2020-03-09 11:59 Seth Troisi ha scritto:
>> > On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato
>> > wrote:
>> >
>>
On Mon, Mar 9, 2020 at 5:03 AM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-09 11:59 Seth Troisi ha scritto:
> > On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato
> > wrote:
> >
> >> Ciao,
> >>
> >> Il 2020-03-09 02:56 Seth Troisi ha scritto:
>
> > It's highly possible I misunderstand how these macros
Ciao,
Il 2020-03-09 11:59 Seth Troisi ha scritto:
On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato
wrote:
Ciao,
Il 2020-03-09 02:56 Seth Troisi ha scritto:
It's highly possible I misunderstand how these macros are supposed to
be used.
I also dislike the boiler plate of the macros but I didn't
On Mon, Mar 9, 2020 at 2:05 AM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-03-09 02:56 Seth Troisi ha scritto:
> > From Marco Bodrato's analysis I got inspired and modified nextprime to
>
> Your analysis is much deeper than mine :-)
> I do not have much time now... but I glanced at the code and writ
Ciao,
Il 2020-03-09 02:56 Seth Troisi ha scritto:
From Marco Bodrato's analysis I got inspired and modified nextprime to
Your analysis is much deeper than mine :-)
I do not have much time now... but I glanced at the code and write here
a few comments.
You can see some of my thresholds and
>From Marco Bodrato's analysis I got inspired and modified nextprime to uses
a much larger segmented sieve and tuned the prime limit for large inputs.
You can see some of my thresholds and testing input in this google
sheet[1]. The end result is sieve up ~ LOG2(N) ^ (20/7) / 3268
For 1000 bit numbe
Some more justification for my patch
I wrote some code that replaces mpz_millerrabin with a static lookup and
ran it for a number of values.
Existing Code (with real mpz_millerrabin)
100, gap: 1533, 0.00164 seconds
200, gap: 2547, 0.00675 seconds
300, gap: 3757, 0.01161 seconds
500, gap: 3765, 0.
I tried using a segmented sieve. this avoids multiplication or mod in the
inner loop.
It's an improvement and the code is easy to comprehend.
$ ./tune/speed -s 100-300,500,1000 -f 1.1 mpz_nextprime -p mpz_nextprime
$ hg import ~/Downloads/nextprime_segment.patch --no-commit
$ make -j4; make -C tun
"Marco Bodrato" writes:
> Ciao,
>
> Il Mer, 12 Febbraio 2020 7:26 am, Niels Möller ha scritto:
>> And for a small prime gap (common case), this cost should be the main
>> part of the sieving. So it would make sense to optimize it. If we also
>> use the ptab, we could compute modulo single-limb pr
Some observations:
Around N, the average prime gap is log(N). Right?
Therefore, we will probably need to pass log(N) composites on average
for typival usages of mpz_nextprime.
Adding a trial divisor prime p will eliminate 1/p of the composites. We
can see it as being successful with 1/p probab
Ciao,
Il Mer, 12 Febbraio 2020 7:26 am, Niels Möller ha scritto:
> Marco Bodrato writes:
>> Maybe my estimates are wrong. If they are not, the limit for trial
>> division should be increased more than linearly on the size of the
> And current code uses
> prime_limit = nbits / 2;
> Why the co
Marco Bodrato writes:
> Maybe my estimates are wrong. If they are not, the limit for trial
> division should be increased more than linearly on the size of the
> numbers that are tested.
And current code uses
prime_limit = nbits / 2;
And here "prime_limit" is a limit on the number of primes
I worked your math and tested against some Constants I had, everything
agrees.
This also matches much of my analysis in my prime gap search where I scale
my sieve much more than linearly.
On Tue, Feb 11, 2020, 2:13 PM Marco Bodrato
wrote:
> Ciao,
>
> Il 2020-02-10 21:01 ni...@lysator.liu.se ha
Ciao,
Il 2020-02-10 21:01 ni...@lysator.liu.se ha scritto:
On my laptop, it gives a speedup of about 25% for larger sizes. Not
sure
how to tune for small sizes, but clearly the old code clamping the size
of the prime table based on the bit size is better than doing nothing.
The computation of
Seth Troisi writes:
> Did you still limit the trial division to prime_limit?
No, I used *all* tabulated primes (which makes it slower for smaller
inputs). It seems clear that setting prime_limit improves performance
for smaller numbers.
> I'd love to see your code so I can try to understand wha
Did you still limit the trial division to prime_limit?
trialdivtab.h has extra primes (1000 primes up to 10,000 instead of the
first 180 primes up to 1000).
which decreases the percentage of numbers that need prime testing from ~8%
to ~6%
This shouldn't affect numbers less than 200 bits (where you
Seth Troisi writes:
> This was discussed previously in this thread
> https://gmplib.org/list-archives/gmp-devel/2019-September/005465.html
> TL;DR >95% of time is spent in miller rabin.
I tried out using the same dtab table used in trialdiv.c.
On my laptop, it gives a speedup of about 25% for l
umber of repetitions is larger
than some adequately large ammount.
By the way I pushed this version of your patch.
https://gmplib.org/repo/gmp/rev/3507f80aee0a
I was referencing my change for mpz_prevprime which is implemented via
a macro shared with mpz_nextprime
In my opinion, the lo
I've removed the test large gap.
Let's just trust that I've testing my mpz_prevprime patch sufficiently for
that case and not both with checking it in.
The large change I'd like to submit is mpz_prevprime.
The code is here: https://github.com/sethtroisi/libgmp/pull/10
It'
Ciao,
Il 2020-02-05 00:59 Seth Troisi ha scritto:
I got VERY VERY VERY lucky and found a prime gap > 2^15 with the 4th
highest merit of ANY KNOW PRIME GAP.
Great!
Given Marco's timing of 25 seconds (and a goal of say 3 seconds on
that machine) the start prime would need to be ~~200 digits.
On mersenneforum there's a prime gap search project. I tried running a
modified version of their search program.
I got VERY VERY VERY lucky and found a prime gap > 2^15 with the 4th
highest merit of *any know prime gap*.
it's a PRP with 404 digits that could replace the 454 digit prime in the
patch
On Thu, Jan 30, 2020 at 6:23 AM Niels Möller wrote:
> t...@gmplib.org (Torbjörn Granlund) writes:
>
> > We have tried to stick to a limit of 1 s on a reasonable current
> > computer. Most tests should use much less, if possible.
>
> Maybe it would make sense with a command line option or environm
https://github.com/sethtroisi/libgmp/pull/12/files)
I was referencing my change for mpz_prevprime which is implemented via a
macro shared with mpz_nextprime
It was attached to my previous message in this chain (
https://gmplib.org/list-archives/gmp-devel/2019-September/005479.html)
On Thu, J
t...@gmplib.org (Torbjörn Granlund) writes:
> We have tried to stick to a limit of 1 s on a reasonable current
> computer. Most tests should use much less, if possible.
Maybe it would make sense with a command line option or environment
variable to the test binaries to enable certain more expensi
Marco Bodrato writes:
On an ARM processor I'm playing with, before that patch:
$ time tests/mpz/t-nextprime
real 0m0.254s
after the patch:
$ time tests/mpz/t-nextprime
real 0m25.878s
We have tried to stick to a limit of 1 s on a reasonable current
computer. Most tests should use
Ciao,
Il 2020-01-28 23:31 Seth Troisi ha scritto:
There doesn't seem to be any objection to this change and it has good
tests.
I think the macro can be improved (and potentially expanded to
mpz_nextprime_stride) but I hope that can happen after an initial
version is checked in.
I'm sorry, but
There doesn't seem to be any objection to this change and it has good tests.
I think the macro can be improved (and potentially expanded to
mpz_nextprime_stride) but I hope that can happen after an initial version
is checked in.
committing this would also allow me to improve my implementation of
mp
Ciao,
Il 2019-09-03 08:41 Seth Troisi ha scritto:
1. s->reps next_primes chained (next_prime(p, p); next_prime(p, p);)
Currently it takes about 20 seconds to test -s 16-128, and 15 minutes
to test -s 16-1028
with -t 1.04 the resulting graph is much smoother than the old graph.
Also your pro
quence does 'seq' refer
> to in the name.
>
From 353f07c97a7fa142c32119c87ffba0fe925e70bb Mon Sep 17 00:00:00 2001
From: Seth Troisi
Date: Wed, 4 Sep 2019 23:46:10 -0700
Subject: [PATCH 1/3] Add mpz_prevprime
---
gmp-h.in| 3 ++
mpz/nextprime.c | 129 +-
Seth Troisi wrote on 2019-09-03 08:59:
3. add mpz_nextprime_seq(a, b) => next prime a + k*b with k >= 1
Personally I would prefer it named mpz_nextprime_step or mpz_nextprime_stride
or mpz_nextprime_strided. Or even mpz_nexprime_with_step, if that doesn't
violate some naming convention I'm n
Seth Troisi writes:
> Trying to sum up the proposals for how this api should work,
>
> 1. add mpz_prevprime(rop, op) or mpz_precprime(rop, op)
> 2. change mpz_nextprime(-10) => -7 (instead of 2)
> 3. add mpz_nextprime_seq(a, b) => next prime a + k*b with k >= 1
&g
Trying to sum up the proposals for how this api should work,
1. add mpz_prevprime(rop, op) or mpz_precprime(rop, op)
2. change mpz_nextprime(-10) => -7 (instead of 2)
3. add mpz_nextprime_seq(a, b) => next prime a + k*b with k >= 1
Considerations
1. on negative number return X?
Should
; > functions in pari/gp. These differ from gmp by nextprime(p) == p if p is
> > prime. And they don't consider negative numbers to be primes.
>
> Il Mer, 21 Agosto 2019 10:02 am, Seth Troisi ha scritto:
> > Finally for mpz_prevprime(rop, op <= 2) it's not clear
pari/gp. These differ from gmp by nextprime(p) == p if p is
> prime. And they don't consider negative numbers to be primes.
Il Mer, 21 Agosto 2019 10:02 am, Seth Troisi ha scritto:
> Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be
> set to, so I use th
Ciao,
Il Gio, 22 Agosto 2019 10:32 am, Niels Möller ha scritto:
> "Marco Bodrato" writes:
>> I'd suggest to extend the range for mpz_nextprime.
>> Can we consider both positive and negative primes?
> I think that's a bit unusual. We can compare with the corresponding
> functions in pari/gp. Thes
"Marco Bodrato" writes:
> Currently tune/speed usually use the mean of many calls with the same input.
> Maybe for _nextprime we should use a chain? Give the previous result as
> the new input.
Makes sense to me.
> I know that my proposal is an incompatible change for the interface... but
> I'd
ently tune/speed usually use the mean of many calls with the same input.
Maybe for _nextprime we should use a chain? Give the previous result as
the new input.
>> For implementing mpz_prevprime, I tried to reuse as much code as
> Maybe it would make sense to generalize a bit further, and wri
ng, since some numbers will be much slower than others?
> For implementing mpz_prevprime, I tried to reuse as much code as possible
> with a macro for the function body, I'm not sure how readable it ended up.
> it also possible this could be speed up if I used separate code for
to mean size bits instead
of limbs for for measuring mpz_nextprime, as the function is slow (in the
worstcase it can take >5 second for a 1500 bit input, and >90 seconds for a
~2700 bit input)
For implementing mpz_prevprime, I tried to reuse as much code as possible
with a macro for the func
75 matches
Mail list logo
