Programming outside the box – count to a million using 16 bits

I got this problem from a co-worker and I think it does a good job of seeing if a programmer can think outside the box.

1. You have 16 bits available for data storage between calls.
2. Compose a function, and find a way to know when the function has been called approximately one million times.
3. You MAY NOT use any additional memory space other than the 16 bits given.
4. Recursion may be used for efficiency, but, again, you MAY NOT use memory definition inside the recursion frames: only the 16 bits.

Figured it out? Post the answer in a comment. Haven't figured it out? Don't read the comments until you do!

It took me about 3 minutes of working through approaches that wouldn't work until I got that a-ha moment.

Comments

[Nicolas]

I would say that the function just need a counter with 16 bits (from 0 to 65535) and you increase it by random rougly 1 time out of 15,29 at each call.

[shogg]

// count to a million using 3 bits:

fn(0);

void fn(byte expo) {

if(expo == 0x110) { return; }

fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
fn(expo+1);
}

[MMI]

int calledNTimes(WORD *word) {
if(word > 50000) return 1;
if(rand() % 4 == 0) *word += 1;
return 0;
}

[Ivan]

We measure the time it takes the function to execute. Will probably need to run the function, say 1000 - 10 000 times in a loop. We can use the 16 bits to store the time, and for counting. Then we calculate how much time it will take to execute (approximately) 1 000 000 times, and store it in the 16 bits - store it in seconds, or tens, or hundredth of a second - as accurately as possible, as long as it fits in 16 bits.
The function will have to contain in it the code (of course this code has to be there when we measure the exec time too) that will get current exec. time, and subtract it from the number we have stored (might need to multiply, depending on whether we stored seconds, or hundredth, etc). When we reach 0 - we stop.
Something like that should work, I guess...

[Matt]

What's storage exactly in this case? Is it some space we have to store lets say for example a counter? Or is it our maximum memory we can use for our function? Or can use use as much memory in our function as long as the "state" between the calls is 16bits or lower?

I'll take it that by 16bits of storage you mean that we can store a counter in those 16bits. So, taking into account that it's supposed to be "approximately" and not "exactly" 1mln calls, I'd simply use a rand function and add a number to the counter every 1000/65 ~= 15th/16th function call (since 2^16 ~= 65k).

Can't agree with you that it's a good test for programmers. It simply shows can you tackle "hard", yet useless problems. I mean I've been working only for 2 years now but never had I faced anything similar. I think there are better ways to test whether or not someone is a brainiac.

[Jørgen Wessel]

Solution is based with the emphasis on the "approxomatly" part, not exact.
Assuming 1'000'000 / 16^2 equals about 16, updating the 16 bit counter only every 16 times will allow the counter to count until the desired one million.
With the large number of calls, a random generated number between 0 and 16 will provide a statistically signifant number with low error margin.

[Michal]

class Counter {
short counter = 1;

public boolean tick() {
if (System.nanoTime() % 15 == 0) {
counter++;
}
return (counter == -1);
}

int getApprox() {
return ((counter < 0) ? (Short.MAX_VALUE * 2 + counter) : counter) * 15;
}
}

what about this java solution ???

[Sury Soni]

Store two numbers in 16 bits (possibly product or may be power of two prime numbers)
1 = 1x1
2 = 2x1
3 = 3x1
..
..
..
12 = 4x3
..
..
234 = 117x2

or
1 = 1 ^ 1
2 = 2 ^ 1
256 = 16 ^ 2

I believe, by distributing 16 bits among two numbers, we can get large sequence of numbers as a product or power of those two numbers.

Don't know yet, what could be the best way to write a quick program for that.

Otherwise doing multiple arithmatic operations on those two numbers to get more unique numbers.

[Igor Kolesnik]

May be something like this. The function f() is called 16 x 65,535 times.

void f(unsigned short n)
{
if (n != 0)
f(n << 1);

while (n++ != max(unsigned short))
{
// do something
}
}

int main()
{
f(1);
}