last day (18 days later) » 

Stack Exchange
Stack Exchange
08:11
5
Q: Memory management and speed for Fast GCD

Mohsen AfshinLet's say that we have some $300\,\text{K}$ digits (arbitrary function) and want to trial factor with $100{,}000{,}000$ first prime numbers. PRP = {}; Func[Q_] := 77^Q + 2; Do[If[TimeConstrained[PrimeQ[Func[i]], 1, True], AppendTo[PRP, i]], {i, 160000, 161000}] PRP: ($64$ numbers out of $10...

performance-tuning memory prime-numbers
tchronis
tchronis
Why are you taking the product since you are dealing with prime numbers? GCD[Func[i],Pr] will be equal to 1 if and only if GCD[Func[i],everyprime] result will be equal to 1 for every prime of those 20000000. In this way you will save a lot of Memory but maybe will be slower...
Mohsen Afshin
Mohsen Afshin
@tchronis, if p be a factor of n, then GCD[p,n] != 1
tchronis
tchronis
Yes that is true. I am talking about the theorem: Gcd(a,p1*p2*p3*...pn)==1 if and only if gcd(a,pi)==1 for all i from 1 to n where pi are distinct primes.
Mohsen Afshin
Mohsen Afshin
@tchronis, I know that. The same operation using Divisible or GCD by all primes is 10 times slower (230 seconds)
tchronis
tchronis
Maybe you can split the product in let's say 4 sets and with a loop check them all. In that case you will use 1/4 of the memory and become less slower...
Your modification runs faster but you are not exploiting all kernels of your machine with ParallelDo or ParallelTable.
Mohsen Afshin
Mohsen Afshin
08:11
@thchronis, You're correct, actually I if written with Reap and Sow and some parallelizing it would become great
tchronis
tchronis
09:08
Using Reap and Sow seems to me tricky in Parallel Processes. I am thinking about taking smaller prime clusters... it is interesting though. Also I am searching mma's manual about sharing variables in parallel processes...
I saw also your other post about GCD's efficiency and I think this would be interesting to try to improve... Maybe implement a parallel version of GCD.
Mohsen Afshin
Mohsen Afshin
Yep, if it is possible to unleash all resources while removing the numbers as soon as possible, it would become a fast GCD
tchronis
tchronis
I think i got it: I parallelized the calculation of a certain cluster and then i remove from the list the ones that lead to GCD>1
I am testing but i think there is a 2x improvement...
Mohsen Afshin
Mohsen Afshin
Wow
tchronis
tchronis
Also a further improvement can be applied on evaluating for primes from a certain length and on....
I will write a new answer with the latest code...
Mohsen Afshin
Mohsen Afshin
Thank you
tchronis
tchronis
09:22
You are welcome
 
1 hour later…
tchronis
tchronis
10:26
Unfortunately dropping easy cases leaves behind small work for only one kernel that delays the parallelization. I Added my improvements. Use gcd not gcd2. I will at last add a Folding process to improve automation.
Mohsen Afshin
Mohsen Afshin
Thanks, I'll test it
 
1 hour later…
tchronis
tchronis
12:01
I have calibrated the algorithm and it is much faster. I am using the new gcd function and using a repetitive process very efficiently. I will post my result tomorrow. A certain calculation about the maximum memory you want to use is necessary.
The rule is : Try to use as much memory as possible... Now I am calculating for prp and 1000000 primes in only 30sec and with constant growth.
Mohsen Afshin
Mohsen Afshin
Calculating 1M primes product takes 30 sec?
tchronis
tchronis
No Calculating GCD for all prp and 1M primes takes 30 sec.
64 numbers in prp
For small number of primes (under 20M) use fold[i_] :=
AbsoluteTiming[{res = gcd[res, i*1000000, i*4, (i - 1)*4 + 1],
Length[res]}]
And then run :
res = prp; Scan[Print[{#, fold[#]}] &, Range @@ {1, 20}]
To calculate for 20M
Mohsen Afshin
Mohsen Afshin
You initial gcd for me:
In[37]:= AbsoluteTiming[gcd[PRP, 1000000, 4]]

Out[37]= {73.328659, {1, 1, 1002109, 1, 1, 1, 1, 1445419, 1, 1, 1, 1,
1, 1, 1, 14474231, 1, 1, 1, 1, 1, 1, 1, 1227181, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 10287491, 1, 1, 1, 1, 1604461, 1, 1, 1, 1, 1, 1,
1, 22337354293870268089, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}
And the gcd2
71 seconds
using parallelization
The above code isn't complete, ha?
tchronis
tchronis
?
What do you mean : "
The above code isn't complete, ha?"
Mohsen Afshin
Mohsen Afshin
fold[i_] :=
AbsoluteTiming[{res = gcd[res, i*1000000, i*4, (i - 1)*4 + 1],
Length[res]}]
WHere products calculaation?
tchronis
tchronis
12:15
It has to be followed by res = prp; Scan[Print[{#, fold[#]}] &, Range @@ {1, 20}]
and gcd is the latest version. See my post at the end.
Mohsen Afshin
Mohsen Afshin
ok
thanks
tchronis
tchronis
There is a lot of new code so finally i will post a new answer with my final code.
Mohsen Afshin
Mohsen Afshin
thank you
tchronis
tchronis
You are welcome.

  last day (18 days later) »