Discussion between Mohsen Afshin and tchronis

Mohsen Afshin

06:51

@tchronis I wrapped it all into a function

It worked and printed the composites and removed them

but I don't know why the efficiency is not why I expect

in your latest gcd, each 2,500,000 primes GCD over 1300 samples took near half an hour

Unfortunately, my first run using new method took the same, 25 minutes :-(

It's a nested loop

the outer one over primes

the inner one over partitions of input data

In each iteration of inner loop, I calculate the product of the current partition numbers

so, for my 14 cluster primes, the same set of numbers are caculated 14 times

each partition product has 3.5M digits.

I feared from memory issue

but if I hold them (14 x 3.5M digits number) in memory

then I can save

500-600 seconds for each iteration of outer loop

Mohsen Afshin

07:30

look at this:

10:43:19 Partition 2 finished

10:47:53 Partition 3 finished

Nearly 4 minutes for a partition with 200 numbers

Now look at this:

In[113]:= Timing[ partitionproduct = Fold[Times, 1, func[partitions[[2]]]];]

Out[113]= {178.687500, Null}

In[110]:= Timing[GCD[partitionproduct, pro]]

Out[110]= {62.171875, 1}

In[112]:= {IntegerLength[partitionproduct], IntegerLength[pro]}

Out[112]= {64953267, 23104071}

Of that 4 minutes, 3 minutes was spending on multiplying the numbers and only 1 minute for the GCD

tchronis

08:28

Hi Mohsen. I see in my computer that for big Primes the calculation Prime[i] starts to slow down a lot. So i think a good idea is to store files with products of 10M primes and load them succesively. For example : To calculate the 500M-510M product it takes 864 sec in my machine. But to load it from a file it takes only 60 sec.

But before that , i am sending you my newnotebook here ....

10M is the best cluster. 1 M slows down a lot especially for small primes (below 100M)

No fancy parallelization here not even catch ...

Mohsen Afshin

Hi @tchronis

tchronis

Here i can only upload an Image...

Mohsen Afshin

I send u my note, too

Have dropbox?

tchronis

Yes i show it (you mean here in this discussion ?)

Yes i have : [email protected]

Mohsen Afshin

Ok, let me

tchronis

08:34

I am preparing a nice post but for next week that i will describe all timings in such cases. I will post it in mathematica.stackexchange.com when i find the time.

Mohsen Afshin

I sent

The version I sent you

pre compute all partitions

and will then gcd them

for me the initial multiply should take 14 x 40 seconds before the main loop

tchronis

Nice! I sent you mine with results for the first 500M

Copy the file and run a new version of it to compare with your results!

Each calculation print out the following :

tchronis

Index of 10M for example if 33 then it is for 330-340 million product

Time to calculate primes and product , Memory needed)

Mohsen Afshin

oooff

tchronis

Time to calculate GCD , GCD

Mohsen Afshin

08:42

We should find the right balance of GCD

tchronis

Number of remaining probable prime in prp list.

Mohsen Afshin

I'm not sure if the same operand size is the best configuration

tchronis

I multiplied all func[i] and took gcd with Prod [10M primes]

Mohsen Afshin

Single partition?

for 33 numbers you mean

tchronis

I tested with 1M and it looks that it is slower to calculate GCD .

Originaly 64 , then as you move on from cluster to cluster they reduce to 36 (for 500M)

Mohsen Afshin

08:44

What was the integer length of each operand?

tchronis

I think around 150000 digits for the f product and 50 million for the prime product.

The most time consuming part is the calculation of primes.

The longer the operands the shorter the time you will get for GCD

Mohsen Afshin

you mean GCD of 150K and 50M numbers?

tchronis

Yes

It is calculated in 60 sec

Mohsen Afshin

So it would become the old scenario, inefficiency

tchronis

What do you mean ?

Mohsen Afshin

08:47

In my note, I sent you, the GCD is performed over

tchronis

You can fit in memory 50M length number with no problem...

Mohsen Afshin

60M and 30M numbers

the products of input has 60M

and primes product has 30M

tchronis

You don't have ineficiency because I split in clusters.

So my best senario for a single kernel says :

Mohsen Afshin

So you mean the final GCD operands are nearly same size ?

tchronis

60 sec to load 10M primes product +

60 sec to calculate the GCD

(as long as you have stored them. It needs 10G of disk space to hold them on your drive

Mohsen Afshin

08:51

In fact

I come to a conclusion

that

tchronis

So 2m for 10.000.000 but in a constant rate. The same for 1-10 and the same for 501-510

Mohsen Afshin

if average removing time

for a candidate

be larger than

1/3 of the full primality test using OpenPFGW

then that's the stop point of sieving and factoring

since by sieve

we only remove composites

while by primality test, we prove the primality or compositeness of a number with 100% accuracy

tchronis

YEs , i agree. I suppose you have other mathematical methods to prove primality for the rest (like lucas-lechmer test etc /

Mohsen Afshin

in a prime finding scenario, 1/3 can be a good threshold

As an example, proving a single number of 300K size take me 1 hour

so if I can remove composites

in less than 20 minutes

it's good

tchronis

But from 64 you go very quicly to 36 in this case (i think with good prime product files) you can achive that in 1 hour.

I mean for all of them.

1 hour for all of them ...

Mohsen Afshin

08:56

Actually, my functions differs from the one I posted in my question. so that may differ

tchronis

I will upload in dropbox today my final findings.

Mohsen Afshin

Thank you

tchronis

It is important to have these files constructed in your computer.

Mohsen Afshin

My code is just printing something after half an hour:

11:57:09 Multiplying partitions started

12:18:58 Multiplying partitions finished

12:18:58 Cluster 34 started

12:20:37 Partition 1 finished

12:21:41 Partition 2 finished

12:22:45 Partition 3 finished

12:23:48 Partition 4 finished

12:24:51 Partition 5 finished

12:25:56 Partition 6 finished

tchronis

I am uploading a script for you to do it . Please don't run it in Dropbox as it will create 10Gb total.

Mohsen Afshin

08:58

Ok man, I know ;-)

tchronis

But you have very good timings also !!!

Mohsen Afshin

The last timings?

You know, it's like Agriculture

Seeds are growning

12:25:56 Partition 6 finished

12:27:06 1764240371 divides 169587

12:27:07 Partition 7 finished

12:27:07 Cluster 35 started

12:28:24 Partition 1 finished

12:29:29 Partition 2 finished

Look:

tchronis

:-)

Mohsen Afshin

My MMA RAM usage is 400MB for holding all those 14 numbers of 60M digits

In previous code, 1 cluster was running for 25 minutes

tchronis

Yes... I am not holding them , move to the next cluster and forget the previous...

Mohsen Afshin

09:02

Now, it finishes in 5 minutes

the 5x fold

But you know, I regret that even those that we prove their primility using the long 1 hour tests,

most of them

have small factors

tchronis

Yes. You save half the time easily now...

But you need more computers!!! Are you in a university ?

Mohsen Afshin

I think we (our codes, MMA, other apps ...) are some how slower than what we should be

I'm grad

no

tchronis

So you don't have access to a Grid or something like that ?

Mohsen Afshin

And If I was nothing would change since "I" was going to create a small supercomputer for our university using PS3 in 2007, but ........

No, most of universities in Iran except some 5 top class ones in our capital, don't have and even "don't know" supercomputers or Grid ...

And those top class ones have some baby supercomputers with 1000 to 2000 nodes, I just heard the news ...

tchronis

From what we experienced during the last 5 days , the most important thing is to have a great algorithm. But also if someone else has the same algorithm with you it is better you have a better computing environment.

Mohsen Afshin

09:09

My supercomputer has two nodes and 4 threads :-)

tchronis

:-) nice ... one moment i will send you an interesting link for the future...

Mohsen Afshin

thanks

Wow, removing 5 composite in 20 minutes

tchronis

www.parallella.org

Mohsen Afshin

Free?

tchronis

99$

I think it is very very promising.

Mohsen Afshin

09:14

At first, I though it's a service

It's a hardware

I saw some other news about

supercomputers using Raspery PI

tchronis

Yes as long as you are a programmer and now C++ somehow well!

No raspberry Pi is extremel;y slow...

Even with 32 Rpis you don't get the power of a 4Quad at 3.2Ghz

Parallela is for univerisities for raw research or for us :-)

So Mohsen , i have to go to work. We'll talk again. Have a nice day!

Mohsen Afshin

Thanks for your time

You too

Bye

tchronis

Bye :-)

Mohsen Afshin

19:59

I sieved up to 225,000,000

And left with 1312 numbers to be PRPed. I just started two instance of OpenPFGW after performing thousands of randomization over the final list ... Hope to catch one ...

Transcript for

Discussion between Mohsen Afshin and …