Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

A simple example that shows the necessity of the initial nth power check.

Ex: Integer to be tested: 618635360810231509039527102613509910454848893448271939089213219747566591466985089268318751296010673667993589587592240402603239659634192884464647028427726414165757266167241441

That's a 174-digit number. There are about 10^87 174-digit powers, so if you're choosing numbers at random you'll get one every 10^87 tries. The time saved, in your example, is trial division to 10^9 of one 174-digit number, plus one M-R test of a 174-digit number; this is about 9 seconds. The extra time taken is 4 microseconds * 10^87 > 10^74 years.

So your proposal is a waste of time, in that it saves 9 seconds at the cost of 126000000000000000000000000000000000000000000000000000000000000000000000000 years.

Now you might object, realizing that almost all large powers are squares. That's a fair criticism: you could test for squares in less than a tenth the time. (And that test would catch an eight power!) In that case you're saving the same amount at the cost of only 10100000000000000000000000000000000000000000000000000000000000000000000000 years. But I could strike back, noting that the test to 10^9 is too much; replacing it with a test to 10^7 would cause an extra 10^87 * 0.0077 M-R tests (at 400 microseconds each) but save about 10^87 * 8 seconds. That's serious net savings for 'our' method against yours.

[3.14159]

That's a 174-digit number. There are about 10^87 174-digit powers, so if you're choosing numbers at random you'll get one every 10^87 tries. The time saved, in your example, is trial division to 10^9 of one 174-digit number, plus one M-R test of a 174-digit number; this is about 9 seconds. The extra time taken is 4 microseconds * 10^87 > 10^74 years.

So your proposal is a waste of time, in that it saves 9 seconds at the cost of 126000000000000000000000000000000000000000000000000000000000000000000000000 years.

Note: I'm not AIMING for an nth power. I'm weeding them out beforehand via an nth power check. The point is invalidated entirely. My intention: Weed them out beforehand, so there is no time wasted performing the Miller-Rabin test on an nth power.

Hopefully this clears things up.

Now you might object, realizing that almost all large powers are squares. That's a fair criticism: you could test for squares in less than a tenth the time. (And that test would catch an eight power!) In that case you're saving the same amount at the cost of only 10100000000000000000000000000000000000000000000000000000000000000000000000 years.

There is no objection; You raised a strawman point.

That's serious net savings for 'our' method against yours.

It is, compared to your strawman of it. But it's only truly a few ms + a few seconds + a few more ms.

[10metreh]

Imagine trying to find EVERY prime up to 10^100. You have to perform 10^100 nth power checks. Imagine you can do one every microsecond. Then the nth power tests will take 10^94 seconds. These tests save ~10^50 TF+MR runs.
Of course, for most numbers, only a teeny weeny bit of TF should be done. But let's imagine that we have to run your full TF and MR on every number. That will obviously take a lot longer than is necessary. If each TF+MR takes 10 seconds, then 10^50 of them will take 10^51 seconds. That is WAAAAAAY less than the nth power tests took, even though we ran TF to 10^9 and MR on every single number. In fact, even if each nth power test took just 1 Planck time, all the nth power tests would still take >10^55 seconds, which is STILL greater than the time taken to run TF to 10^9 plus one MR run (on a slow computer) on all the nth powers.

[3.14159]

Imagine trying to find EVERY prime up to 10^100. You have to perform 10^100 nth power checks. Imagine you can do one every microsecond. Then the nth power tests will take 10^94 seconds. These tests save ~10^50 TF+MR runs.

Such a list would be impossible to store.

Imagine you can do one every microsecond. Then the nth power tests will take 10^94 seconds. These tests save ~10^50 TF+MR runs.

Right..

Of course, for most numbers, only a teeny weeny bit of TF should be done.

Trial division up to 10^9 would completely factor any number up to 1000000014000000049, so the first 1000000014000000048 integers are factored entirely. Albeit, if I were to do this to every integer, it would take about .. I'd say 2-5 seconds per integer.
2 * 1000000014000000048 = 2000000028000000096 seconds = 63376176515.3243 years at minimum, and at most 5000000070000000240 seconds, or 158440441288.3109 years.

In fact, even if each nth power test took just 1 Planck time, all the nth power tests would still take >10^55 seconds

Your point is..? I'm not making any attempts at testing every integer. But that was an impressive strawman anyway.

If each TF+MR takes 10 seconds, then 10^50 of them will take 10^51 seconds.

If there were no check, it would take 10^101 seconds, by your own maths. !

Tell me: Which is faster: 10^101 seconds, or 10^94 seconds? ! X 2

Even when I use the average figure of 2-5 seconds: 2 * 10^100 seconds vs. 10^94 seconds.

By your own maths, the nth power check would make testing 10^7 times faster.

[3.14159]

Alright: In case you object, I will extend that to 10^500:

Let's make the same assumptions you did. In fact: I will extend the time of the nth power check to 0.5 ms, for realistic figures.

There are about 10^250 nth powers, saving 10^250 trial division and Miller-Rabin tests.

Based on that, the nth power checks would take 5 * 10^496 seconds.

The Miller-Rabin tests, combined with the initial trial division would take 5 * 10^250 seconds, for the numbers which it would test.

If there were no check, it would take about 5 * 10^500 seconds to trial divide and perform the Miller-Rabin test on all 10^500 integers.

10^496 seconds vs. 10^500 seconds.

In general, it would save 5 seconds for every nth power it caught. Between 1 and 10^500, it would save about 5 * 10^250 seconds.

In a more realistic case, it would take 5 * 10^500 - (5 * 10^250) seconds, as opposed to 5 * 10^500 seconds.

[retina]

Originally Posted by 3.14159

If there were no check, it would take 10^101 seconds, by your own maths. !

Tell me: Which is faster: 10^101 seconds, or 10^94 seconds? ! X 2

Even when I use the average figure of 2-5 seconds: 2 * 10^100 seconds vs. 10^94 seconds.

You cannot compare total run time to differential runtime.

That is like the old chestnut: The waiter keeps $2, + the $27 for the three customers, where is the extra dollar?

[3.14159]

You cannot compare total tun time to differential runtime.

Read the other post.

"In a more realistic case, it would take 5 * 10^500 - (5 * 10^250) seconds, as opposed to 5 * 10^500 seconds."

Also: Flinging feces is not recommended.

[retina]

Originally Posted by 3.14159

"In a more realistic case, it would take 5 * 10^500 - (5 * 10^250) seconds, as opposed to 5 * 10^500 seconds."

Also: Flinging feces is not recommended.

Your comparison is still flawed.

Try: "5 * 10^500 - (5 * 10^250) + 5 * 10^496 seconds, as opposed to 5 * 10^500 seconds." instead.

[3.14159]

Try: "5 * 10^500 - (5 * 10^250) + 5 * 10^496 seconds, as opposed to 5 * 10^500 seconds." instead.

1 to 10^500..
10^500 * 0.5 ms per check = 5 * 10^496 seconds total time.
10^250 nth powers save 5 * 10^250 seconds of trial division + Miller-Rabin testing.
Runtime = 5 * 10^496 + (10^500 - 5 * 10^250) seconds, for the numbers that would undergo trial division and Miller-Rabin testing.

Ohshi- You're right.

[CRGreathouse]

Originally Posted by 3.14159

Note: I'm not AIMING for an nth power. I'm weeding them out beforehand via an nth power check. The point is invalidated entirely. My intention: Weed them out beforehand, so there is no time wasted performing the Miller-Rabin test on an nth power.

My point: You spend vastly more time weeding them out then if you simply let the M-R tests catch them, because your tests happen on non-powers as well. The wasted time is many orders of magnitude larger than the time saved (see my post for specific numbers) at any reasonable size.

[CRGreathouse]

Originally Posted by 3.14159

There is no objection; You raised a strawman point.

You're right that my improvement to your method is a strawman. My point was that, even using a technique that makes your method about ten times more efficient, it is still inefficient.