# Find an unknown very large number

Let's suppose there is a finite unknown number `n` (`n` can be very large, does not necessarily fit 64-bits; think of `BigInteger` in Java or `long` in Python) and a function `cmp(x)` that returns `true` if `x <= n`.

Write a program to determine `n` in minimum number of calls to `cmp`.

-
The minimum number of calls will depend on the probability distribution of possible values of `n`. – Anon. Jan 27 '11 at 21:55
How boundless? If it were infinitely large surely search time would be infinite too. – Thomas O Jan 27 '11 at 22:47
It is finite. Just that you don't know the limits. It's part of the problem. – Alexandru Jan 27 '11 at 22:50
Maybe use a very fast-growing function like Ackermann. – Mechanical snail Aug 16 '11 at 21:03
@Alexadru: The problem isn't that `n` is finite. The problem is that the set of numbers that `n` is a member of is unbounded. We need something like n < `10^10000` if we were to consider the "minumum" number of calls to `cmp`. 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. – Thomas Eding Aug 19 '11 at 0:33
show 1 more comment

Here's my solution in C, based on “binary search”:

``````#include <stdio.h>

int cmp(long x) {
return (x <= 727695360);
}

int main(void)
{
char *p = (char*)cmp;

for (;;) {
long x = *(long*)p++;
if (cmp(x) && !cmp(x+1)) {
printf("%ld\n", x);
break;
}
}

return 0;
}
``````

Granted, there are a number of things that could go wrong, including:

• `cmp` might compute its secret indirectly rather than using it as a literal.
• The compiler might tweak the literal to generate faster or smaller code. For example, `x <= 727695360` could become `x < 727695361`.
• The literal may be broken in half due to the target having a fixed-width instruction set. I do not expect this code to work on PowerPC.
• The target CPU might not like those unaligned `long` reads. This code will cause an address error on a 68000 CPU.
-
 I up voted the originality, but it doesn't work for more convoluted code such as `static long n = time(0) + 12348821`. – Alexandru Jan 27 '11 at 22:36

Double our guess until we exceed `n`, then do binary search. This is a reasonable approach until `n` could be very large, at which point you probably want to do more than doubling at each step.

``````b=1;
while (cmp(b)) b *= 2;
a = b/2;
while (a < b-1) {  // invariant: a <= n < b
m = (a+b)/2;
if (cmp(m)) {
a = m;
} else {
b = m;
}
}
return a;
``````
-

Assuming a uniform probability distribution:

1. Assign x to the maximum value n could be, y to the minimum value
2. Guess n=ceiling((x+y)/2)
3. If cmp returns true, y = the guess; else x = the guess - 1
4. If x=y, done (n=x=y); else goto (2)
-
We don't know the maximum, nor the minimum. – Alexandru Jan 27 '11 at 22:39
Then you can't have an optimal solution. Consider one of the other answers where you start at 1 and do doubling -- it favours low numbers, so the greater the range the less optimal the solution is. – Matthew Read Jan 28 '11 at 0:00
Couldn't you define the optimal solution as the one with the lowest average `cmp() calls` to `range` ratio? It does seem like we would need to know how to model the distribution of possible ranges. – mellamokb Apr 5 '11 at 21:55

# 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)))))))
``````

``````(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
``````
-

Simple non-golf binary search:

``````num = 110134848298567717 # sample number
guess = 1
inc = 1
halved = 0
calls_to_cmp = 0

def my_cmp(x, n):
global calls_to_cmp
calls_to_cmp += 1
return x <= n

while True:
small = my_cmp(guess, num)
if small: # add to guess, increase search field
inc *= 2
guess += inc
else: # subtract from guess, decrease search field
inc /= 2
guess -= inc
print "Guess: ", guess, ", inc: ", inc, "  calls so far: ", calls_to_cmp
if inc == 0:
break

print "Done."
``````

One thing to consider is to initially try tripling or quadrupling for the first few loops: this will determine if the number is "small" (say under 1 million) or "large" and may speed the search up.

-

Just to be a cheeky bugger:

# JavaScript, 34 chars

calls to `cmp`, technically 0

``````c=cmp
i=0
while(c(++i));
``````

NOTE: JavaScript isn't a reasonable language to perform this in as it is restricted to 64-bit numeric values, so a string library would be necessary for managing larger numbers.

-

A solution in pseudocode (assuming x is nowhere near 0):

``````x=0
#Step 1: get upper and lower bounds on the number of digits
#double the number of digits until we go past the number
while cmp(2**(2**x)): x++
mindgt=2**(x-1)
maxdgt=2**x
#Step 2: find bounds on log(number)
while(maxdgt-mindgt!=1):
n=(mindgt+maxdgt)/2
if cmp(2**n):
mindgt=n
else:
maxdgt=n
min=2**mindgt
max=2**maxdgt
#Step 3: straightforward binary search
while(max!=min):
n=(max+min)/2
if(cmp(n)):
mindgt=n
else:
maxdgt=n-1
print max
``````

For a value on the order of 1e40, this method takes 9 calls on step #1, 7 calls on step #2 and about 133 calls in step #3 for a total of 149.

-