0
$\begingroup$

I have a computational problem where I need to derive the differences in divisor pairs in as few cpu cycles as possible.

In particular I am interested in divisors of numbers of the form $x^3+3*x^2*y+3*x*y^2$.

For example, take the number $669910141$, this factors into:

$[127, 1; 151, 1; 181, 1; 193, 1]$

and has divisors:

$[1, 127, 151, 181, 193, 19177, 22987, 24511, 27331, 29143,$ $34933, 3471037, 3701161, 4436491, 5274883, 669910141]$.

The values that I am interested in deriving are then:

$669910141-1, 5274883-127, 4436491-151$ etc.

Obviously, factoring and then recombining the factors to obtain the divisors involves a lot of redundancy in regards to wasted cpu cycles.

Given that I have 50 cpus tied up 24/7 performing this type of calculation, I'm posting this question in the hope that there exists an efficient algorithm for this type of work.

For further background, this forms part of a process used for identifying, potentially high rank, Mordell type elliptic curves.

UPDATE:

I finally found a way to get the throughput that I was after. This involved using the FLINT (http://flint.org) library for factoring and a hand coded C program for generating the divisors. This has been effective insomuch as this section of the process is no longer the bottleneck that it used to be.

Kevin.

$\endgroup$

1 Answer 1

2
$\begingroup$

If you know $n$ and $(n/d)-d$ then you can quickly calculate $d$ by $$d=(1/2)\left(\sqrt{((n/d)-d)^2+4n}-((n/d)-d)\right)$$ so getting the numbers you want can't be much faster than finding all the divisors.

$\endgroup$
1
  • 1
    $\begingroup$ I don't know if this is what is desired, but suppose that you are given a list of $k$ primes $p_1 \lt p_2 \lt \cdots \lt p_k$ with product $n.$ Certainly one can produce a list of all $2^k$ divisors $1=d_1 \lt \cdots \lt d_{2^k}=n$ and sort it. Naively with $k \cdot 2^{k-1}$ multiplications but obviously less. How much less? Anyway, all that is really desired is the list of the $2^{k-1}$ values $d_{2^k-j}-d_{j+1}$ Does that allow any speed up? $\endgroup$ Sep 21, 2012 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.