Earlier quoted context omitted.
If I have time later today I'll extend your snippet, but my inclination is that the differences in speed become apparent only with very large numbers. I still suspect my algorithm is about 40-50% faster if you start with a googol.
It seems that the problem involves two parts: 1) To find an upper bound 2) Then divide the remaining region in halves until the number is found. The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That ri…
Excellent response. I think the framing element that was missing is if the random numbers were truly random.