abadfish

August 29th, 2007, 01:04 AM

I saw this in a job posting and thought it was rather interesting:

To Apply:

1.Answer the following: 66 28 31 35 29 3d 3f 3b 66 28 6e 29 20 3d 20 66 28 6e 2d 31 29 2b 66 28 6e 2d 32 29 2b 66 28 6e 2d 33 29 3b 66 28 6e 3c 3d 32 29 3d 6e

Paste your result into the subject line and attach your code in the body.

if you want to see my solution, scroll down

I've translated the ascii stream to be 16-bit hex values. Assuming that is correct, using an ASCII table we get:

f(15) = ? ;

f(n) = f(n-1)+f(n-2)+f(n-3);

f(n <=2) = n

The simplest implementation in C is:

int func(int num)

{

if (num<=2) return num;

return ( func(num-1) + func(num-2) + func(num-3) );

}

Of course you don't want to do it this way! Why? The two biggest reasons are overhead and inefficiency. Let's address these.

Using the following test program:

int main(int argc, char *argv[]

{

int i;

i = func(atoi(argv[i]));

printf("i = %s func(i) = %d\n", argv[i], i);

return 0;

}

If you run this with a value of 36 (the max value before you overrun a 32-bit integer:

% TIMEFORMAT="" time junk 36

i = 36 func(i) = 1748130326

16.24user 0.00system 0:16.27elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k

0inputs+0outputs (0major+155minor)pagefaults 0swaps

It takes 16+ seconds to run this and you use 99% of the CPU. There's a lot of overhead in all those recursive calls.

Its also highly inefficient. Think about what happens when you compute the value of func(36). By the recursive algorithm, you have to compute func(35), func(34), and func(33). In order to compute func(35), you'll have to compute func(34), func(33), and func(32). So you've now done func(34) twice, func(33) three times, etc, etc. You'll computing func() for the lower numbers quite a few times. Why do it multiple times when you only really need to do it once.

To improve upon this, lets do an iterative solution rather than a recursive one. To determine the correct solution, lets see what this algorithm is doing:

i func(i)

0 0

1 1

2 2

3 (f(2) + f(1) + f(0)) = 3

4 (f(3) + f(2) + f(1)) = 6

5 (f(4) + f(3) + f(2)) = 11

6 (f(5) + f(4) + f(3)) = 20

7 (f(6) + f(5) + f(4)) = 37

8 (f(7) + f(6) + f(5)) = 68

9 (f(8) + f(7) + f(6)) = 125

10 (f(9) + f(8) + f(7)) = 230

As you can see, all we really need to keep track of are the previous three computations of func(). This gives us the following code:

int func(int num)

{

int prev1, prev2, prev3, retval;

if (num<=2) return num;

prev1 = 2;

prev2 = 1;

prev3 = 0;

while (num >= 3)

{

retval = prev1 + prev2 + prev3;

prev3 = prev2;

prev2 = prev1;

prev1 = retval;

num--;

}

return retval;

}

Running this code using the same benchmark test we get:

% TIMEFORMAT="" time junk 36

i = 36 func(i) = 1748130326

0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

0inputs+0outputs (0major+155minor)pagefaults 0swaps

The same computation using the iterative method is almost instantaneous and uses almost no CPU time.

To Apply:

1.Answer the following: 66 28 31 35 29 3d 3f 3b 66 28 6e 29 20 3d 20 66 28 6e 2d 31 29 2b 66 28 6e 2d 32 29 2b 66 28 6e 2d 33 29 3b 66 28 6e 3c 3d 32 29 3d 6e

Paste your result into the subject line and attach your code in the body.

if you want to see my solution, scroll down

I've translated the ascii stream to be 16-bit hex values. Assuming that is correct, using an ASCII table we get:

f(15) = ? ;

f(n) = f(n-1)+f(n-2)+f(n-3);

f(n <=2) = n

The simplest implementation in C is:

int func(int num)

{

if (num<=2) return num;

return ( func(num-1) + func(num-2) + func(num-3) );

}

Of course you don't want to do it this way! Why? The two biggest reasons are overhead and inefficiency. Let's address these.

Using the following test program:

int main(int argc, char *argv[]

{

int i;

i = func(atoi(argv[i]));

printf("i = %s func(i) = %d\n", argv[i], i);

return 0;

}

If you run this with a value of 36 (the max value before you overrun a 32-bit integer:

% TIMEFORMAT="" time junk 36

i = 36 func(i) = 1748130326

16.24user 0.00system 0:16.27elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k

0inputs+0outputs (0major+155minor)pagefaults 0swaps

It takes 16+ seconds to run this and you use 99% of the CPU. There's a lot of overhead in all those recursive calls.

Its also highly inefficient. Think about what happens when you compute the value of func(36). By the recursive algorithm, you have to compute func(35), func(34), and func(33). In order to compute func(35), you'll have to compute func(34), func(33), and func(32). So you've now done func(34) twice, func(33) three times, etc, etc. You'll computing func() for the lower numbers quite a few times. Why do it multiple times when you only really need to do it once.

To improve upon this, lets do an iterative solution rather than a recursive one. To determine the correct solution, lets see what this algorithm is doing:

i func(i)

0 0

1 1

2 2

3 (f(2) + f(1) + f(0)) = 3

4 (f(3) + f(2) + f(1)) = 6

5 (f(4) + f(3) + f(2)) = 11

6 (f(5) + f(4) + f(3)) = 20

7 (f(6) + f(5) + f(4)) = 37

8 (f(7) + f(6) + f(5)) = 68

9 (f(8) + f(7) + f(6)) = 125

10 (f(9) + f(8) + f(7)) = 230

As you can see, all we really need to keep track of are the previous three computations of func(). This gives us the following code:

int func(int num)

{

int prev1, prev2, prev3, retval;

if (num<=2) return num;

prev1 = 2;

prev2 = 1;

prev3 = 0;

while (num >= 3)

{

retval = prev1 + prev2 + prev3;

prev3 = prev2;

prev2 = prev1;

prev1 = retval;

num--;

}

return retval;

}

Running this code using the same benchmark test we get:

% TIMEFORMAT="" time junk 36

i = 36 func(i) = 1748130326

0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 0maxresident)k

0inputs+0outputs (0major+155minor)pagefaults 0swaps

The same computation using the iterative method is almost instantaneous and uses almost no CPU time.