import timeit
import gmpy2
import math
A = gmpy2.mpz(11111111111)
# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"
def factor(A):
B = gmpy2.mpz(math.sqrt(2 * A + 0.25) - 1)
D = gmpy2.mpz(A - (B * B + B) / 2)
while (D > 0):
B += 1
D = gmpy2.mpz(A - (B * B + B) / 2)
n = gmpy2.mpz(0)
while (D != 0 and B <= A):
if (D > 0):
B += 1
D -= B
else:
n += 1
D += n
if B > A:
return output(0, 0, 0)
else:
if (B - n) % 2 == 0:
E = gmpy2.mpz((B - n) / 2)
F = gmpy2.mpz(B + n + 1)
else:
E = gmpy2.mpz(B - n)
F = gmpy2.mpz((B + n + 1) / 2)
return output(A, E, F)
def output(A, E, F):
if A == 0:
print(f"Initial Value Error: Reset the B value")
else:
if A % E != 0 or A % F != 0 or A != E * F:
print(f"[Error Occurred] {A} != {E} * {F}")
else:
print(f"{A} = {E} * {F}")
return 0
if __name__ == '__main__':
if A >= 2:
timer_start = timeit.default_timer()
factor(A)
timer_stop = timeit.default_timer()
running_time = round(timer_stop - timer_start, 6)
print("running time: ", running_time, " seconds")
else:
print("undefined for A<2")
If you are interested in the theoretical background of this code, please consider visiting my anotherother question in CS stackexchange.
while (D != 0 and B <= A):
if (D > 0):
B += 1
D -= B
else:
n += 1
D += n
as somewhat asof a natural step, I've made a guess that wouldn't the computation time become faster by trying the following modification.
import timeit
import gmpy2
import math
import multiprocessing
A = gmpy2.mpz(math.pow(2,29)-1)
# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"
k = 6
# Input the number of cores to be used as "k=..."
# [!!Caveat!!] Don't use too much number of cores which exceeds the
# availability of CPU resources of your personal computer environment.
# It can damage the CPU !!!
def factor(n):
if A < 2:
print("undefined for A<2")
else:
B = gmpy2.mpz(math.sqrt(2 * A + 0.25) - 1)
D = gmpy2.mpz(A - (B * B + B) / 2)
while (D > 0):
B += 1
D = gmpy2.mpz(A - (B * B + B) / 2)
D += gmpy2.mpz(n * (n + 1) / 2)
while (D != 0 and B <= A):
if (D > 0):
B += 1
D -= B
else:
D += k * n + (k * (k + 1)) / 2
n += k
if B > A:
return output(0, 0, 0)
else:
if (B - n) % 2 == 0:
E = gmpy2.mpz((B - n) / 2)
F = gmpy2.mpz(B + n + 1)
else:
E = gmpy2.mpz(B - n)
F = gmpy2.mpz((B + n + 1) / 2)
return output(A, E, F)
def output(A, E, F):
timer_stop = timeit.default_timer()
running_time = round(timer_stop - timer_start, 6)
if A == 0:
print(f"Initial Value Error: Reset the B or k value \n")
else:
if A % E != 0 or A % F != 0 or A != E * F:
print(f"[Error Occurred] {A} != {E} * {F} \n")
else:
print(f"[running time: {running_time} seconds] {A} = {E} * {F} \n")
return 0
if __name__ == '__main__':
n = []
timer_start = timeit.default_timer()
with multiprocessing.Pool(processes=k) as pool:
for x in range(0, k):
y = gmpy2.mpz(x)
n.append(y)
results = pool.map(factor, n)
However, my numerical experiments have shown that the latter code of the multiprocessing module is nowhere faster than the previous code of single-core. So I'm here to ask for a help or any kind of advice from professionals and seniors who are experienced in dealing with parallel computation of algorithms.
- Let's say the code of multiprocessing module prints out any kind of result that correctly demonstrates the value of "A = a * b". In that case, even if the other cores are still running, we assume that the procedure of algorithm is done.
Let's say the code of the multiprocessing module prints out any kind of result that correctly demonstrates the value of "A = a * b". In that case, even if the other cores are still running, we assume that the procedure of the algorithm is done.
In this regard, why is the heuristic computation time of the multiprocessing module version slower than the computation time of the single-core version?
As I've argued above, the speed of reaching the target value is assumed to be faster if the size of the constant being added becomes bigger. For example, 2+2+2... reaches 1000 faster than 1+1+1... and 4+4+4... reaches 1000 faster than 2+2+2... and 8+8+8... reaches 1000 faster than 4+4+4...
My personal computer CPU doesn't allow more than 8 cores to be concurrently operated. So I've couldn't check more than that. Still, trying my best, I've observed that the running time becomes slower when the number of used cores become near 8. Meanwhile, I've observed that the running time of the multiprocessing module version code reached its fastest peak when the number of used cores are 4 or 6. (However, none of them were faster than the running time of the single-core version code)
Would there be any plausible explanation for what I've observed? That is, why the computation time meets its peak at 4 cores or 6 cores instead of 8 cores?
Would the running time of the multiprocessing version code become faster eventually if the number of used cores becomes as much as one desires?
In this regard, why is the heuristic computation time of the multiprocessing module version is slower than the computation time of the single-core version?
- As I've argued above, the speed of reaching the target value is assumed to be faster if the size of the constant being added becomes bigger. For example, 2+2+2... reaches 1000 faster than 1+1+1... and 4+4+4... reaches 1000 faster than 2+2+2... and 8+8+8... reaches 1000 faster than 4+4+4...
My personal computer CPU doesn't allow more than 8 cores to be concurrently operated. So I've couldn't check more than that. Still, trying my best, I've observed that the running time becomes slower when the number of used cores become near 8. Meanwhile, I've observed that the running time of the multiprocessing module version code reached its fastest peak when the number of used cores are 4 or 6. (However, none of them were faster than the running time of the single-core version code)
Would there be any plausible explanation for what I've observed? That is, why the computation time meets its peak at 4 cores or 6 cores instead of 8 cores?
- Would the running time of the multiprocessing version code become faster eventually if the number of used cores becomes as much as one desire?
For extra questions, any tips or advice to increase the speed of the computation would be grateful. I would like to welcome any kind of opinions that could let me think differently forabout approaching this matter. Also, please let me know if any errors are found with my code. Before trying gmpy2 module, I'veI encountered some overflow errors when doing computationcomputations with the original Python. I've not encountered any errors yet with my current code. So please let me know of any kind of error or counterexample if you discover it.
The original questions attached inon this page are also still valid. If there's one, many people would learn a lot about the interaction between hardware and software by the answer, especially for those of the explanation on question 2 and 3.
