5
\$\begingroup\$

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.

\$\endgroup\$
6
  • 7
    \$\begingroup\$ The minimum number of calls will depend on the probability distribution of possible values of n. \$\endgroup\$
    – Anon.
    Jan 27, 2011 at 21:55
  • 5
    \$\begingroup\$ How boundless? If it were infinitely large surely search time would be infinite too. \$\endgroup\$
    – Thomas O
    Jan 27, 2011 at 22:47
  • \$\begingroup\$ It is finite. Just that you don't know the limits. It's part of the problem. \$\endgroup\$
    – Alexandru
    Jan 27, 2011 at 22:50
  • 1
    \$\begingroup\$ Maybe use a very fast-growing function like Ackermann. \$\endgroup\$ Aug 16, 2011 at 21:03
  • 6
    \$\begingroup\$ @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. \$\endgroup\$ Aug 19, 2011 at 0:33

7 Answers 7

7
\$\begingroup\$

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;
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
1
  • \$\begingroup\$ I up voted the originality, but it doesn't work for more convoluted code such as static long n = time(0) + 12348821. \$\endgroup\$
    – Alexandru
    Jan 27, 2011 at 22:36
1
\$\begingroup\$

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)
\$\endgroup\$
3
  • 2
    \$\begingroup\$ We don't know the maximum, nor the minimum. \$\endgroup\$
    – Alexandru
    Jan 27, 2011 at 22:39
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ Jan 28, 2011 at 0:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – mellamokb
    Apr 5, 2011 at 21:55
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.