3
$\begingroup$

I recently came up with the following algorithm.

But was given the feedback it was impractical due to too much memory consumption in storing $c!$ it then occurred to me I didn't have to calculate $c!$ and I could get away my simply calculating the last digits of $c!$ and see if that tends to $0$.

The Algorithm So Far

Given: $a<b$ and $ab=c$

We are interested in: $ \frac{c!}{c^\lambda}$

Then its simple to show that:

$$ \frac{c!}{c^a} = \text{integer}$$

whereas,

$$ \frac{c!}{c^{a+1}} \neq \text{integer}$$

The Latest Addition

I realized we don't have to calculate all the digits of $\frac{c!}{c^{\lambda}}$. We can asymptotically expand $c!\sim \sqrt{2 \pi c } (\frac{c}{e})^c $ and then as we are interested in finding if

$$\frac{c!}{c^\lambda} \stackrel{?}{=} \text{integer}$$

$$ \implies \frac{\sqrt{2 \pi c }(c/e)^c}{c^\lambda}(1+ \frac{1}{12(c+1)} + \dots + \text{relevant terms} + \dots) \stackrel{?}{=} \text{integer}$$

where $$ \text{relevant terms} \times \frac{\sqrt{2 \pi c }(c/e)^c}{c^\lambda} = \alpha_0 + \frac{\alpha_{-1}}{10}$$

Where $ \alpha_0 $, $\alpha_{-1}$ are the numbers in the units and first decimal place.

Hence, if:

$$ \text{relevant terms} \times \frac{\sqrt{2 \pi c }(c/e)^c}{c^\lambda} - \alpha_0 = \frac{\alpha_{-1}}{10} \approx 0 $$

Question

Does this make my algorithm viable? What is the running time with the new addition? Does this already exist in the literature?

$\endgroup$
  • $\begingroup$ With regards to "impractical due to too much memory consumption in storing $c!$": not only memory consumption, but also computation time for calculating $c!$. $\endgroup$ – barak manos Aug 2 '16 at 19:25
  • $\begingroup$ Which is why I hope the asymptotic method should work out better :) $\endgroup$ – drewdles Aug 2 '16 at 19:28
  • 1
    $\begingroup$ BTW, a small piece of advice: I wouldn't build up an algorithm that relies on a specific counting base (in your case, $10$), since a number is prime independently of the base used for representing it. $\endgroup$ – barak manos Aug 2 '16 at 19:29
  • $\begingroup$ And to answer your question - no, it doesn't make your algorithm viable, since you have not explained how you plan on calculating the last $2$ decimal digits. $\endgroup$ – barak manos Aug 2 '16 at 19:30
  • 2
    $\begingroup$ And hey, you keep forgetting that an approximation gives you the most significant digits accurately, while giving you the least significant digits inaccurately. So I'm pretty sure that you can forget about retrieving those last two digits using Stirling approximation. $\endgroup$ – barak manos Aug 2 '16 at 19:39
2
$\begingroup$

There was more problems with your previous algorithm than just memory storage. The number of steps it takes to calculate $c!$ -even with Stirling's approximation and only going up to relevant terms- is still tremendous. Numbers get really big farther down the road. For example, the factorial of a number with around $100$ digits (roughly $10^{100}$) should be around the size $10^{10^{100}}$; i.e. larger than comprehension.

On the other hand, consider primality testing algorithms, such as Fermat's test or the AKS test. These compensate for large powers by taking the problem modulo $n$ (or in the case of AKS, modulo $n$ and $x^r-1$). Modular exponentiation is extremely fast, so it dramatically reduces the speed of these algorithms.

Bottom line, factorials are just impractical for integer factorization.

$\endgroup$
  • $\begingroup$ did you read "the latest addition" section? I dont need to explicitly calculate $c!$ but instead only consider "relevant terms" .... Cheers! $\endgroup$ – drewdles Aug 2 '16 at 19:35
  • 2
    $\begingroup$ @AnantSaxena Yes of course I read it. To determine if $c!/c^a$ is an integer, you need to calculate all the digits anyway (or at least all the digits of the integer part of the number). Even if you don't calculate all the digits and solve the memory problem, there is still a computation problem. The number of steps is still tremendous. $\endgroup$ – JasonM Aug 2 '16 at 19:40
  • $\begingroup$ @JasonM Thanks for the clear answer. I'm assuming you mean modular exponentiation dramatically reduces the runtime (or something similar), not the speed, of these algorithms? $\endgroup$ – Servaes May 14 '17 at 11: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.