2
$\begingroup$

Is there a way to use Parallelize the following operation, in order to make it do the calculations faster? Or is there another way to speed up this calculation?

With[{ropts = SystemOptions["ReduceOptions"]}, 
  Internal`WithLocalSettings[
   SetSystemOptions[
    "ReduceOptions" -> "SolveDiscreteSolutionBound" -> 10^(14)], 
   Solve[y^2 == 2213326116 + 94098 x (1 + x) (-31363 + 31366 x) && 
     10^(13) <= y <= 10^(14) && x >= 2, {y, x}, Integers], 
   SetSystemOptions[ropts]]] // AbsoluteTiming
$\endgroup$
  • 3
    $\begingroup$ No, there isn't a way to parallelize this. $\endgroup$ – Szabolcs Jan 8 at 21:07
  • $\begingroup$ @Szabolcs Ok, and another way to speed it up? $\endgroup$ – Jan Jan 8 at 21:09
  • 1
    $\begingroup$ @Jan speeding up Solve is, obviously, non-trivial. However, in answering your previous question from which you got this code, Roman proposed an alternative to Solve using a brute-force approach. Have you tried it here? $\endgroup$ – MarcoB Jan 8 at 21:37
  • $\begingroup$ @MarcoB yes but it is in no way faster $\endgroup$ – Jan Jan 8 at 21:42
4
$\begingroup$

You want $10^{13}\leq y\leq 10^{14}$, so obviously $10^{26}\leq y^2\leq 10^{28}$. The range of $x$ for which your expression $10^{26}\leq y^2 = 2213326116 + 94098\ x\ (1 + x) (-31363 + 31366\ x)\leq 10^{28}$ can be easily found:

N@Reduce[10^26 < 2213326116 + 94098 x (1 + x) (-31363 + 31366 x) <= 10^28, x]

323584. < x <= 1.50194*10^6

That's not a huge range; we can brute-force test all values of $x$ in that range, and we can do that in parallel, e.g. using ParallelDo:

ParallelTable[
 If[
   IntegerQ@Sqrt[2213326116 + 94098 x (1 + x) (-31363 + 31366 x)],
   x, Nothing
 ],
 {x, 300000, 1600000}
]

This is not exactly fast, but it does finish within two minutes on my 4-core machine, whereas your Solve expression was still chugging away after a couple of minutes. This is an embarrassingly parallel operation, i.e. it suffers from no interdependence or communication overhead, so it should see a nice boost from extensive parallelization on many kernels.

Unfortunately, however, it appears that there are no results in that range that this method could find.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Note that to Sow in parallel is not straightforward. $\endgroup$ – Michael E2 Jan 8 at 22:42
  • $\begingroup$ @MichaelE2 Good point. I even knew that at some point :-( Let me change it to ParallelTable just to avoid that headache. $\endgroup$ – MarcoB Jan 8 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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