« Windward / C.U. Code Wars – A Good Time was had by All | Main | I Rock! »

09/03/2011

Comments

Feed You can follow this conversation by subscribing to the comment feed for this post.

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.

// 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);
}


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

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...

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.

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.

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 ???

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.

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);
}

The comments to this entry are closed.

David Thielen

B.I. Tweets

    follow me on Twitter

    Windward Reports

    Quantcast

    • Quantcast