Find an unknown very large number

Question

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.

Answer 1

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.

Answer 2

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;

Answer 3

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)

Answer 4

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

Answer 5

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.

Answer 6

Just to be a cheeky bugger:

JavaScript, 34 chars

calls to cmp, technically 0

c=cmp
i=0
while(c(++i));
alert(i-1)

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.

Answer 7

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.