Определите, является ли данное целое число элементом последовательности Фибоначчи в C, не используя float

Question

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

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

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

Насколько я знаю, положительное целое число - это ровно число Фибоначчи, если один из

(5n ^ 2) + 4

или

(5n ^ 2) - 4

это идеальный квадратПоэтому я ответил на вопрос: это просто, поскольку подпрограмма должна определить, так ли это.

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

Тогда я сказал, хорошо, мы можем построить массив с квадратными числами до 256. Затем мы могли бы выполнить итерациюи сравните их с числами, заданными формулами (см. выше).Они сказали: это плохой подход, даже если он сработает.Поэтому они не приняли этот ответ.

Наконец я сдался.Так как у меня не было других идей.Я спросил, каково было бы решение: они сказали, это не будет сказано;но посоветовал мне попробовать поискать сам.Мой первый подход (формула 2) должен быть ключевым, но квадратный корень может быть сделан альтернативно.

Я много гуглял дома, но никогда не находил "альтернативных" алгоритмов счетчика квадратного корня.Везде разрешалось использовать плавающие числа.

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

Даже если я провалил тест на собеседование, для меня это очень интересная тема - работать над архитектурами, в которых не допускаются операции с плавающей точкой.

Поэтому мои вопросы:

1. Как можно смоделировать плавающие числа (если разрешено использовать только целые числа)?
2. Каким будет возможный заголовок в C для этой упомянутой проблемы?Примеры кода приветствуются.

Answer 1

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

• Как минимум, двоичный поиск должен быть первой мыслью при поиске в таблице.Некоторые рассчитанные подходы поиска также могут быть предложены для обсуждения, такие как использование команды find-first-set-bit для индексации в таблице.
• Хэширование может быть другой идеей, заслуживающей рассмотрения, особенно с учетом эффективного настраиваемого хэша.может быть построен.
• Как только мы решили использовать таблицу, вполне вероятно, что прямая таблица чисел Фибоначчи будет более полезной, чем таблица квадратов.

Answer 2

Цель этого типа интервью - увидеть, как вы подходите к новым проблемам.Если вы уже знаете ответ, это, несомненно, ваша заслуга, но на самом деле это не ответ на вопрос.Интервьюеру интересно наблюдать за тем, как вы решаете проблемы.

По этой причине часто интервьюер добавляет дополнительные ограничения, пытаясь вывести вас из зоны комфорта и посмотреть, как вы справляетесь.

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

По-видимому, необходимо вычислить 5n²±4, вычислить квадратные корни и затем убедиться, что один из них является целым числом.Имея доступ к реализации с плавающей запятой с достаточной точностью, это не будет слишком сложным.Но насколько это точно?Если n может быть произвольным 32-битным числом со знаком, то n², очевидно, не вписывается в 32 бита.Фактически, 5n²+4 может составлять до 65 бит, не считая знакового бита.Это намного выше точности double (обычно 52 бита) и даже long double, если доступно.Поэтому вычисление точного квадратного корня будет проблематичным.

Конечно, нам на самом деле не нужны точные вычисления.Мы можем начать с аппроксимации, возвести ее в квадрат и посмотреть, будет ли она на четыре больше или на четыре меньше 5n².И легко понять, как вычислить правильное предположение: оно будет очень близко к n×√5.Используя хорошее предварительно вычисленное приближение √5, мы можем легко выполнить это вычисление без необходимости использования плавающей запятой, без деления и без функции sqrt.(Если приближение не точное, нам может потребоваться скорректировать результат вверх или вниз, но это легко сделать с помощью идентификатора (n+1)² = n²+2n+1; как только мы получим n², мы можем вычислить (n+1)² только с добавлением.

Нам все еще нужно решить проблему точности, поэтому нам понадобится какой-то способ работы с 66-битными целыми числами, но нам нужно только реализовать сложение и умножение натуральных чисел, что значительно проще, чем полноепакет bignum. Действительно, если мы сможем доказать, что наша оценка квадратного корня достаточно близка, мы могли бы безопасно выполнить проверку по модулю 2³¹.

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

Итак, какие еще способы узнать, является ли n числом Фибоначчи.Один интересный факт заключается в том, что если n равно Fib(k), то k является полем log<sub>&phi;</sub>(k&times;&radic;5 + 0.5).Поскольку log<sub>&phi;</sub> легко вычисляется из log<sub>2</sub>, который, в свою очередь, может быть аппроксимирован простой побитовой операцией, мы могли бы попытаться найти аппроксимацию k и проверить ее, используя классическую O(log k) рекурсию для вычисления Fib(k).Ни одно из вышеприведенных чисел не превышает емкость 32-разрядного знакового типа.

Еще проще: мы можем просто пройти цикл Фибоначчи в цикле, проверяя, достигли ли мы целевого числа.Нужно всего 47 петель.Кроме того, эти 47 чисел можно предварительно рассчитать и выполнить поиск с помощью бинарного поиска, используя намного меньше, чем разрешенные вами байты 1 КБ.