Comment on Java Puzzle: Square RootComments−IvyMike13yI'm surprised nobody's given the obvious algorithm yet: while(i < BigInt(2).pow(10000)) ++i;Before anyone complains, this algorithm is correct and does not break any of the rules as far as I can tell. :)I think the timing attack is probably what he's really looking for.Edit: as mattvanhorn pointed out, answer() is void, but that's ok... changed to a "constant time" algorithm. :)−lancefisher13yThe BigInteger is really big.An i7 does about 109 gigaFLOPS, or 109 operations per nanosecond. [1]Suppose we can do 1 guess per operation. There are 2^10,000 possible roots. [2]2^10,000 / 109 nanoseconds is 5.804×10^2991 years. [3]The stars will burn out before you brute force it.[1] http://en.wikipedia.org/wiki/FLOPS[2] http://bit.ly/ZIWkkt (parens in the original link)[3] http://www.wolframalpha.com/input/?i=2%5E10%2C000+%2F+109+na...−IvyMike13yI must dryly point out that this does not invalidate the correctness of the algorithm.−IvyMike13yAs an optimist, I must point out that if Moore's law holds for the next 10000 doublings we'll have the answer in 20000 years, plus 9 picoseconds.−mattvanhorn13yanswer() has a void return, although I suppose you might be able to watch System.out to see if it worked.−raylu13yNobody said you had to stop after reaching that line ;)−nire13yYup, just set a new PrintStream(new ByteArrayOutputStream()) in System.setOut() and you're good.
Comments
I'm surprised nobody's given the obvious algorithm yet: while(i < BigInt(2).pow(10000)) ++i;
Before anyone complains, this algorithm is correct and does not break any of the rules as far as I can tell. :)
I think the timing attack is probably what he's really looking for.
Edit: as mattvanhorn pointed out, answer() is void, but that's ok... changed to a "constant time" algorithm. :)
The BigInteger is really big.
An i7 does about 109 gigaFLOPS, or 109 operations per nanosecond. [1]
Suppose we can do 1 guess per operation. There are 2^10,000 possible roots. [2]
2^10,000 / 109 nanoseconds is 5.804×10^2991 years. [3]
The stars will burn out before you brute force it.
[1] http://en.wikipedia.org/wiki/FLOPS
[2] http://bit.ly/ZIWkkt (parens in the original link)
[3] http://www.wolframalpha.com/input/?i=2%5E10%2C000+%2F+109+na...
I must dryly point out that this does not invalidate the correctness of the algorithm.
As an optimist, I must point out that if Moore's law holds for the next 10000 doublings we'll have the answer in 20000 years, plus 9 picoseconds.
answer() has a void return, although I suppose you might be able to watch System.out to see if it worked.
Nobody said you had to stop after reaching that line ;)
Yup, just set a new PrintStream(new ByteArrayOutputStream()) in System.setOut() and you're good.