mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Wilson-prime search practicalities (https://www.mersenneforum.org/showthread.php?t=16028)

 jasonp 2011-09-23 11:21

See David Yun's paper 'Algebraic Algorithms Using P-adic Constructions' for a light introduction to p-adic arithmetic. Basically if you have a number modulo p it's treated as an approximation to another number mod p^k for k>1. In p-adic arithmetic closeness is based on how large the residue is, not on its precise value.

(That's at least based on my understanding, of which anything p-adic is close to the limit)

It's traditional for Wilson residues to be measured in terms of how close a 'near miss' they are to declaring p a Wilson prime, though, modified by the fact that they're -1 mod p by construction

 R.D. Silverman 2011-09-23 12:17

[QUOTE=jasonp;272502]See David Yun's paper 'Algebraic Algorithms Using P-adic Constructions' for a light introduction to p-adic arithmetic. Basically if you have a number modulo p it's treated as an approximation to another number mod p^k for k>1. In p-adic arithmetic closeness is based on how large the residue is, not on its precise value.
[/QUOTE]

'closeness' is measured by how close a number is to the [i]nearest[/i]
power of p.

Elements are constructed as follows:

Let f be a monic, irreducible polynomial. Let a be a root mod p. Lift
a (via Hensel) to be a root mod p^2 (a_2), then p^3 (a3) , ..... The sequence

.....a_3 a_2 a_1 a_0 is a p-adic number. Note that it extends
infinitely to the LEFT. These numbers (believe it or not) form a field

 Random Poster 2011-09-24 09:29

[QUOTE=R.D. Silverman;272507]'closeness' is measured by how close a number is to the [I]nearest [/I]power of p.[/QUOTE]
I have no idea what that's supposed to mean. By definition, the distance between two p-adic numbers a and b is determined by the largest integer n such that p^n divides a-b; the larger n is, the smaller the distance. In the context of this thread, the question is about the p-adic distance between (p-1)! and -1, or in other words, what is the largest n such that p^n divides (p-1)!+1. For true Wilson primes n>=2, but for any other prime n=1, so this is completely useless for distinguishing what are near-Wilson primes.

 R. Gerbicz 2011-09-25 07:12

There will be a parallel code for multicore computers (though still not finished). Moreover there are some really nice algorithmic improvements from Edgar Costa and David Harvey.

 rogue 2011-09-25 12:55

[QUOTE=R. Gerbicz;272683]There will be a parallel code for multicore computers (though still not finished). Moreover there are some really nice algorithmic improvements from Edgar Costa and David Harvey.[/QUOTE]

I pointed them to this search. It'll be interesting to see what you come up with once you put your brains together.

 Jeff Gilchrist 2011-09-25 18:24

[QUOTE=R. Gerbicz;272683]There will be a parallel code for multicore computers (though still not finished). Moreover there are some really nice algorithmic improvements from Edgar Costa and David Harvey.[/QUOTE]

That would be great since things are starting to slow down now.

Any idea how much of an improvement these algorithmic changes will be? As in should we pause our search temporarily until the new code is ready?

 R. Gerbicz 2011-09-25 19:15

[QUOTE=Jeff Gilchrist;272705]
Any idea how much of an improvement these algorithmic changes will be? As in should we pause our search temporarily until the new code is ready?[/QUOTE]

Seeing only the parallel part: running on c cores the code would be faster by approx. c/2, even for c=16. David Harvey's improvements gives a gain factor of (at least) two in speed.

You can pause, but what I can tell you that due to the algorithmic changes the new code's savefile will be different from what we are currently using in wilsontest. So it won't recognize it.

 Jeff Gilchrist 2011-09-25 23:51

[QUOTE=R. Gerbicz;272708]You can pause, but what I can tell you that due to the algorithmic changes the new code's savefile will be different from what we are currently using in wilsontest. So it won't recognize it.[/QUOTE]

Sounds good. When I said pause, I meant once I have finished my current jobs in progress, wait until the new code is ready, not literally pause a file part-way through. But that is good to know.

Any ETA on when this will be ready?

 R. Gerbicz 2011-09-26 18:40

[QUOTE=Jeff Gilchrist;272722]
Any ETA on when this will be ready?[/QUOTE]

I hope it will be less than a month.

 Jeff Gilchrist 2011-10-02 13:09

I have now finished both of my ranges 200e9 to 250e9 and 270e9 to 300e9.

One new near-Wilson prime found:
[CODE]298114694431 -1+82p
[/CODE]

I will reserve more ranges when the new code is ready.

 rajula 2011-10-03 09:06

I have now finished the range from 250e9 to 270e9. There were three near-Wilson primes:

[CODE]
258818504023 -1+4p
260584487287 -1-52p
265784418461 -1-78p[/CODE]

I will also wait for the new version before continuing.

All times are UTC. The time now is 12:35.