3 ms·
This is seriously awesome. Got to love when you make a blog post about a 20x speedup, and the internet returns the favor with an Infx speedup.
by te 11y ago
This is seriously awesome. Got to love when you make a blog post about a 20x speedup, and the internet returns the favor with an Infx speedup.
- nanis 11y agoYou need to keep in mind, though, that the factors of 9999999999999999999999999999999999999999 need to be found somehow. Sure, one can "cheat" and use the factors of 1111111111111111111111111111111111111111 and a couple of extra 3s, but, then you have avoided the problem. That is fine normally, but just not an apples-to-apples comparison.
- Someone 11y agoFirstly, lots of work has been done here. See for example http://www.worldofnumbers.com/repunits.htm http://www.worldofnumbers.com/repunits.htm (factorizations of repunits up to 8580 digits). I also think repunits are, in general, easier to factor because ones that do not have a prime number of digits have obvious divisors. Certainly, rep units of up to 50 digits are factored easily (Google a bignum factorization program online, and try for yourself) Even disregarding that, the original code computed a square root about sqrt(n) times (that's why its running time went up by a factor of 10 for every two digits added). Even without using advanced factoring algorithms, you can factor that number using, at the very most, sqrt(n) trial divisions.