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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Aaron Meyerowitz
    Commented Sep 21, 2012 at 0:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .