Return to Revisions

I may have arrived at some development.

Consider there are "30000 * 30000" number of cores. For each of those cores we distribute s=0..29999, r=0..29999, where n = s (mod 30000) and B = r (mod 30000).

Then, we put a code as follows before we start the while loop.

n = gmpy2.mpz(s)  
D += (n * (n + 1)) / 2
B += r
D -= r * B - (r * (r-1)) / 2

For our original code

import timeit
import gmpy2
import math

A = gmpy2.mpz(12421772708041)
# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"

def factor(A):
    B = gmpy2.mpz(math.sqrt(math.pow(2,1) * 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)
    print(f"interim B: {B}")
    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:
        print(f"[B={B}, n={n}]")
        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")

it took around 1.4 second.

If we put s=9840 and r=5028, then

import timeit
import gmpy2
import math

A = gmpy2.mpz(12421772708041)


# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"

def factor(A):
    B = gmpy2.mpz(math.sqrt(math.pow(2, 1) * 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)
    print(f"interim B: {B}")
    n = gmpy2.mpz(9840)  # 8529840 = 9840 (mod 30000)
    D += (n * (n + 1)) / 2
    B += 5028  # 9879358-4984330 = 5028 (mod 30000)
    D -= 5028 * B - (5028 * 5027) / 2
    while (D != 0 and B <= A):
        if (D > 0):
            B += 30000
            D -= 30000 * B - 449985000
        else:
            D += 30000 * n + 450015000
            n += 30000
    if B > A:
        return output(0, 0, 0)
    else:
        print(f"[B={B}, n={n}]")
        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")

it took less than 1 millisecond.

If we can make automatic copies of numerous similar codes, doing the same task, as what I have referred to at this question

then we are done.

As more cores we operate concurrently, the faster we get. At the answer from the question which I referred to, he says with confidence that if we port the code into C or C++ then we can do the job what we desire.

I'm not an expertise at handling all those C++ stuffs. If somebody could embody what the answer has suggested, please consider posting your answer on this page. I'm sure it will be a valuable source of study for numerous people.