Fibonacci Guessing Game - supposed problem needs review

Good evening, Rodion,

This task is implemented correctly from my point of view, except of one thing - the checker does not round results to 2 digits after decimal point as requested in task description.

Rodion,

Thanks for another nice problem. The problem description makes an interesting comparison between the binary split and the Fibonacci split. I was expecting this to be reflected in the required answer; something along the lines of calculating the expectation values for both methods, rather than just the Fibonacci method.

The probklem is live now so it should stay as it is. However, there is still scope to add another problem which calculates the expectation values for a binary split. This is a slightly harder version of the original problem but also has the advantage that there is a much larger choice for the maximum number in each case.

Rodion,

The binary split can be done with any maximum number. The split range is either two equal numbers or two numbers which differ by 1. I was expecting to have to give two values for each test. One is the value that you asked for and the other was the expectation value for the same maximum number but using a binary split.

For example, with the test data in your problem; the first test starts with a maximum value of 21 which is then split into 13 and 8 using the Fibonacci approach. The binary approach would split the 21 into 11 and 10. Continuing with the binary splitting would lead to a different expectation value. I had exopected that both would be given for the answer to each test.

If a binary split is used for a separate problem you can clearly use any integer as a starting point so problem data values are very unlikely to be reproduced in successive data sets.

Another minor point; I would have chosen to round to 4 (or even more) decimal places. The 2 decimal places might allow a lengthy simulation approach; perhaps this was even intended.

Rodion,

I realised that there is a simple calculation for numbers which are an exact power of 2. The Fibonacci numbers are not powers of 2 so the expectation calculation gives a significantly different value from the binary log. For other starting numbers the difference is not as great because you get fewer splits where one part of the range differs from the other by 1. Nevertheless there is still a significant difference when we go to 4 decimal places. Including an occasional starting number which is a power of 2 would not be a problem. I think that you have to go through the splits to calculate the final answer. I don't think you can just apply some formula to the starting number.

We don't actually have to go anywhere with this. I just thought it was an interesting idea, stemming from the fact that I had expected the comparison when reading your problem. The first example of 21 in your problem description has an expectation value of 4.57 with the Fibonacci approach and 4.48 with the binary approach. The latter is better, as expected. For comparison, the binary log gives 4.39.

Rodion,

I am more than happy to create the problem. I will have a close look at how it behaves over the full range of numbers and then send a proposal to you, probably tomorrow. I envisage something fairly similar to your previous problem but with the binary split. I prefer to go with 4 decimal places (dependent on what the numbers actually look like). The solution will need to be more sophisticated than the simple approach that I took with the Fibonacci version.

Update: I've just checked the numbers and 4 decimal places work well over the full range.

Rodion,

I have now created the problem. It should be in your e-mail.

What computer scientists care about: it's both O(log(n)). :)

Of course we are here on CodeAbbey, and thus we are curious about the ratio of the required steps for both approaches when we use Fibonacci numbers as inputs:

i=3,  fibonacci=2, ratio=1.0000, fibonacci_steps=1.0000, binary_steps=1.0000
i=4,  fibonacci=3, ratio=1.0000, fibonacci_steps=1.6667, binary_steps=1.6667
i=5,  fibonacci=5, ratio=1.0000, fibonacci_steps=2.4000, binary_steps=2.4000
i=6,  fibonacci=8, ratio=1.0417, fibonacci_steps=3.1250, binary_steps=3.0000
i=7,  fibonacci=13, ratio=1.0204, fibonacci_steps=3.8462, binary_steps=3.7692
...
i=96,  fibonacci=51_680_708_854_858_323_072, ratio=1.0408, fibonacci_steps=68.2482, binary_steps=65.5723
i=97,  fibonacci=83_621_143_489_848_422_977, ratio=1.0413, fibonacci_steps=68.9718, binary_steps=66.2352
i=98,  fibonacci=135_301_852_344_706_746_049, ratio=1.0416, fibonacci_steps=69.6954, binary_steps=66.9093
i=99,  fibonacci=218_922_995_834_555_169_026, ratio=1.0409, fibonacci_steps=70.4190, binary_steps=67.6518
i=100,  fibonacci=354_224_848_179_261_915_075, ratio=1.0411, fibonacci_steps=71.1426, binary_steps=68.3336
...
i=196,  fibonacci=40_934_782_466_626_840_596_168_752_972_961_528_246_147, ratio=1.0420, fibonacci_steps=140.6089, binary_steps=134.9360
i=197,  fibonacci=66_233_869_353_085_486_281_758_142_155_705_206_899_077, ratio=1.0416, fibonacci_steps=141.3325, binary_steps=135.6848
i=198,  fibonacci=107_168_651_819_712_326_877_926_895_128_666_735_145_224, ratio=1.0417, fibonacci_steps=142.0561, binary_steps=136.3743
i=199,  fibonacci=173_402_521_172_797_813_159_685_037_284_371_942_044_301, ratio=1.0422, fibonacci_steps=142.7797, binary_steps=136.9953
i=200,  fibonacci=280_571_172_992_510_140_037_611_932_413_038_677_189_525, ratio=1.0417, fibonacci_steps=143.5033, binary_steps=137.7581

That's of course no proof whatsoever, but it looks like the Fibonacci approach takes <5% more steps than the binary one.

Rodion,

Thanks for posting the problem and for adding an example, which I forgot to add in my haste to send things to you. I had intended to use the data from the Fibonacci problem as the example for this one, so that the comparison which I had expected initially would be made between the two problems. The example which I had in mind is given below. Perhaps you can add it to the problem? Please accept my apologies for omitting it.

input data:
4
21
377
2584
75025

answer:
4.4762 8.6419 11.4149 16.2530

I found the analysis from you and Mathias very interesting.