Find a positive integer within range using only elementary operations

Question

Background

The platform I'm coding for is an esoteric scripting engine coded some time ago that only has limited capabilities. Because I cannot produce a version of the engine that can be run on its own (it needs to attach to a running instance of a game), I have translated the code into C# with limitations to mimic the scripting environment.

Task

Given a blackbox function, find the secret in the blackbox using the following limitations:

1. You can only declare variables of the decimal type
2. You have access to the elementary operators (+, -, /, *, ==, != ...etc) except for modulo (%)
3. You cannot use library functions (Math.Floor() ...etc)

The function is as follows:

//the function returns the result of the operation between the secret and the input //available operations are: >=, >, <=, <, ==, != public static bool BlackBox(decimal num, string operation) { //the secret is always an integer greater than or equal to 1 //you can assume a maximum value the secret cannot exceed, if it helps //in this example, the maximum is 400000 decimal secret = 317810; if (operation == ">=" && secret >= num) return true; else if (operation == ">" && secret > num) return true; else if (operation == "<=" && secret <= num) return true; else if (operation == "<" && secret < num) return true; else if (operation == "==" && secret == num) return true; else if (operation == "!=" && secret != num) return true; else return false; } 

Implementation

My first thought was to try a binary search but was stumped because I can't use floor/ceil. I settled on using a Fibonacci search to get to the ballpark and follow with a linear search to find the exact value:

public static void Main() { decimal num1 = 0; decimal num2 = 1; //use fibonacci sequence to get close to ballpark while (BlackBox(num2, ">=")) { decimal temp = num1; temp += num2; num1 = num2; num2 = temp; } //use linear search for the last mile while (BlackBox(num1, "!=")) { num1++; } Console.WriteLine("The number is " + num1.ToString()); } 

This works well for small numbers but as the range of the secret grows the linear portion can get quite time consuming (I chose a worst-case example for this implementation for this reason) because the scripting engine is no where near as efficient as C#. My question is how can I improve this algorithm in terms of performance? Or, is there another algorithm that can perform better than Fibonacci search (maybe a binary search implementation is possible)?

Answer 1

My first thought was to try a binary search but was stumped because I can't use floor/ceil.

I'm not sure why you thought that would matter. Once you have a maximum number, all you need is to divide the difference between max and min in half and add it to min on each iteration. Here's a simple example that works for your test case. It might need tweaking for some edge cases.

const int MAX_SECRET = 400000; public static decimal Find() { decimal max = MAX_SECRET; decimal min = 0; while(max - min > 0) { decimal temp = ((max - min) / 2) + min; if(BlackBox(temp,"==")) { return temp; } if(BlackBox(temp, "<")) { max = temp; } else { min = temp; } } return max; } 

EDIT

Did some more thinking on the efficiency of this algorithm. The problem mainly stems from using a decimal to represent an int. A decimal doesn't want to do integer math. One way around this is, to use the rounding functionality when the maximum precision is exceeded, to make a floor function. This greatly reduces the iterations to find the target number.

Here's one way that uses the max precision of C#:

const int MAX_SECRET = 400000; public static decimal Find() { decimal max = MAX_SECRET; decimal min = 0; decimal count = 0; while(max - min > 0) { decimal temp = floor((max - min) / 2) + min; if(BlackBox(temp,"==")) { return temp; } if(BlackBox(temp, "<")) { max = temp; } else { min = temp; } } return max; } const decimal MAX_PRECISION = 10000000000000000000000000000M; static decimal floor(decimal num) { decimal temp = (num / MAX_PRECISION) * MAX_PRECISION; if(temp > num) { --temp; } return temp; } 

This cuts the iterations down to the same level as using int's instead of decimal's. To use this in a different language the MAX_PRECISION constant may need to adjusted.

Answer 2

I know this was not your concern. But let me point out anyway that the BlackBox implementation can be simplified quite a bit.

if (operation == ">=") return secret >= num; if (operation == ">") return secret > num; // ... return false; 

Answer 3

Using @vnp hint I've implemented a dual loop fibonacci to avoid a linear search:

public static void Main() { decimal num1 = 1; decimal num2 = 1; decimal num3 = 0; decimal num4 = 0; decimal min = 0; int count = 0; while (BlackBox(num4, "!=")) { do { num3 = num1; num3 += num2; num1 = num2; num2 = num3; num3 += min; num4 = num1 + min; count++; Console.WriteLine(num4.ToString()); } while (BlackBox(num3, ">=")); min += num1; num1 = 1; num2 = 1; } Console.WriteLine("The number is " + num4.ToString() + " in iterations " + count.ToString()); } 

This version uses only 182 iterations to find the answer; vastly improved over the original but still loses to the binary search.

Answer 4

You can indeed solve this using a binary search. In my solution i implemented a recursive method to solve the problem, although a non-recursive version could easily be implemented as well. This solves the problem within O(log n) iterations. It uses 19 iterations to find the secret number of 317810

private static void Main(string[] args) { int max = 400000; int min = 1; int current = max / 2; binarySearch(max, min, current); } private static int binarySearch(int max, int min, int current) { if (BlackBox(current, ">")) { return binarySearch(max, current, (max + current) / 2); } if (BlackBox(current, "<")) { return binarySearch(current, min, (current + min) / 2); } if (BlackBox(current, "==")) { return current; } // secret number is not within range of max/min return -1; }