Content deleted Content added
add hatnote |
Ltypestar2 (talk | contribs) Adding a way to get a optimal a_max |
||
Line 143:
But the [[Recursion (computer science)|recursion]] is stopped when few ''a''-values remain; that is, when ({{Not a typo|aend-astart}})/{{Not a typo|astep}} is small. Also, because ''a'''s step-size is constant, one can compute successive b2's with additions.
== Optimal <math>a_{\mathrm{max}}</math> ==
=== Premise ===
An optimal <math>a_{\mathrm{max}}</math> can be computed using derivative methods. This derivation assumes you didint use any seiving.
The cost of executing Fermat’s method from <math>\sqrt{N}</math> up to <math>a_{\mathrm{max}}</math> is roughly proportional to a constant we will call <math>d</math>. In the combined method the trial division bound becomes <math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N}</math>. Writing <math>a_{\mathrm{max}} = \sqrt{N} + d</math>, one gets:
<math>a^2_{\mathrm{max}} - N = (\sqrt{N} + d)^2 - N = \sqrt{N}^2 + 2\sqrt{N}d + d^2 - N = 2\sqrt{N}d + d^2</math>
subsututing the new formula we get
<math>a_{\mathrm{max}} - \sqrt{a_{\mathrm{max}}^2 - N} \to a_{\mathrm{max}} - \sqrt{2\sqrt{N}d + d^2} </math>
The goal is to choose a <math>a_{\mathrm{max}}</math> such that <math>C\left(d,N\right) = d + \left(a_{\mathrm{max}} - \sqrt{2\sqrt{N}d + d^2}\right) \to d+ \left(\sqrt{N}+d\right) - \sqrt{2\sqrt{N}d + d^2} = \sqrt{N} +2d - \sqrt{2\sqrt{N}d + d^2}</math> is minimized.
=== Finding the Optimum ===
[[Derivative|Differentiate]] <math>C\left( d , N\right) </math> with respect to <math>d</math>. Due to the linearity of derivatives
<math>\frac{d}{dd} \sqrt{N} +2d - \sqrt{2\sqrt{N}d + d^2} = \frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2d - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} </math>
Notice the <math>\sqrt{N}</math> term dosent depend on <math>d</math> so its derivative respect to d is 0
For the <math>2d </math> term we can use the constant multiple rule to get <math>\frac{d}{dd} 2d \to 2 \frac{d}{dd} d </math> but notice the derivative of <math>d</math> is just 1 so <math>2 \frac{d}{dd} d \to 2 </math>.
For the last term <math>\sqrt{2\sqrt{N}d + d^2} </math> we use the chain rule:
<math>\frac{d}{dd}\sqrt{2\sqrt{N}d + d^2} \to \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}\frac{d}{dd}2\sqrt{N}d + d^2 </math>
Use linearity on the term to get <math>\frac{d}{dd}2\sqrt{N}d + d^2 \to \frac{d}{dd}2\sqrt{N}d + \frac{d}{dd}d^2 </math>
For the first term, use the constant multiple rule and the power rule to get:
<math>\frac{d}{dd}2\sqrt{N}d \to 2\sqrt{N}\frac{d}{dd}d \to 2\sqrt{N} </math>
For the second term use the power rule: <math>\frac{d}{dd}d^2 = 2d </math>
So subsututing known derivatives we get
<math>\frac{d}{dd}2\sqrt{N}d + \frac{d}{dd}d^2 \to 2\sqrt{N} + 2d = 2\left(\sqrt{N}+d\right) </math>
<math>\frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}\frac{d}{dd}2\sqrt{N}d + d^2 \to \frac{\left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}}{2}2\left(\sqrt{N}+d\right) = \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N}+d\right)</math><math>\frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2d - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} = \frac{d}{dd} \sqrt{N} + \frac{d}{dd} 2d - \frac{d}{dd} \sqrt{2\sqrt{N}d + d^2} = 2 - \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N}+d\right) </math>Setting this to 0 gives you the optimal d
<math> 2 - \left(2\sqrt{N}d + d^2\right)^{-\frac{1}{2}}\left(\sqrt{N}+d\right) = 0 \to \frac{\sqrt{N}+d}{\sqrt{2\sqrt{N}d+d^2}} = 2 \to \sqrt{N}+d = 2\sqrt{2\sqrt{N}d+d^2} </math>
Eliminating the square root
<math> \sqrt{N}+d = 2\sqrt{2\sqrt{N}d+d^2} \to \left(\sqrt{N}+d\right)^2 = 4\left(2\sqrt{N}d+d^2\right) </math>
Simplifying
<math> \left(\sqrt{N}+d\right)^2 = 4\left(2\sqrt{N}d+d^2\right) \to \sqrt{N}^2+2\sqrt{N}d+d^2 = 8\sqrt{N}d+2d^2 </math>
Subtract RHS from both sides and combining like terms
<math> \sqrt{N}^2+2\sqrt{N}d+d^2 = 8\sqrt{N}d+2d^2 \to N+2\sqrt{N}d+d^2 - 8\sqrt{N}d+2d^2 = 0 \to N-6\sqrt{N}d-3d^2 = 0 \to 6\sqrt{N}d+3d^2-N = 0 </math>Apply the quadratic formula
<math>d = \frac{-2\sqrt{N}\pm\sqrt{\left(2N\right)^2-4\times1\times\left(-\frac{N}{3}\right)}}{2} \to -\sqrt{N} \pm \frac{2\sqrt{N}}{\sqrt{3}}</math>
Since <math> d > 0 </math> take the positive solution.
Now get the optimal <math>a_{\mathrm{max}}</math> from the optimal <math>d</math>
<math>a_{\mathrm{max}} = \sqrt{N} + d \to \sqrt{N} + -\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}} = \frac{2\sqrt{N}}{\sqrt{3}}</math>
So under then permise of no seiving, optimally you should chose <math> \frac{2\sqrt{N}}{\sqrt{3}} </math>
=== Cost ===
Substute <math> -\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}} </math> for <math>d</math> we get
<math>C\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}},N\right) = \sqrt{N} +2\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) - \sqrt{2\sqrt{N}\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) + \left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right)^2}</math>Simplyfing
<math>\sqrt{N} +2\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) - \sqrt{2\sqrt{N}\left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right) + \left(-\sqrt{N} + \frac{2\sqrt{N}}{\sqrt{3}}\right)^2} \to \sqrt{N}\left(\sqrt{3}-1\right)</math>
So using Fermat + Trial divison we get a cost of <math>\sqrt{N}\left(\sqrt{3}-1\right)</math> which is a imporvement over plain trial division
==Multiplier improvement==
| |||