Hi , thanks. What do you mean randomizing the clusters ? You mean internally (inside the 10.000.000 batch) or externally these 30 batches (for 300M primes ?).

We can do anything but as i think it you may not gain speed (as a matter of fact you may loose some) because smaller primes are more probable to act as divisors.

What could be interesting but i am not sure would be randomize the set of primes and omit lots of them that either are obviously not good or we just can take this risk and move on to higher length primes...

I will change a little bit the code to track the divisors that prove that GCD>1

Hi @tchronis

You're true, randomizing needs chance

The chance to have a divisor in high ranges

so that the divisor comes sonner

sooner

but it's only a chance and pirme numbers doesn't understand it

I'm just running your latest code since last night on a 2000 set of numbers for 100M primes.

It really saves me hours

As an example six numbers are removed within the last hour

or 5 hour saving

Unfortunately, I'm too late and lacks enough time to process all those giant numbers,. ... It's not a maze or game.

I need to break this (primes.utm.edu/top20/page.php?id=53) record for a personal reason, (it's not to list my name in the list)

With a chance of less than 1 percent or even toward zero ...

:-(

A question

I set

noprimesinacluster = 2500000;

Using a single kernel

and 300K numbers

You think what's optimal value for noclusters?

1? 2? or 4?

Breaking records is nice! From my experience most top-scorers - record breakers are using a grid of computers (like in a university) to achieve volume of calculations.

I know

k*2^-1 +- 1

To use a single kernel , use noclusters=1

300K numbers you mean primes ?

ye

So if noclusters=1, maybe it's better to lower noprimesinacluster somehow down to 1000000

Why use only 1 kernel ?

Since I have a core i5 and I need one of the cores for my programming job and the other do the computation

Ok i get it. You could tell Mathematica to use only some of the available kernels...

Not all 4 for example...

No, I'm dual core

Actually, I replaced ParallelTable with Table

for my case

out of my initial 2200 prp by testing up to 35M primes,

I removed some 750 composites

Ok , I understand. For a single kernel evaluation in my machine noprimesinacluster = 10000000 (10M) works great. You have to experiment for smaller primes (like 30K) to establish a good noprimesinacluster. But i think it is somewhere between 1M and 100M :-)

Sorry my mistake ... just a minute...

ok, nop

I also added a timing print to know the interval between detections

Oh, Syntax error

The correct is:

I saw your mathlogic website, It seems there are somebody in the world unleashing MMA power in real case research

Thank you! Yes we are growing mathlogic step by step :-)

Yes you are right you must track a proof of divisibility! The simplest way to do it is exactly as you have done it.

A more sofisticated way is to use a parallel version of Reap and Sow but in this case is just too much work. I would like to work on this to implemented in the future to other projects as well.

the ParallelCatch?

Sorry my error - Reap and Show

There is a post for this in Wolfram's site...

I think for now you are fine with the print modification. If you go massive parallel then you need more....

Yes,

And I won't go beyond these single or dual or at last quad cores

It was very nice working with you in Number theory (this is one of my favorite fields in Mathematics). I hope we meet again soon to explore more interesting problems in Mathematics and Mathematica of course.... I am still wondering why there is not a highly parallelized version of GCD for Mathematica... I would like to see it working on a GPU (CUDA , OpenCL etc). It could boost works like yours by at least 20x

Yea, really, I was thinking about that (GPGPU) already

It's the best

case for these massive tasks require multiple little tests

What GPU do you have ? NVIDIA , ATI ?

Unfortunately, I'm running 6490M ATI lacking both OpenCL and no CUDA ....

I was amazed by CUDA support in MMA8 but couldn't test it

Imagine 100000 stream cores running all those little tests in parallel

I will inform you in the future if i come up with something interesting in this direction!

Thank you

Actually

I use sourceforge.net/projects/openpfgw/files/latest/download

OpenPFGW for PRP testing

after trial factoring.

It has built-in factoring

! I will check it thank you.

but MMA is some 5x or even 10x faster than OpenPFGW trial factoring

Yes MMA's internals are great but secret also ...

If you read my post on another tool

NewPGen

you'll see that

NewPGen is 5x faster than MMA !!!

in sieving

it's tremendously fast

super native Assembly code for multiple forms of numbers

But at last, MMA should beat them all, although MMA is multi paradigm program

Yes that is the secret.. Highly performing compilers.... If you have the right Algorithm of course..

I will check it further...

but it should be the best in every section

In my spare time ofcourse !

Of course

Good progress:

Yes that is a long conversation. Being best at everything is not possible (Best at SUMO and Gymnastics (jumps etc) ) is not possible :-)

I will try to make GCD faster. That will be my next spare time task :-)

OK. Not to take your time. Since like my processor, I'm multi core, too. Chatting, Coding, Computing, Testing, ... :-)

I wish you the best Mohsen !

Thank you very much for spending your time for unknown coders

You are very welcome. We are a growing healthy community and we should help each other to grow together.

Ye, If there was no SO, MMA SE, then I couldn't finish even a single app

That is the good version of globalization!

Yeap

+1 for your post "Fast Sieve Implementation" :-)

Thank, I earn in MMA only by questions, no answer

After a while answering will become a natural habit !

ye, I do mostly in SO

Just a note : You can go to Edit->Preferences->Parallel and set in Local Kernels Manual setting for the number of kernels you want to use...

I know that, thanks @tchronis

Dear @tchronis, one thing I forgot to say is this question

mathematica.stackexchange.com/questions/15062/…

Parallel PowerMod

Unfortunately the nature of PowerMod prevents us from parallelizing

It would be so great if one can write a parallelized version of that

of course, parallel version for a single check not over a list

Also this, yielding to faster codes mathematica.stackexchange.com/questions/23757/…

As I know, proving the primality (involving multiple PowerMod in different bases) of world's records including those 12.9M and 17M digits records took nearly a month on 64 cores cluster. Of course I think they have a parallelized version for those special (2^K-1) forms but a parallel PowerMod for any number can be quite useful. Imagine if resources are available why not prove a number with more processors unless that you are limited with the serial modular exponentiation

@tchronis, I found it out

5x faster !!!

Believe it?

The idea is simple. When one of the GCD operands is large, we waste by letting the other be small, so enlarge it

I took a sample of 10 numbers 4 of which I was aware to be composite with their dividers

I added six other to the list

I calculated a product:

pro = Product[i, {i, Prime[Range[50000000, 55000000]]}];

And test it with a sample :

5 seconds on average

So the full list would take 50 seconds

Now list merge them all

And here it is

10 seconds vs 50 seconds ...

Then it's sufficient to factor the result

FactorInteger[1039989007311842791563433451188495001]

{{995758963, 1}, {996861941, 1}, {1001748581, 1}, {1045877387, 1}}

And it's sufficient to do simple divisibility to map divisors to numbers

Actually now, I do manual checks, can you merge them all together to a new function? Specifically it would be great if we can specify the number of numbers to be merged, 10,100, 1000 ...

Thanks

I think you didn't get this line :

Yes that is interesting , so if i understood correctly , you multiply a number of exponents and then try to find prime-divisors in one step! And then assign which is whom ... Clever! Yes i think there is a trade-off and GCD sure is not linear concerning the number of digits.(i think it is logarithmic). I will test it in my code and get back to you tomorrow or the day after that.!

Thank you

It requires more testing, I doubt to that a little. 5x is very much. although I got the same (80 vs 500) in a sample with 100 numbers although the GCD result was 1

As you go in higher primes the improvement decreases. I am testing to find a composite in the remaining list of 32....

I was going to post this for you "But I set another 100 sample and the result is not yet returned !!! passing the normal (5x100 seconds ...) time "

But fortunately, I was evaluating WRONG cell

look at here

and here

It really works

6.5x ...

Yeah...! I is pretty late here so i will leave my computer calculating... :-)

It's late here too (00:27 AM)

Thanks for your help

Bye! We'll talk tomorrow!

Have a good night

bye

U2 :-)