16 янв. 2011 г.

log2(1M)

Многие задачки, которые задают на собеседованиях появляются рано или поздно на ресурсах типа braingames.ru, что в общем-то и не удивительно.

Так например, fp-сообществу понравилась эта задачка, придуманная в нашем отделе.

По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS
sqrt(2000) = ?
вспомнилась классическая задача, задаваемая у нас:
log2(1000000) = ?


Не предполагается, что ответ будет с точностью до какого знака после запятой (точки) - достаточно оценить с точностью до единицы.

5 комментариев:

GrAndSE комментирует...

sqrt(2000) ~ 45 (45*40=1800, 45*5=225, 45^2=2025)
log2(1m) ~ 20 (2^20=1024*1024)

Vladimir Dolzhenko комментирует...

@GrAndSE: это уж очень грубая оценка, но пойдёт)

GrAndSE комментирует...

Владимир, в задании то с точностью до единицы :) Потому и первое что приходит на ум :) Разумеется, что можно помозговать и придумать более элегантные/точные обоснования и/или решения (хотя для log2(1m) для программиста 20 наверное самое очевидное :) ) А какие бы Вы сами предложили решения?

Vladimir Dolzhenko комментирует...

log2(1M) = log2(10^6) = 6 * log2(10)

log2(8) = 3 < log2(10)
т.е если очень грубо - то
18 < log2(1M) < 20 (используя ваш под подход)

если точнее, то
log2(10) = log2(8 * (10/8)) = 3 + log2(10/8) = 3 + log2(1 + 1/4) = (первый член ряда Маклорена) ~= 3.25

т.е log2(1M) ~= 6 * 3.25 = 19.5

aamonster комментирует...

Фу-фу-фу. 19.5 - более грубая оценка, чем 20.

Если бы мне понадобилось дать оценку точней - я бы начал с первоначальной оценки 20, а потом искал бы поправку:
1e6 = 2^20/A
A = 1.024*1.024 = 1.048576 (ну, в уме бы считал, как 1.05)
logb(1e6) = 20 - logb(A)
Ну а тут или logb(A) считал бы как ln(A)/ln(2) ~= 0.05/ln(2) ~= 0.07
logb(1e6) ~= 20-0.035 = 19.93
либо выписал бы цепочку
A, A^2, A^4, A^8 и так далее и получил бы 1/logb(A), сложив степени членов последовательности, дающих в сумме 2.