mersenneforum.org  

Go Back   mersenneforum.org > Search Forums

Showing results 1 to 25 of 59
Search took 0.01 seconds.
Search: Posts Made By: CraigLo
Forum: Prime Gap Searches 2021-11-04, 14:58
Replies: 48
Views: 4,904
Posted By CraigLo
I always wondered why Seth claimed a factor of...

I always wondered why Seth claimed a factor of 10000 improvement. I would have expected less than 10. Re-computing the mods probably explains it.

In my sieve I use 1 bit per multiplier per...
Forum: Prime Gap Searches 2021-11-04, 06:26
Replies: 48
Views: 4,904
Posted By CraigLo
The advantage of my approach is that you can do...

The advantage of my approach is that you can do much better than Sieve of Eratosthenes. When using a wheel with the first 250 primes, only about 1 in 13 numbers can be prime. It's even better than...
Forum: Prime Gap Searches 2021-11-02, 15:43
Replies: 48
Views: 4,904
Posted By CraigLo
Treesieve looks like it is useful when you want...

Treesieve looks like it is useful when you want to compute C%p for the same C with a lot of different primes. I've never tried it, but it seems like it is better for trial division than sieving....
Forum: Prime Gap Searches 2021-11-01, 06:33
Replies: 48
Views: 4,904
Posted By CraigLo
I use the GPU for everything except for some...

I use the GPU for everything except for some initialization and verifying large gaps.


I skip step 3 (BPSW). For numbers around 264 there is only about a 1 in 1E12 chance of being a SPRP-2. The...
Forum: Prime Gap Searches 2021-11-01, 05:46
Replies: 66
Views: 8,996
Posted By CraigLo
This approach is only useful when it is needed to...

This approach is only useful when it is needed to guarantee that a number is prime. For prime gap searches that probably means only maximal gap searches where we want to make sure we haven't missed...
Forum: Prime Gap Searches 2021-10-25, 22:43
Replies: 66
Views: 8,996
Posted By CraigLo
I've written some code. It isn't finished but...

I've written some code. It isn't finished but it's enough to do some benchmarking.

Using my standard cycle length of 36E9, it takes about 0.18 seconds using my old 65-bit code. This is roughly...
Forum: Prime Gap Searches 2021-10-06, 16:45
Replies: 66
Views: 8,996
Posted By CraigLo
Here is the full list >= 1300 1320 29.7556...

Here is the full list >= 1300
1320 29.7556 18447459329282765737
1320 29.7555 18448829219040457859
1320 29.7553 18454478540221538011
1310 29.5295 18466554803229195359
1552 34.9844...
Forum: Prime Gap Searches 2021-10-04, 05:49
Replies: 66
Views: 8,996
Posted By CraigLo
I made it up to 264 + 260. I'm going to stop here...

I made it up to 264 + 260. I'm going to stop here for now until I rewrite the code.


I was a bit unlucky after finding the 1572 and didn't find any new first occurrences. I found a 1510 which is...
Forum: Prime Gap Searches 2021-09-24, 06:45
Replies: 66
Views: 8,996
Posted By CraigLo
I think you want M = 0.261 instead of .577 in...

I think you want M = 0.261 instead of .577 in your equations.

I use wheels for the first 14 primes (up to 43) so they aren't sieved. I'm currently sieving about 10k primes so the last prime ~=...
Forum: Prime Gap Searches 2021-09-23, 18:19
Replies: 66
Views: 8,996
Posted By CraigLo
Thanks. The goal is to check primality with a...

Thanks. The goal is to check primality with a single Fermat test. The problem is handling pseudoprimes. If a number is a pseudoprime then there is some prime p that divides it. As you have shown,...
Forum: Prime Gap Searches 2021-09-22, 15:21
Replies: 66
Views: 8,996
Posted By CraigLo
Can any of the mathematicians here confirm that...

Can any of the mathematicians here confirm that my approach (post #46) is a valid prime test? If it is I will start to write code to see how fast it is.
Forum: Prime Gap Searches 2021-09-10, 06:47
Replies: 48
Views: 4,904
Posted By CraigLo
I was reading through some of the CGBN...

I was reading through some of the CGBN documentation.

It says CGBN currently requires 4, 8, 16 or 32 thread per CGBN group. What is a CGBN group? Is it a single bignum?

Also, the size must be...
Forum: Prime Gap Searches 2021-09-10, 06:39
Replies: 48
Views: 4,904
Posted By CraigLo
I think you will be better off with a library...

I think you will be better off with a library that is designed to work well with the GPU architecture instead of trying to run GMP in the GPU.

CUMP looks like it is for floating point numbers....
Forum: Prime Gap Searches 2021-09-09, 17:44
Replies: 48
Views: 4,904
Posted By CraigLo
I use GMP for my CPU code but I've only used...

I use GMP for my CPU code but I've only used linux. I have my laptop set up so I can boot into either linux or Windows. I'm not sure if that will work for you.

For the GPU stuff I have written all...
Forum: Prime Gap Searches 2021-09-08, 06:35
Replies: 48
Views: 4,904
Posted By CraigLo
Nice. I started with an old laptop that had a...

Nice. I started with an old laptop that had a 940mx gpu (384 cores I think).



I haven't had a chance to look at the CGBN library yet. It wasn't available when I started a few years ago. One of...
Forum: Prime Gap Searches 2021-09-05, 06:23
Replies: 66
Views: 8,996
Posted By CraigLo
It's faster mainly because there are far fewer...

It's faster mainly because there are far fewer memory accesses. The normal sieve needs to eliminate one out of every p numbers. The psp-sieve only needs to eliminate 1 out of every p*ord(p) numbers....
Forum: Prime Gap Searches 2021-09-03, 17:26
Replies: 66
Views: 8,996
Posted By CraigLo
But normal sieve to sqrt(N) is slow. That's why...

But normal sieve to sqrt(N) is slow. That's why we do the Fermat test in the first place. The psp-sieve should be very fast. Then we only need to normal sieve with a small number of primes and do a...
Forum: Prime Gap Searches 2021-09-02, 15:47
Replies: 45
Views: 9,398
Posted By CraigLo
If a gap has a low Jacobs value then the gap is...

If a gap has a low Jacobs value then the gap is lower than expected. This means the next maximal gap is also likely to have a gap that is lower than expected. Similarly, if the Jacobs value is high...
Forum: Prime Gap Searches 2021-08-28, 06:15
Replies: 66
Views: 8,996
Posted By CraigLo
This might work ... If n is a 2-psp...

This might work ...
If n is a 2-psp (pseudoprime to base 2) and prime p divides n then
n = p, mod (p*ord(p))
where ord(p) is the multiplicative order of 2 mod p...
Forum: Prime Gap Searches 2021-08-27, 20:43
Replies: 66
Views: 8,996
Posted By CraigLo
Edit to above: There was no need to do the...

Edit to above:
There was no need to do the Lucas test at all. If it is a 2-PSP it is known to be composite. You could check if it is a 2-PSP before doing the PRP test. I would probably do this by...
Forum: Prime Gap Searches 2021-08-24, 20:45
Replies: 66
Views: 8,996
Posted By CraigLo
There is a list of base 2 pseudoprimes up to 264....

There is a list of base 2 pseudoprimes up to 264.
http://www.janfeitsma.nl/math/psp2/index

When you guys were doing the search up to 264 it would have been faster to do the Lucas test only if the...
Forum: Prime Gap Searches 2021-08-24, 18:32
Replies: 66
Views: 8,996
Posted By CraigLo
Bases of 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...

Bases of 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 have been proven a deterministic test up to 3.18 * 1023.
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

For 265 this can...
Forum: Prime Gap Searches 2021-08-24, 14:01
Replies: 66
Views: 8,996
Posted By CraigLo
I checked continuously from 264 but I'm only...

I checked continuously from 264 but I'm only doing 1 Fermat test so it is possible that a number is incorrectly called a prime. I think it is unlikely that this has lead to missing a large gap (very...
Forum: Prime Gap Searches 2021-08-19, 19:00
Replies: 66
Views: 8,996
Posted By CraigLo
I've checked up to 264 + 61*1016. In addition to...

I've checked up to 264 + 61*1016. In addition to the 1552 and 1572 I found 7 gaps in the 1400s but the largest is still 1430 so no new first occurrences.
Forum: Prime Gap Searches 2021-08-19, 18:37
Replies: 66
Views: 8,996
Posted By CraigLo
I don't think anyone is working on confirming...

I don't think anyone is working on confirming them. My code can't be used for confirmation. I don't have much CPU resources to contribute and I'm not sure what code others have used. I might be able...
Showing results 1 to 25 of 59

 
All times are UTC. The time now is 14:49.


Tue Dec 7 14:49:38 UTC 2021 up 137 days, 9:18, 1 user, load averages: 1.16, 1.31, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.