Clojure - 161 chars
Solution using BigInteger arithmetic and successive squaring / square roots to home in on answer. I believe this usually results in less comparisons than binary search for large values of n - typically close to the number of bits in the binary representation of the answer, which is the theoretical optimum if you only have a binary comparison available.
(use'clojure.contrib.math)(defn find[](loop[l 0 h nil](let[t(+(if h((exact-integer-sqrt(* l h))0)(* l l))1)](if(= l h)l(if(cmp t)(recur t h)(recur l(dec t)))))))
Expanded for readability:
(use 'clojure.contrib.math)
(defn find[]
(loop [l 0 h nil]
(let [t (+ (if h ((exact-integer-sqrt(* l h)) 0) (* l l)) 1)]
(if (= l h) l
(if (cmp t) (recur t h) (recur l (dec t)))))))
Note that the conciseness of the solution is considerably helped by the fact that Clojure automatically uses BigIntegers once values go outside the 64-bit long range.
In action:
; counter for compares
(def counter (atom 0))
; value to find
(def n 100000000000000000000000000000000000000000000000000000000)
; compare function
(defn cmp [x]
(do
(swap! counter inc)
(<= x n)))
;let's find it!
(find)
=> 100000000000000000000000000000000000000000000000000000000
; how many calls to cmp?
@counter
=> 203
; how close to theoretical optimum?
(.bitLength 100000000000000000000000000000000000000000000000000000000)
=> 187
n
. \$\endgroup\$n
is finite. The problem is that the set of numbers thatn
is a member of is unbounded. We need something like n <10^10000
if we were to consider the "minumum" number of calls tocmp
. You need to start at some finite number and consider growing from it. The problem is what number is optimal to start with. Without a bound, there is not optimal start (there might be unoptimal starts, but I haven't given it much thought). To sum things up, "minimum" and "unbounded" make this problem not well-defined. \$\endgroup\$