I mean, an application could exist where this isn’t even wrong. Maybe as a “subroutine” of another algorithm that only needs a truly composite number most of the time to work.
That this reads as a joke says a lot about what application we’re intuitively expecting.
That’s kind of what I meant by putting “subroutine” in quotes. You obviously wouldn’t write it like this, you’d just use a random large number with a bit of explanation.
Oh well, live and learn. I’ll try to be clearer next time.
I just took the above comment as continuing the joke, but this explanation actually confuses me more.
Well, I don’t really think you need to be very clear in this case. Jokes are more fun when you “get” them rather than have them explained.
I get OP was a joke, but I was trying to make a serious observation.
Say you have some kind of stochastic algorithm that works on the assumption it’s fed a composite number most of the time. Maybe something like Pollard’s Rho algorithm, where whatever number theoretic structure you need accumulates slowly over time as a result. You decide to just pick a large number at random for each iteration.
Implicitly, you’ve solved the problem of finding a composite number by assuming all (large) numbers are composite, like in this post. It is pretty close, like mentioned in this post. If that’s not good enough, you could also use a primality test that fails some small portion of the time, which do exist, and use less power than guaranteed tests.
I mean, an application could exist where this isn’t even wrong. Maybe as a “subroutine” of another algorithm that only needs a truly composite number most of the time to work.
That this reads as a joke says a lot about what application we’re intuitively expecting.
Edit: Not sure why this is being downvoted.
Perhaps because it would do better, being replaced with
noop.A link time optimiser might actually do so.
That’s kind of what I meant by putting “subroutine” in quotes. You obviously wouldn’t write it like this, you’d just use a random large number with a bit of explanation.
Oh well, live and learn. I’ll try to be clearer next time.
I just took the above comment as continuing the joke, but this explanation actually confuses me more.
Well, I don’t really think you need to be very clear in this case. Jokes are more fun when you “get” them rather than have them explained.
I get OP was a joke, but I was trying to make a serious observation.
Say you have some kind of stochastic algorithm that works on the assumption it’s fed a composite number most of the time. Maybe something like Pollard’s Rho algorithm, where whatever number theoretic structure you need accumulates slowly over time as a result. You decide to just pick a large number at random for each iteration.
Implicitly, you’ve solved the problem of finding a composite number by assuming all (large) numbers are composite, like in this post. It is pretty close, like mentioned in this post. If that’s not good enough, you could also use a primality test that fails some small portion of the time, which do exist, and use less power than guaranteed tests.