Метод ферми – Как определить неизвестное: метод Ферми для быстрой оценки чего угодно: matveychev_oleg — LiveJournal

Вопросы Ферми, Парадокс Ферми | Портал об образовании Newtonew

Предыстория

Вопросы Ферми называются так в честь великого итальянского физика Энрико Ферми, обладателя нобелевской премии по физике. Он был известен тем, что мог за короткий промежуток времени оценить абсолютно все.

Известна следующая история: Энрико Ферми присутствовал на полигоне при испытании атомной бомбы Тринити 16 июля 1945 года. Вместо того, чтобы настраивать сложные приборы для оценки мощности бомбы, он достал листок из своего блокнота, разорвал его на мелкие кусочки, и когда после взрыва взрывная волна достигла ученого, он подбросил клочки бумаги в воздух и по тому, как далеко они улетели, определил, что мощность взрывной волны превысила 10 килотонн. В конечном итоге оказалось, что действительное значение мощности было порядка 18,6 килотонн. Таким образом, Ферми смог дать разумную нижнюю оценку взрыва, пользуясь не более чем листочком бумаги.

Кроме того, Энрико Ферми учил своих студентов тому, как оценить что угодно за 60 секунд. Например, одним из самых известных вопросов Ферми является задача об определении числа настройщиков пианино в Чикаго, к которой мы еще вернемся.

Ферми был уверен, что все знания являются взаимосвязанными и что при наличии критической массы фактов, возможно вывести оценки для самых экзотических вещей, включая даже расстояние до ближайшей внеземной цивилизации. К слову, Энрико Ферми также принадлежит парадокс касательно отсутствия следов деятельности инопланетных цивилизаций.

Суть метода

Ответы на вопросы Ферми основываются на двух китах: предположениях и здравом смысле. Для наглядности рассмотрим несколько примеров.

Вопрос: сколько флаконов шампуня производится в мире за год?

При оценке потребительских товаров удобно исходить из собственных потребностей. В частности, вы можете сказать, что используете порядка 1-2 флаконов шампуня в год. Учитывая, что в мире есть менее обеспеченные люди, разумно взять нижнюю границу в 1 флакон на человека и тогда получим, что каждый год производится порядка 7 миллиардов флаконов шампуня.

В данном случае стоит понимать, что точный ответ на этот вопрос, возможно, не сможет дать даже сотрудник компании Procter & Gamble (один из лидеров мирового рынка потребительских товаров) и самое большее, что вы можете сделать, это получить разумную оценку на основе предположений, которые не противоречат здравому смыслу. В частности, если вы участник известной рок-группы, который тратит 3-4 флакона шампуня в год на уход за своей огромной шевелюрой, то рассуждения вида «Я трачу 3-4 флакона в год, поэтому моей оценкой будет 7 миллиардов * 3 или 4» в данном случае будут довольно необоснованны ввиду сильных погрешностей.

Вопрос: у вас есть стопка десятирублёвых монет высотой с Эйфелеву башню. Сможете ли вы уместить эти монеты в среднестатистическую комнату?

В данном случае вы могли бы сделать предположение об объёме комнаты, затем о радиусе монеты, вычислить площадь её поверхности и умножить на высоту всей конструкции, после чего сравнить полученные значения. Однако есть значительно более простой метод.

Предположим, что среднестатистическая комната имеет высоту 2-3 метра, а Эйфелева башня меньше 400 метров (возможно вы помните, что в высоту она составляет 300 метров с чем-то, но для более надежного предположения лучше взять верхнюю границу). В таком случае стопка монет больше высоты среднестатистической комнаты не более чем в 200 раз. Другими словами, теперь вы можете переформулировать вопрос: уместится ли 200 стопок монет высотой до потолка в комнате? Учитывая, что диаметр монеты можно смело ограничить 3 сантиметрами, получаем стену монет длиной в 6 метров, которую можно легко разбить на 10 линий по 60 сантиметров, причем ширина полученной конструкции будет ограничена 30 сантиметрами. Другими словами, такой набор монет можно с легкостью уместить в среднестатистической комнате, то есть ответ на задачу утвердительный.

Вопрос: сколько настройщиков пианино в Чикаго?

Сделаем несколько предположений. Для начала оценим население Чикаго в три миллиона, а число людей в одной семье — в два-три человека. При этом предположим, что процент семей, которые пользуются услугами настройщиков пианино, составляет от 1/50 до 1/10, пианино необходимо настраивать как минимум один раз в год, а настройщики пианино работают примерно 200 дней в году, причём в день настраивают примерно 5 инструментов.

Таким образом, искомое число приближенно равно: (3 000 000 / 2-3) x (1/50-1/10) x 1 / (5 x 200) = 20-150.

Интересно, что во времена Энрико Ферми реальное значение составляло порядка 50 человек.

Зачем это нужно?

Многие люди могут подумать: «А какая польза от решения таких задач, помимо разминки мозгов?».

Как оказалось, многие крупные компании и университеты при собеседовании используют вопросы Ферми, чтобы определить, насколько хорошо человек умеет рассуждать, имея ограниченный набор фактов. В своей книге «Достаточно ли вы умны, чтобы работать в Google?» Уильям Паундстоун даже посвящает целую главу вопросам Ферми — так широко они применяются при приёме на работу в ведущие компании.

Помимо этого, в жизни часто приходится уметь давать оценку различным явлениям, и если вы способны дать обоснованный ответ на вопросы вида «Сколько коров в Канаде?», то и вопросы, более приближенные к реальности, не вызовут у вас затруднений.

Заключительные напутствия

В качестве тренировки советую прочесть соответствующую главу из уже упомянутой книги Паундстоуна «Достаточно ли вы умны, чтобы работать в Google?».

А ещё можете попрактиковаться прямо сейчас. Мы приготовили решения следующих вопросов Ферми:

1. Оцените количество автозаправок в России.
2. Сколько потребуется рулонов туалетной бумаги, чтобы покрыть ею всю Москву и сколько на это необходимо денежных средств?
3. Сколько людей ежегодно оканчивают университет?
4. Сколько насечек на 5-тирублевой монете?
5. Сколько каждый год выпускается книг?

Всё, что от вас нужно — это опубликовать свои рассуждения в комментариях, после чего мы обсудим ваши методы решения и предложим свои собственные. Удачи в решении!

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.

Как определить неизвестное: метод Ферми для быстрой оценки чего угодно: matveychev_oleg — LiveJournal

1. Как определить неизвестное

У физика Энрико Ферми (1901-1954), получившего в 1938 г. Нобелевскую премию, был настоящий талант к интуитивным измерениям, иногда казавшимся даже случайными. Как-то он продемонстрировал его при испытании атомной бомбы на полигоне Тринити 16 июля 1945 г., где вместе с другими учеными-атомщиками наблюдал за взрывной волной из базового лагеря.

Пока другие окончательно настраивали приборы для измерения мощности взрыва, Ферми разорвал на мелкие кусочки страничку из своего блокнота. Когда после взрыва подул сильный ветер, он подбросил эти кусочки в воздух и заметил, куда они упали (обрывки, улетевшие дальше всех, должны были показать пик давления волны). Ферми пришел к выводу, что мощность взрывной волны превысила 10 килотонн.

Эта информация оказалась очень важной, так как другим наблюдателям нижний предел данного параметра был неизвестен. После длительного анализа показаний приборов мощность взрывной волны была в конце концов оценена в 18,6 килотонн.

Ферми сумел определить требуемый показатель, проведя одно простое наблюдение — за рассеиванием обрывков бумаги по ветру.

Ферми славился тем, что учил студентов навыкам приблизительных расчетов самых фантастических величин, о которых те не могли иметь никакого представления. Самым известным примером такого «вопроса Ферми» является определение числа настройщиков пианино в Чикаго.

Студенты (будущие ученые и инженеры) начали с того, что у них нет для этого расчета никаких данных. Конечно, можно было просто пересчитать всех настройщиков, прочитав объявления, справившись в каком-нибудь агентстве, выдающем лицензии на такие услуги, и т. д. Но Ферми пытался научить своих студентов решать задачи и тогда, когда проверить результат будет не так просто. Ему хотелось, чтобы они поняли, что все-таки знают что-то об искомой величине.

Для начала Ферми попросил определить другие имеющие отношение к пианино и их настройщикам показатели — тоже неизвестные, но более легкие для оценки. Это были численность населения Чикаго (составлявшая в 1930-1950-х годах чуть более 3 млн. человек), среднее число человек в одной семье (два или три), процент семей, регулярно пользующихся услугами настройщиков пианино (максимально — каждая десятая, минимально — каждая тридцатая семья), требуемая частота настройки (в среднем, вероятно, не менее раза в год), число пианино, настраиваемых настройщиком за день (четыре или пять инструментов с учетом затрат времени на дорогу), а также число рабочих дней настройщика в году (скажем, 250).

Эти данные позволили рассчитать число настройщиков по следующей формуле:

= (Численность населения / Число членов одной семьи) х

х Процент семей, пользующихся услугами настройщиков х

х Число настроек в году /

/ (Число пианино, настраиваемых одним настройщиком за день х Число рабочих дней в году).

В зависимости от цифр, подставляемых в это уравнение, вы получите ответ в интервале 20-200; правильный ответ составлял примерно 50 человек. Когда эту цифру сравнивали с реальной (которую Ферми мог узнать из телефонного справочника), она всегда была ближе к реальной, чем думали студенты.

Полученный интервал значений выглядит слишком широким, но разве это не огромный шаг вперед по сравнению с позицией «неужели это вообще можно определить?», которую студенты занимали поначалу?

Данный подход позволял производившим расчеты людям понять, откуда берется неопределенность. Какие переменные характеризовались наибольшей неопределенностью — процент семей, регулярно пользующихся услугами настройщиков пианино, частота настроек, число инструментов, которые можно настроить за день, или что-то еще? Самый крупный источник неопределенности указывал на то, какие измерения позволят максимально снизить ее.

Поиск ответа на «вопрос Ферми» не предполагает проведения новых наблюдений и поэтому не может безоговорочно считаться измерением. Скорее, это оценка того, что вам уже известно о проблеме, способом, позволяющим несколько приблизиться к цели.

Вот еще один урок для бизнесмена — не считайте неопределенность неустранимой и не поддающейся анализу. Вместо того чтобы впадать в уныние по поводу своего незнания, спросите себя: а что же вы все-таки знаете о проблеме? Оценка имеющейся количественной информации о предмете — очень важный этап измерения явлений, которые выглядят неизмеряемыми.

2. «Вопросы Ферми» для нового предприятия

Чак Макей из компании Wizard of Ads всячески поощряет использовать «вопросы Ферми» для оценки размера своего рынка в том или ином районе. Недавно один страховой агент попросил Чака дать совет, стоит ли его компании открывать офис в Уичита-Фоллз (штат Техас), где до сих пор у нее не было представительства.

Будет ли на данном рынке спрос на услуги еще одного страховщика? Чтобы проверить реализуемость плана, Макей воспользовался методикой «вопросов Ферми» и начал с проблемы численности населения.

Согласно общедоступным статистическим данным, жители Уичита-Фоллз владели 62 172 автомашинами, а средняя годовая автомобильная страховая премия в штате Техас составляла 837,40 дол. Макей предположил, что почти все машины застрахованы, поскольку это обязательное требование.

Поэтому общая выручка от страхования составляла ежегодно 52 062 833 дол. Агент узнал, что средняя комиссионная ставка составляет 12%, так что все годовое комиссионное вознаграждение составляло 6 247 540 долл. В городе действовали 38 страховых агентств. Если разделить все комиссионное вознаграждение на 38 агентств, то окажется, что годовые комиссионные одного из них составляют в среднем 164 409 дол.

Рынок, по всей видимости, был уже достаточно насыщен, поскольку численность населения Уичита-Фоллз сократилась со 104 197 человек в 2000 г. до 99 846 человек в 2005 г. Кроме того, на данном рынке уже работало несколько крупных фирм, поэтому доходы нового агентства были бы еще меньше — и все это без учета накладных расходов.

Вывод Макея: скорее всего, новое агентство в этом городе вряд ли будет прибыльным, поэтому от плана следует отказаться.

3. Чему нас учит пример Ферми

Руководители часто говорят: «Ни о чем подобном мы не могли бы даже догадываться». Они заранее пасуют перед неопределенностью. Вместо того чтобы попытаться провести измерения, они бездействуют, обескураженные кажущейся невозможностью устранить ее. Ферми в подобном случае мог бы сказать: «Да, вы многого не знаете, но что-то же вы все-таки знаете?»

Иные менеджеры возражают: «Чтобы определить этот показатель, нужно потратить миллионы». В итоге они предпочитают не проводить и менее масштабные (с малыми затратами) исследования, потому что их погрешность обычно выше, чем у дорогих комплексных научных работ.

Между тем, даже небольшое снижение неопределенности может принести миллионы в зависимости от важности решения, принятию которого оно способствует, и от частоты принятия подобных решений.

«Вопросы Ферми» показали даже далеким от науки людям, как можно проводить измерения, кажущиеся на первый взгляд настолько сложными, что не стоит и пытаться ими заниматься. Обычно вещи, считающиеся в бизнесе неизмеряемыми, можно количественно определить с помощью простейших приемов наблюдения, как только люди поймут, что неизмеримость — всего лишь иллюзия.

С этой точки зрения ценность подхода Ферми состоит, прежде всего, в том, что оценка современного уровня наших знаний о предмете — необходимое условие последующих измерений.опубликовано econet.ru

Автор: Дaглaс У. Хaббapд (Douglas W. Hubbard)

метод Ферми для быстрой оценки чего угодно

Развить в себе умение измерять неизвестное — совсем не простое дело. К счастью, история знала немало личностей, продемонстрировавших такое поразительное умение. Один из них — лауреат Нобелевской премии по физике, который учил своих студентов измерять на примере оценки числа настройщиков пианино в Чикаго.

Метод Ферми

1. Как определить неизвестное

У физика Энрико Ферми (1901-1954), получившего в 1938 г. Нобелевскую премию, был настоящий талант к интуитивным измерениям, иногда казавшимся даже случайными. Как-то он продемонстрировал его при испытании атомной бомбы на полигоне Тринити 16 июля 1945 г., где вместе с другими учеными-атомщиками наблюдал за взрывной волной из базового лагеря.

Пока другие окончательно настраивали приборы для измерения мощности взрыва, Ферми разорвал на мелкие кусочки страничку из своего блокнота. Когда после взрыва подул сильный ветер, он подбросил эти кусочки в воздух и заметил, куда они упали (обрывки, улетевшие дальше всех, должны были показать пик давления волны). Ферми пришел к выводу, что мощность взрывной волны превысила 10 килотонн.

Эта информация оказалась очень важной, так как другим наблюдателям нижний предел данного параметра был неизвестен. После длительного анализа показаний приборов мощность взрывной волны была в конце концов оценена в 18,6 килотонн.

Ферми сумел определить требуемый показатель, проведя одно простое наблюдение — за рассеиванием обрывков бумаги по ветру.

Ферми славился тем, что учил студентов навыкам приблизительных расчетов самых фантастических величин, о которых те не могли иметь никакого представления. Самым известным примером такого «вопроса Ферми» является определение числа настройщиков пианино в Чикаго.

Студенты (будущие ученые и инженеры) начали с того, что у них нет для этого расчета никаких данных. Конечно, можно было просто пересчитать всех настройщиков, прочитав объявления, справившись в каком-нибудь агентстве, выдающем лицензии на такие услуги, и т. д. Но Ферми пытался научить своих студентов решать задачи и тогда, когда проверить результат будет не так просто. Ему хотелось, чтобы они поняли, что все-таки знают что-то об искомой величине.

Для начала Ферми попросил определить другие имеющие отношение к пианино и их настройщикам показатели — тоже неизвестные, но более легкие для оценки. Это были численность населения Чикаго (составлявшая в 1930-1950-х годах чуть более 3 млн. человек), среднее число человек в одной семье (два или три), процент семей, регулярно пользующихся услугами настройщиков пианино (максимально — каждая десятая, минимально — каждая тридцатая семья), требуемая частота настройки (в среднем, вероятно, не менее раза в год), число пианино, настраиваемых настройщиком за день (четыре или пять инструментов с учетом затрат времени на дорогу), а также число рабочих дней настройщика в году (скажем, 250).

Эти данные позволили рассчитать число настройщиков по следующей формуле:

Число настройщиков пианино в Чикаго =

= (Численность населения / Число членов одной семьи) х

х Процент семей, пользующихся услугами настройщиков х

х Число настроек в году /

/ (Число пианино, настраиваемых одним настройщиком за день х Число рабочих дней в году).

В зависимости от цифр, подставляемых в это уравнение, вы получите ответ в интервале 20-200; правильный ответ составлял примерно 50 человек. Когда эту цифру сравнивали с реальной (которую Ферми мог узнать из телефонного справочника), она всегда была ближе к реальной, чем думали студенты.

Полученный интервал значений выглядит слишком широким, но разве это не огромный шаг вперед по сравнению с позицией «неужели это вообще можно определить?», которую студенты занимали поначалу?

Данный подход позволял производившим расчеты людям понять, откуда берется неопределенность. Какие переменные характеризовались наибольшей неопределенностью — процент семей, регулярно пользующихся услугами настройщиков пианино, частота настроек, число инструментов, которые можно настроить за день, или что-то еще? Самый крупный источник неопределенности указывал на то, какие измерения позволят максимально снизить ее.

Поиск ответа на «вопрос Ферми» не предполагает проведения новых наблюдений и поэтому не может безоговорочно считаться измерением. Скорее, это оценка того, что вам уже известно о проблеме, способом, позволяющим несколько приблизиться к цели.

Вот еще один урок для бизнесмена — не считайте неопределенность неустранимой и не поддающейся анализу. Вместо того чтобы впадать в уныние по поводу своего незнания, спросите себя: а что же вы все-таки знаете о проблеме? Оценка имеющейся количественной информации о предмете — очень важный этап измерения явлений, которые выглядят неизмеряемыми.

2. «Вопросы Ферми» для нового предприятия

Чак Макей из компании Wizard of Ads всячески поощряет использовать «вопросы Ферми» для оценки размера своего рынка в том или ином районе. Недавно один страховой агент попросил Чака дать совет, стоит ли его компании открывать офис в Уичита-Фоллз (штат Техас), где до сих пор у нее не было представительства.

Будет ли на данном рынке спрос на услуги еще одного страховщика? Чтобы проверить реализуемость плана, Макей воспользовался методикой «вопросов Ферми» и начал с проблемы численности населения.

Согласно общедоступным статистическим данным, жители Уичита-Фоллз владели 62 172 автомашинами, а средняя годовая автомобильная страховая премия в штате Техас составляла 837,40 дол. Макей предположил, что почти все машины застрахованы, поскольку это обязательное требование.

Поэтому общая выручка от страхования составляла ежегодно 52 062 833 дол. Агент узнал, что средняя комиссионная ставка составляет 12%, так что все годовое комиссионное вознаграждение составляло 6 247 540 долл. В городе действовали 38 страховых агентств. Если разделить все комиссионное вознаграждение на 38 агентств, то окажется, что годовые комиссионные одного из них составляют в среднем 164 409 дол.

Рынок, по всей видимости, был уже достаточно насыщен, поскольку численность населения Уичита-Фоллз сократилась со 104 197 человек в 2000 г. до 99 846 человек в 2005 г. Кроме того, на данном рынке уже работало несколько крупных фирм, поэтому доходы нового агентства были бы еще меньше — и все это без учета накладных расходов.

Вывод Макея: скорее всего, новое агентство в этом городе вряд ли будет прибыльным, поэтому от плана следует отказаться.

3. Чему нас учит пример Ферми

Руководители часто говорят: «Ни о чем подобном мы не могли бы даже догадываться». Они заранее пасуют перед неопределенностью. Вместо того чтобы попытаться провести измерения, они бездействуют, обескураженные кажущейся невозможностью устранить ее. Ферми в подобном случае мог бы сказать: «Да, вы многого не знаете, но что-то же вы все-таки знаете?»

Иные менеджеры возражают: «Чтобы определить этот показатель, нужно потратить миллионы». В итоге они предпочитают не проводить и менее масштабные (с малыми затратами) исследования, потому что их погрешность обычно выше, чем у дорогих комплексных научных работ.

Между тем, даже небольшое снижение неопределенности может принести миллионы в зависимости от важности решения, принятию которого оно способствует, и от частоты принятия подобных решений.

«Вопросы Ферми» показали даже далеким от науки людям, как можно проводить измерения, кажущиеся на первый взгляд настолько сложными, что не стоит и пытаться ими заниматься. Обычно вещи, считающиеся в бизнесе неизмеряемыми, можно количественно определить с помощью простейших приемов наблюдения, как только люди поймут, что неизмеримость — всего лишь иллюзия.

С этой точки зрения ценность подхода Ферми состоит, прежде всего, в том, что оценка современного уровня наших знаний о предмете — необходимое условие последующих измерений.опубликовано econet.ru

Автор: Дaглaс У. Хaббapд (Douglas W. Hubbard)

P.S. И помните, всего лишь изменяя свое сознание — мы вместе изменяем мир! © econet

Дисбаланс, инженеры и Ферми — Манжеты гейм-дизайнера

Мы работаем в индустрии, во многом построенной на понятии «игрового баланса». Забавно, что единой чёткой формулы хорошего баланса до сих пор не существует.

Хороший баланс — это когда «игра работает как надо». Звучит почти как «фан — это когда играть весело». Что более эфемерно и трудно воспроизводимо — фан или баланс? Обладает ли хорошо сбалансированная игра по умолчанию фаном? Обязательно ли фановая игра должна быть хорошо сбалансирована?

Вернёмся на минутку к ещё более забавному и расплывчатому определению игровой индустрии. Что такое игра? Не хочу разжигать философские споры, однако, вспомню расхожую фразу Сида Мейера — «A game is a collection of interesting choices» = «Игра — это серия интересных решений».

Дополню цитату старины Сида: игра — это серия решений, хорошая игра — это серия интересных решений. Хороший баланс должен эту серию обеспечивать. Плохой баланс подразумевает недостаток или отсутствие выбора между решениями в принципе.

Вернёмся к нашему старому примеру с комплектами предметов в ролевой игре. Представим, что вместо одного комплекта на уровень у нас есть три: А1, А2 и А3. Все они одной цены, но немного разных параметров. Если эффективность одного из комплектов будет достаточно превышать эффективность других, то это сделает их практически бесполезными в большинстве случаев.

Пример из Magic: The Gathering. В игре есть классическое синее заклинание Counterspell, которое стоит две синие маны и отменяет любое заклинание противника. Counterspell входит во все базовые редакции MTG и является «фирменной» картой синих. Позднее была введена синяя карта Mana Leak, которая также стоила две маны, только одна из них должна была быть синей, а вторая могла быть любого цвета. Но при этом Mana Leak позволяла отменять свой эффект, если противник тратил ману, что существенно ограничивало её применение. Да, в этом прослеживалась стратегия мана контроля, но карта просто не была достаточно сильна, чтобы занять слот Counterspell. Стоит ли говорить, что Mana Leak была значительно менее популярна, особенно в моносиних колодах, где бесцветная мана не давала никакого преимущества.

Такой дисбаланс плох не только фактическим лишением игрока возможности выбора, но и отвлечением его внимания на «мусорные» сущности. А постоянно отвлекающийся от геймплея игрок скоро прекратит играть. Нет интересных решений — нет интересной игры.

Известный всем пример дисбаланса — поздняя стадия игры в Монополию, когда в 100% случаев самым эффективным решением является попадание в тюрьму и пассивное наблюдение за тем, как конкуренты банкротятся на умопомрачительно дорогих клетках игрового поля. Подумайте только! Самая эффективная стратегия в игре — это не играть! Никаких решений в эндшпиле Монополии нет, это просто затянутое завершение игры.

К какому бы из типов ни принадлежал дисбаланс, он всегда связан с ограничением свободы выбора игрока.

Высокая цена при низкой эффективности или высокая эффективность при низкой цене

Самый распространённый тип дисбаланса. Игровые решения обычно связаны с игровой стоимостью в том или ином виде. Это может быть потеря возможных решений, игровых денег или любой другой собственности. Если один из вариантов либо слишком дорогой для своего эффекта, либо слишком дешёвый — это дисбаланс, потому что одно из решений заведомо проигрышное.

Решение: Настройка простыми математическими действиями с ценой или базовыми параметрами эффективности.

Хинт: при прототипировании баланса всегда умножайте или делите все значения на два. Это наглядно покажет вам эффективность зависимостей между элементами. Увеличьте параметр на 100% или уменьшите на 50%. Вы сразу сможете понять, необходима ли более точная настройка или элемент в корне работает неправильно.

Одинаковая цена и эффективность

Что любопытно, гейм-дизайнеры часто ударяются в другую крайность и создают множество очень слабо отличающихся друг от друга элементов. Решение не будет интересным, если все его варианты эквивалентны. Вернёмся к MTG и построению колоды. Каждая карта, которую игрок кладёт в колоду — это решение. Это преследование определённой стратегии. Если все карты одинаковы и работают по одной схеме — нет стратегии, нет выбора. Даже синергия отдельных элементов не спасёт ситуацию — она тоже участвует в уравнении эффективности. Это работает только в случаях, когда игра не основана на стратегии (например, файтинги или шашки).

Решение: Дайте игроку возможность преследовать разные стратегии и стили игры, дайте ему самовыражаться хотя бы минимально. Некоторые стратегии могут быть сильнее других — это нормально, но и они, в свою очередь, должны быть нивелированы третьими стратегиями.

Дисбаланс времени игрока

Большинство сравнений между элементами при балансировке связано со стоимостями различных решений — чем игрок должен пожертвовать, чтобы пойти по выбранному пути. Очень просто забыть о том факте, что на принятие решений игрок тратит время. В стратегии в реальном времени игрок не обладает бесконечным количеством времени, что делает его ценным ограниченным ресурсом. В походовой стратегии игровое время безгранично. Но время игрока — нет. Вспомните, на чём была основана основная стратегия зергов в Starcraft?

Решение: Учитывайте время, необходимое игроку на принятие решений и просчитывание последствий.

Дисбаланс умений игроков

Со временем умение игрока растёт, а следовательно, меняется и сравнительная эффективность его решений. В любой MOBA-игре есть простые для освоения персонажи, эффективно играть на которых несложно. Также есть сложные персонажи, требующие для эффективности определённых навыков. Сравнительная эффективность таких персонажей для новичка и ветерана будет значительно различаться.

Решение: Основанный на мастерстве игрока постоянно эволюционирующий геймплей считается хорошим решением, но важно не забывать о новичках и о правильной кривой сложности.

Принудительное преимущество

Когда игрок сражается против другого игрока, некоторые последовательности действий могут привести к гарантированному преимуществу одного игрока над другим. Это не только соответствует общей черте всех типов дисбаланса — одно решение, очевидно, выигрышное — но и является нечестной ситуацией. Например, при игре в крестики-нолики невозможно выиграть за нолики, если игрок за крестики знает определённую последовательность ходов.

Решение: Универсального рецепта здесь нет — проводите плейтесты и пользуйтесь аналитикой.

Как победить дисбаланс?

Успех победы над дисбалансом, как и любой инженерной задачи, лежит в качественной подготовке! 🙂 Балансируемость игровой модели — её качественная сторона. Чем проще привести модель в состояние баланса, тем лучше эта модель спроектирована. Если модель обладает нулевой балансируемостью, то никакие тюнинги и настройки её не спасут.

Игра — это система. С точки зрения инженера, три основных столпа любой хорошей системы это:

Модульность

Каждая игровая механика и каждый игровой элемент должны служить определённой цели. В идеале — единственной цели. Таким образом, настраивая один элемент системы, вы настраиваете всего один аспект геймплея.

Хороший пример — бета-тестирование Starcraft. У Blizzard была достаточно простая система повреждений. Каждый юнит наносил один из трёх типов повреждений: взрывчатый, обычный или ударный. Каждый из типов обладал различным мультипликатором против различных размеров юнитов. Взрывчатый был хорош против больших целей, ударный — против мелких, а обычный — против всего.

Проблема была в Муталиске. Он не втискивался в общие стандарты, с точки зрения требуемой функциональности. Муталиска нельзя было причислить к «средним» юнитам — это делало его слишком устойчивым к взрывчатым повреждениям. Нельзя было и к большим — тогда он становился слишком лёгкой добычей для тех же «взрывчатых» юнитов.

Blizzard не могли просто изменить мультипликаторы системы повреждений — это нарушило бы множество других связей уже сбалансированных игровых элементов. По этой же причине они не могли поменять и значения повреждений «взрывчатых» юнитов.

Ситуацию не упрощало и то, что Муталиск выполнял две роли — антивоздушную и антипехотную. Но при этом его повреждения имели одно базовое значение, в отличие от тех же призраков, у которых были отдельные повреждения для воздушных целей.

Blizzard не могли сбалансировать Муталиска ещё пять месяцев после коммерческого релиза игры. Исправление проблемы не было невозможным, но было сильно затруднено отсутствием модульности в игровой системе.

Муталиск имел достаточно уникальную роль в игре. Blizzard могли изолировать его характеристики от других единиц, им было бы гораздо легче сбалансировать его. Самое простое решение — добавить уникальный тип единицы «Муталиск» со своей устойчивостью к различным типам повреждений. Разделить наземные и воздушные атаки тоже хорошая мысль.

Справедливости ради стоит сказать, что в Starcraft модульность присутствует. Например, спеллкастеры. Каждый из юнитов этого типа служит сравнительно уникальной цели. Многие заклинания (Broodling, EMP Blast, etc) имели крайне специализированные роли. Думаю, с их балансом не возникло никаких проблем.

Высокая модульность системы — это не только превентивная мера, это активный шаг к решению многих проблем с балансом. Система с высокой модульностью будет иметь все необходимые инструменты для настройки элементов любого назначения.

Консистентность

Очень простой и очень важный принцип. Все игровые механики и элементы должны работать на кор-геймплей, а не отвлекать игрока от него. Иначе механика в лучшем случае будет отвлекать игрока, в худшем — так или иначе нанесёт вред самому кор-геймплею. Не вводите механики и элементы, которые не будут служить цели вашей игры, не будут когерентны игровому опыту.

Простота

Используйте принцип бритвы Оккама — не стоит множить сущностей без необходимости. Проще говоря: будьте проще сами и делайте простыми свои системы. Чрезмерно сложные игровые системы ожидаемо очень сложны для понимания и восприятия, а следовательно, их тяжелее балансировать.

Переусложненные системы имеют место в двух случаях. Первый  когда первоначальное проектирование было настолько слабо, что нагромождение поправок в дизайне и концепции складывается в монстра, который работает только в теории. Второй — когда система развивается и поддерживается очень продолжительное время большим количеством людей — это порождает «наследственный дизайн» (программисты поймут:). Отсутствие простоты также ведёт к отсутствию консистентности и, часто, модульности. Не забывайте, что игрокам тоже будет сложно разобраться в вашей сложной системе.

С чего начать?

Первым делом необходимо вывести базовую формулу игровой мощности — отношение эффективности к затраченным ресурсам. Пусть это будет сферическая мощность в вакууме, главное, чтобы она подчинялась законам вашей игровой модели. Игровыми ресурсами может быть что угодно в зависимости от жанра: золото, мана, DPS, время и так далее.

Базовая формула мощности создаст фундамент, на котором вы уверенно возведёте свой баланс. Отталкивайтесь от времени, которое по плану должен тратить ваш игрок за одну сессию. Если вы хотите игровую сессию в полчаса, убедитесь, что игрок за это время получит все необходимые ресурсы и инструменты для ощутимого продвижения в игре. Время сессии также является точкой, от которой можно отталкиваться при проектировании.

Если у вас нет каких-то определённых целей и ограничений — делайте систему простой. Приравняйте 1 единицу маны к 1 единице повреждений — это облегчит вам жизнь. После первого фидбэка от взаимодействий в системе вы всегда сможете перенастроить значения.

Разумеется, просто свести всё к базовой формуле не получится — всё-таки частенько игры представляют собой сравнительно сложные системы. И тут нам на помощь снова приходит инженерная мысль.

Метод Ферми

Энрико Ферми был гениальным физиком, известным своей способностью получать точнейшие прогнозы на основании минимума информации. Он славился тем, что учил студентов навыкам приблизительных расчётов самых фантастических величин, о которых те не могли иметь никакого представления. Самым известным примером такого «вопроса Ферми» является определение числа настройщиков пианино в Чикаго.

Ферми хотел, чтобы студенты, не имея никаких стартовых данных, смогли прикинуть необходимое значение. Для этого он просил их оценить связанные с искомой сущностью показатели — тоже неизвестные, но более легко поддающиеся оценке. Таким образом была выведена следующая формула:

Число настройщиков пианино в Чикаго =

= (Численность населения / Число членов одной семьи) х

х Процент семей, пользующихся услугами настройщиков х

х Число настроек в году /

/ (Число пианино, настраиваемых одним настройщиком за день х Число рабочих дней в году).

В зависимости от подставляемых в уравнение цифр получается ответ в интервале 20–200. Верный ответ — примерно 50 человек. Когда эту цифру сравнивали с реальной (которую Ферми мог узнать из телефонного справочника), она всегда была ближе к реальной, чем думали студенты.

Полученный интервал значений выглядит слишком широким, но разве это не огромный шаг вперёд по сравнению с позицией «неужели это вообще можно определить?», которую студенты занимали поначалу?

Метод Ферми помогает понять, откуда берётся неопределённость. Помогает разложить её на отдельные переменные неопределённости. Самый крупный источник неопределённости указывал на то, какие измерения позволят максимально снизить её.

Метод Ферми не предполагает проведения новых наблюдений и поэтому не может безоговорочно считаться измерением. Скорее, это оценка уже известной информации о проблеме способом, позволяющим несколько приблизиться к цели.

Использование метода Ферми, как и умножение/деление параметров, позволит вам быстро прикинуть масштабы и механизмы вашей игровой модели и определить её слабые и сильные места.

Надеюсь, что кому-нибудь было интересно или полезно. В следующий раз расскажу, как дисбаланс может быть весёлым 🙂

Увидимся!

Источники:

Метод Ферми для быстрой оценки чего угодно

Очень полезный навык.

Развить в себе умение измерять неизвестное — совсем не простое дело. К счастью, история знала немало личностей, продемонстрировавших такое поразительное умение. Один из них — лауреат Нобелевской премии по физике, который учил своих студентов измерять на примере оценки числа настройщиков пианино в Чикаго.

1. Как определить неизвестное

У физика Энрико Ферми (1901—1954), получившего в 1938 г. Нобелевскую премию, был настоящий талант к интуитивным измерениям, иногда казавшимся даже случайными. Как-то он продемонстрировал его при испытании атомной бомбы на полигоне Тринити 16 июля 1945 г., где вместе с другими учеными-атомщиками наблюдал за взрывной волной из базового лагеря.

Пока другие окончательно настраивали приборы для измерения мощности взрыва, Ферми разорвал на мелкие кусочки страничку из своего блокнота. Когда после взрыва подул сильный ветер, он подбросил эти кусочки в воздух и заметил, куда они упали (обрывки, улетевшие дальше всех, должны были показать пик давления волны). Ферми пришел к выводу, что мощность взрывной волны превысила 10 килотонн.

Эта информация оказалась очень важной, так как другим наблюдателям нижний предел данного параметра был неизвестен. После длительного анализа показаний приборов мощность взрывной волны была в конце концов оценена в 18,6 килотонн.

Ферми сумел определить требуемый показатель, проведя одно простое наблюдение — за рассеиванием обрывков бумаги по ветру.

Ферми славился тем, что учил студентов навыкам приблизительных расчетов самых фантастических величин, о которых те не могли иметь никакого представления. Самым известным примером такого «вопроса Ферми» является определение числа настройщиков пианино в Чикаго.

Студенты (будущие ученые и инженеры) начали с того, что у них нет для этого расчета никаких данных. Конечно, можно было просто пересчитать всех настройщиков, прочитав объявления, справившись в каком-нибудь агентстве, выдающем лицензии на такие услуги, и т. д. Но Ферми пытался научить своих студентов решать задачи и тогда, когда проверить результат будет не так просто. Ему хотелось, чтобы они поняли, что все-таки знают что-то об искомой величине.

Для начала Ферми попросил определить другие имеющие отношение к пианино и их настройщикам показатели — тоже неизвестные, но более легкие для оценки. Это были численность населения Чикаго (составлявшая в 1930—1950-х годах чуть более 3 млн. человек), среднее число человек в одной семье (два или три), процент семей, регулярно пользующихся услугами настройщиков пианино (максимально — каждая десятая, минимально — каждая тридцатая семья), требуемая частота настройки (в среднем, вероятно, не менее раза в год), число пианино, настраиваемых настройщиком за день (четыре или пять инструментов с учетом затрат времени на дорогу), а также число рабочих дней настройщика в году (скажем, 250).

Эти данные позволили рассчитать число настройщиков по следующей формуле:

Число настройщиков пианино в Чикаго =

= (Численность населения / Число членов одной семьи) х

х Процент семей, пользующихся услугами настройщиков х

х Число настроек в году /

/ (Число пианино, настраиваемых одним настройщиком за день х Число рабочих дней в году).

В зависимости от цифр, подставляемых в это уравнение, вы получите ответ в интервале 20-200; правильный ответ составлял примерно 50 человек. Когда эту цифру сравнивали с реальной (которую Ферми мог узнать из телефонного справочника), она всегда была ближе к реальной, чем думали студенты.

Полученный интервал значений выглядит слишком широким, но разве это не огромный шаг вперед по сравнению с позицией «неужели это вообще можно определить?», которую студенты занимали поначалу?

Данный подход позволял производившим расчеты людям понять, откуда берется неопределенность. Какие переменные характеризовались наибольшей неопределенностью — процент семей, регулярно пользующихся услугами настройщиков пианино, частота настроек, число инструментов, которые можно настроить за день, или что-то еще? Самый крупный источник неопределенности указывал на то, какие измерения позволят максимально снизить ее.

Поиск ответа на «вопрос Ферми» не предполагает проведения новых наблюдений и поэтому не может безоговорочно считаться измерением. Скорее, это оценка того, что вам уже известно о проблеме, способом, позволяющим несколько приблизиться к цели.

Вот еще один урок для бизнесмена — не считайте неопределенность неустранимой и не поддающейся анализу. Вместо того чтобы впадать в уныние по поводу своего незнания, спросите себя: а что же вы все-таки знаете о проблеме? Оценка имеющейся количественной информации о предмете — очень важный этап измерения явлений, которые выглядят неизмеряемыми.

2. «Вопросы Ферми» для нового предприятия

Чак Макей из компании Wizard of Ads всячески поощряет использовать «вопросы Ферми» для оценки размера своего рынка в том или ином районе. Недавно один страховой агент попросил Чака дать совет, стоит ли его компании открывать офис в Уичита-Фоллз (штат Техас), где до сих пор у нее не было представительства.

Будет ли на данном рынке спрос на услуги еще одного страховщика? Чтобы проверить реализуемость плана, Макей воспользовался методикой «вопросов Ферми» и начал с проблемы численности населения.

Согласно общедоступным статистическим данным, жители Уичита-Фоллз владели 62 172 автомашинами, а средняя годовая автомобильная страховая премия в штате Техас составляла 837,40 дол. Макей предположил, что почти все машины застрахованы, поскольку это обязательное требование.

Поэтому общая выручка от страхования составляла ежегодно 52 062 833 дол. Агент узнал, что средняя комиссионная ставка составляет 12%, так что все годовое комиссионное вознаграждение составляло 6 247 540 долл. В городе действовали 38 страховых агентств. Если разделить все комиссионное вознаграждение на 38 агентств, то окажется, что годовые комиссионные одного из них составляют в среднем 164 409 дол.

Рынок, по всей видимости, был уже достаточно насыщен, поскольку численность населения Уичита-Фоллз сократилась со 104 197 человек в 2000 г. до 99 846 человек в 2005 г. Кроме того, на данном рынке уже работало несколько крупных фирм, поэтому доходы нового агентства были бы еще меньше — и все это без учета накладных расходов.

Вывод Макея: скорее всего, новое агентство в этом городе вряд ли будет прибыльным, поэтому от плана следует отказаться.

3. Чему нас учит пример Ферми

Руководители часто говорят: «Ни о чем подобном мы не могли бы даже догадываться». Они заранее пасуют перед неопределенностью. Вместо того чтобы попытаться провести измерения, они бездействуют, обескураженные кажущейся невозможностью устранить ее. Ферми в подобном случае мог бы сказать: «Да, вы многого не знаете, но что-то же вы все-таки знаете?»

Иные менеджеры возражают: «Чтобы определить этот показатель, нужно потратить миллионы». В итоге они предпочитают не проводить и менее масштабные (с малыми затратами) исследования, потому что их погрешность обычно выше, чем у дорогих комплексных научных работ.

Между тем, даже небольшое снижение неопределенности может принести миллионы в зависимости от важности решения, принятию которого оно способствует, и от частоты принятия подобных решений.

«Вопросы Ферми» показали даже далеким от науки людям, как можно проводить измерения, кажущиеся на первый взгляд настолько сложными, что не стоит и пытаться ими заниматься.Обычно вещи, считающиеся в бизнесе неизмеряемыми, можно количественно определить с помощью простейших приемов наблюдения, как только люди поймут, что неизмеримость — всего лишь иллюзия.

С этой точки зрения ценность подхода Ферми состоит, прежде всего, в том, что оценка современного уровня наших знаний о предмете — необходимое условие последующих измерений.

Решение нестандартных задач Ферми | Блог 4brain

Задачи Ферми являются весьма действенным способом тренировки реальной применимости знаний человека на практике, а также способности быстро находить способы решения любой жизненной задачи. Современное образование часто предлагает знания, имеющие общий или абстрактный характер. Студенты и школьники часто способны решать сложные типовые задачи, совершая множество операций, а когда речь заходит о том, чтобы решить элементарную, но нестандартную задачу, они впадают в ступор.

Так один из пробных тестов ЕГЭ в 2012 году показал, что учащиеся 11-го класса не смогли решить простейшую арифметическую задачу по математике на подсчет потраченной электроэнергии. Это произошло потому, что они не смогли найти алгоритм решения. Получается, что этих школьников, а скорее всего и многих других школьников в нашей стране, учат решать стандартные типовые задачи по уже «вызубренному» алгоритму. Задачи Ферми существуют как раз для того, чтобы этот алгоритм человек сумел найти самостоятельно, используя логику, общие знания разных дисциплин, а также креативное мышление.

Примеры задач Ферми

Для того, чтобы понять что такое задачи Ферми, просто посмотрите несколько примеров:

Задача 1. Найдите, сколько вам потребуется написать страниц текста, для того, чтобы читать его вслух в течение одного часа.

Задача 2. Сколько потребуется бензина, чтобы проехать от Калининграда до Владивостока на Ладе Калина.

Задача 3. Сколько коробок с пиццей может поместиться в Daewoo Matiz с водителем.

Чтобы решить эти и подобные нестандартные задачи по математике, физике, химии или информатике, вам потребуется не просто посчитать, но понять, что и как считать. Начать следует с поиска метода решения нестандартной задачи (алгоритма), а затем переходить к расчетам и оценкам. Кроме того, важно правильно использовать примерные расчеты и делать вероятностные оценки. В большинстве задач ответ может получиться примерным или находиться в диапазоне.

Применение задач Ферми. Так как часто ответ задач Ферми представляет сомнительный практический интерес, главный акцент делается именно на метод решения. Поэтому задачи Ферми нашли свое применение на различных собеседованиях в крупные компании, конкурсах, интеллектуальных играх, олимпиадах по физике или по информатике. Суть использования задач сводится к тому, чтобы увидеть способность человека к поиску нестандартных решений. Кроме того, задачи Ферми часто используются изощренными учителями и преподавателями, которые стремятся развивать интеллектуальные способности своих учеников.

Методы решения нестандартных задач Ферми

Для решения задач, нельзя назвать единственный алгоритм, однако некоторые рекомендации существуют:

1. Даже, если задача показалась вам сложной, а тематика далекой – старайтесь найти подход и вспомнить необходимую информацию.
2. Найдите нужный алгоритм решения, используя различные стороны ваших знаний, стараясь не прибегать к помощи сторонних источников.
3. Сделать все необходимые оценки и предварительные расчеты.
4. Продемонстрируйте ваше решение, назовите конкретный ответ, а также расскажите о возможных отклонениях.

Еще некоторые примеры нестандартных задач (или задач Ферми) смотрите в данной статье.

Метод факторизации Ферма — Википедия

Метод факторизации Ферма — алгоритм факторизации (разложения на множители) нечётного целого числа n{\displaystyle n}, предложенный Пьером Ферма (1601—1665) в 1643 году.

Метод основан на поиске таких целых чисел x{\displaystyle x} и y{\displaystyle y}, которые удовлетворяют соотношению x2−y2=n{\displaystyle x^{2}-y^{2}=n}, что ведёт к разложению n=(x−y)⋅(x+y){\displaystyle n=(x-y)\cdot (x+y)}.

История

В начале XVII века во Франции математические идеи начали активно распространяться между учёными посредством переписки. В 1638 году к кругу переписывающихся учёных присоединился Пьер Ферма. Переписка была удобным способом общения, так как Ферма жил в Тулузе, а многие его знакомые учёные жили в Париже. Одним из таких учёных был Марен Мерсенн, занимавшийся распространением писем, пересылкой и связью многих учёных между собой. 26 декабря 1638 года в письме Мерсенну Ферма упомянул, что нашёл метод, с помощью которого можно находить делители положительных чисел, но какие-либо подробности и описание метода он опустил. На тот момент Мерсенн также вёл переписку с французским математиком Бернаром Френикль де Бесси, занимавшимся, как и Ферма, теорией чисел, в частности, делителями натуральных чисел и совершенными числами. В начале 1640 года, узнав о том, что Ферма получил метод нахождения делителей, Френикль пишет Мерсенну, и тот пересылает письмо Ферма. Мерсенн долгое время был связующим звеном между двумя математиками в их переписке. Именно в письмах Френиклю Ферма смог доказать корректность метода факторизации, а также впервые сформулировать и обосновать основные положения теоремы, которая позже была названа Малой теоремой Ферма ^[1][2].

Видео по теме

Обоснование

Метод Ферма основан на теореме о представлении числа в виде разности двух квадратов:

Доказательство

Если задана факторизация n=a⋅b{\displaystyle n=a\cdot b}, то имеет место соотношение: n=a⋅b=(a+b2)2−(a−b2)2{\displaystyle n=a\cdot b=({\tfrac {a+b}{2}})^{2}-({\tfrac {a-b}{2}})^{2}}. Таким образом получается представление в виде разности двух квадратов.

Обратно, если дано, что n=x2−y2{\displaystyle n=x^{2}-y^{2}}, то правую часть можно разложить на множители: (x−y)(x+y){\displaystyle (x-y)(x+y)}^[3].

Описание алгоритма

Для разложения на множители нечётного числа n{\displaystyle n} ищется пара чисел (x,y){\displaystyle (x,y)} таких, что x2−y2=n{\displaystyle x^{2}-y^{2}=n}, или (x−y)⋅(x+y)=n{\displaystyle (x-y)\cdot (x+y)=n}. При этом числа (x+y){\displaystyle (x+y)} и (x−y){\displaystyle (x-y)} являются множителями n{\displaystyle n}, возможно, тривиальными (то есть одно из них равно 1, а другое — n{\displaystyle n}.)

В нетривиальном случае, равенство x2−y2=n{\displaystyle x^{2}-y^{2}=n} равносильно x2−n=y2{\displaystyle x^{2}-n=y^{2}}, то есть тому, что x2−n{\displaystyle x^{2}-n} является квадратом.

Поиск квадрата такого вида начинается с x=⌈n⌉{\displaystyle x=\left\lceil {\sqrt {n}}\right\rceil } — наименьшего числа, при котором разность x2−n{\displaystyle x^{2}-n} неотрицательна.

Для каждого значения k∈N,{\displaystyle k\in \mathbb {N} ,} начиная с k=1{\displaystyle k=1}, вычисляют (⌈n⌉+k)2−n{\displaystyle (\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n} и проверяют, не является ли это число точным квадратом. Если не является, то k{\displaystyle k} увеличивают на единицу и переходят на следующую итерацию.

Если (⌈n⌉+k)2−n{\displaystyle (\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n} является точным квадратом, то есть x2−n=(⌈n⌉+k)2−n=y2,{\displaystyle x^{2}-n=(\left\lceil {\sqrt {n}}\right\rceil +k)^{2}-n=y^{2},} то получено разложение:

n=x2−y2=(x+y)(x−y)=a⋅b,{\displaystyle n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b,} в котором x=(⌈n⌉+k){\displaystyle x=(\left\lceil {\sqrt {n}}\right\rceil +k)}

Если оно является тривиальным и единственным, то n{\displaystyle n} — простое.

На практике значение выражения на (k+1){\displaystyle (k+1)}-ом шаге вычисляется с учётом значения на k{\displaystyle k}-ом шаге:

(s+1)2−n=s2+2s+1−n,{\displaystyle \left(s+1\right)^{2}-n=s^{2}+2s+1-n,} где s=⌈n⌉+k.{\displaystyle s=\left\lceil {\sqrt {n}}\right\rceil +k.}

Примеры

Пример с малым числом итераций

Возьмём число n=10873{\displaystyle n=10873}. Вычислим s=⌈n⌉=105.{\displaystyle s=\left\lceil {\sqrt {n}}\right\rceil =105.} Для k=1,2,…{\displaystyle k=1,2,…} будем вычислять значения функции s+k{\displaystyle s+k}. Для дальнейшей простоты построим таблицу, которая будет содержать значения y=(s+k)2−n{\displaystyle y=(s+k)^{2}-n} и y{\displaystyle {\sqrt {y}}} на каждом шаге итерации. Получим:

Как видно из таблицы, уже на втором шаге итерации было получено целое значение y{\displaystyle {\sqrt {y}}}.

Таким образом имеет место следующее выражение: (105+2)2−n=242{\displaystyle (105+2)^{2}-n=24^{2}}. Отсюда следует, что n=1072−242=131⋅83=10873.{\displaystyle n=107^{2}-24^{2}=131\cdot 83=10873.}

Пример с большим числом итераций

Пусть n=89755.{\displaystyle n=89755.} Тогда n≈299,591{\displaystyle {\sqrt {n}}\approx 299,591} или s=⌈n⌉=300.{\displaystyle s=\left\lceil {\sqrt {n}}\right\rceil =300.}

y=237{\displaystyle {\sqrt {y}}=237}

a=s+k+y=300+82+237=619{\displaystyle a=s+k+{\sqrt {y}}=300+82+237=619}

b=s+k−y=300+82−237=145{\displaystyle b=s+k-{\sqrt {y}}=300+82-237=145}

Данное разложение является не конечным, так как, очевидно, что число 145{\displaystyle 145} не является простым: 145=29⋅5.{\displaystyle 145=29\cdot 5.}

В итоге, конечное разложение исходного числа n{\displaystyle n} на произведение простых множителей 89755=5⋅29⋅619.{\displaystyle 89755=5\cdot 29\cdot 619.}

Оценка производительности

Наибольшая эффективность расчета методом факторизации Ферма достигается в случае, когда множители числа n{\displaystyle n} примерно равны между собой. Это обеспечивает относительно короткий поиск последовательности^[4]

s2−n, (s+1)2−n, (s+2)2−n … (s+k)2−n.{\displaystyle s^{2}-n,\ (s+1)^{2}-n,\ (s+2)^{2}-n\ …\ (s+k)^{2}-n.}

В наихудшем варианте, когда, к примеру, a{\displaystyle a} близко к n,{\displaystyle n,} а b{\displaystyle b} близко к 1, алгоритм Ферма работает хуже по сравнению с методом перебора делителей. Число итераций для данного случая:

Iter⁡(n)=a+b2−⌈n1/2⌉≈n2−⌈n1/2⌉,{\displaystyle \operatorname {Iter} (n)={\tfrac {a+b}{2}}-\left\lceil {n}^{1/2}\right\rceil \thickapprox {\tfrac {n}{2}}-\left\lceil {n}^{1/2}\right\rceil ,} то есть, очевидно, что оно имеет порядок O(n).{\displaystyle O(n).}

Метод факторизации Ферма будет работать не хуже метода перебора делителей, если Iter⁡(n)<n1/2,{\displaystyle \operatorname {Iter} (n)<{n}^{1/2},} отсюда можно получить оценку для большего делителя a<4n1/2.{\displaystyle a<4{n}^{1/2}.} Следовательно, метод Ферма имеет экспоненциальную оценку и, как метод пробного деления, не подходит для разложения больших чисел. Можно повысить эффективность, если выполнить сначала пробное деление числа n{\displaystyle n} на числа от 2 до некоторой константы B, а затем выполнить поиск делителей методом Ферма. Такой поход помогает избавиться от малых делителей числа n{\displaystyle n}