Что означает log2 в информатике

Введение в анализ сложности алгоритмов (часть 3)

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Логарифмы

Практическая рекомендация: на соревнованиях алгоритмы часто реализуются на С++. Как только вы проанализировали сложность вашего алгоритма, так сразу можете получить и грубую оценку того, как быстро он будет работать, приняв, что в секунду выполняется 1 000 000 команд. Их количество считается из полученной вами функции асимптотической оценки, описывающей алгоритм. Например, вычисление по алгоритму с Θ( n ) займёт около секунды при n = 1 000 000.

Рекурсивная сложность

Если вы всё же не уверены в этом, то вы всегда можете найти точную сложность путём подсчёта количества инструкций. Примените этот метод к данной функции, чтобы найти её f( n ), и убедитесь, что она линейная (напомню, что линейность означает Θ( n ) ).

Логарифмическая сложность

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

Вот реализация такого метода в псевдокоде:

Если вы не уверены, что метод работает в принципе, то отвлекитесь и решите вручную какой-нибудь простой пример.

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

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

Источник

Один способ вычисления логарифма по основанию 2

Вычисление логарифмов довольно распространённая операция в цифровой обработке сигналов. Чаще пожалуй приходится считать только свёртки (умножение с накоплением) и амплитуды с фазами. Как правило для вычисления логарифмов на FPGA применяется алгоритм CORDIC в гиперболическом варианте, требующий только таблицы и простых арифметических операций. Однако это не всегда бывает удобно, особенно если проект большой, кристалл маленький и начинаются танцы с оптимизацией. Именно с такой ситуацией и пришлось мне однажды столкнуться. Оба порта блока RAM (Cyclone IV) уже плотненько были в работе, не оставляя свободных окон. Использовать ещё один блок под гиперболический CORDIC не хотелось. Зато был умножитель, для которого во временной диаграмме получалось приличное свободное окно. Денёк подумав, я сочинил следующий алгоритм, в котором не используется таблиц, но есть умножение, точнее возведение в квадрат. И поскольку схемотехнически возведение в квадрат проще общего случая умножения, возможно этот алгоритм представляет интерес для специализированных микросхем, хотя для FPGA разницы конечно нет. Подробнее под катом.

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

Пусть есть число X. Требуется найти число Y такое, чтобы .
Положим так же что X лежит в интервале от 1 до 2. Это не слишком ограничивает общность, поскольку X всегда можно перевести в этот интервал умножением или делением на степень двойки. Для Y это будет означать добавление или вычитание целого числа, что делается легко. Итак X лежит в интервале от 1 до 2. Тогда Y будет лежать в интервале от 0 до 1. Запишем Y как бесконечную двоичную дробь:

Коэффициенты в этой записи есть ни что иное, как просто биты двоичного представления числа Y. Причём поскольку Y меньше 1, очевидно что =0.

Возведём наше первое уравнение в квадрат: и как и ранее, запишем двоичное представление числа 2Y. Очевидно, что

Т.е. биты остались теми же, просто сдвинулись степени двойки. Бита в представлении нет, потому что он равен нулю.

Возможны два случая:

1) 2$» data-tex=»inline»/>, 2Y > 1,

2) , 2Y Вот полный код модуля и теста

Запустим тест вот таким скриптом:

Запустив тест, видим окончательный вывод симулятора — value=27819, result=9ba5. Верилог выдал то же самое что С. Временная диаграмма тут довольно тривиальна и особого интереса не представляет. Поэтому её не привожу.

Убеждаемся, что они совпадают бит в бит. Итого, реализация на верилоге повторяет с точностью до бита модель на С. Это и есть тот результат, которого следует достигать, реализуя алгоритмы в железе.

На этом пожалуй всё. Надеюсь кому-то этот мой опыт окажется полезен.

Источник

Что такое логарифм. Как посчитать логарифм. Свойства логарифмов. Примеры решения логарифмов

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

Часто у учеников возникает путаница, где аргумент, а где основание логарифма. И что же нужно возвести в степень, чтобы этот логарифм, наконец, посчитать.

В этой статье мы откроем секрет, как легче запомнить принцип решения логарифма.

Итак, давайте разбираться, что такое логарифм.

Что такое логарифм и как его посчитать

Логарифм имеет следующий вид:

где a – это основание логарифма,

b – это аргумент логарифма

Чтобы узнать значение логарифма приравняем его к X.и преобразовываем вЗапомните, что именно основание (оно выделено красным) возводится в степень.

Чтобы было легче, можно запоминать так – основание всегда остается внизу (и в первом, и во втором выражении a внизу)!

Чтобы вычислить данный логарифм, необходимо приравнять его к X и воспользоваться правилом, описанным выше:А в какую степень нужно возвести 2, чтобы получилось 8? Конечно же в третью степень, таким образом:

Еще раз обращаю ваше внимание, что основание (в нашем случае это – 2) всегда находится внизу и именно оно возводится в степень.

Логарифмы со специальным обозначением

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

Десятичный логарифм

Десятичный логарифм обозначается lg и имеет основание 10, т.е.

Чтобы вычислить десятичный логарифм, нужно 10 возвести в степень X.

Например, вычислим lg100

Натуральный логарифм

Натуральный логарифм обозначается ln и имеет основание e, то есть

Чтобы вычислить данный логарифм нужно число е возвести в степень x. Некоторые из вас спросят, что это за число такое е? Число е – это иррациональное число, т.е. точное его значение вычислить невозможно. е = 2,718281…

Сейчас не будем подробно разбирать, зачем это число нужно, просто запомним, что

И вычислить его можно таким образом:

Основные свойства логарифмов

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

Совет – тренируйтесь применять эти свойства в обе стороны, то есть как слева направо, так и справа налево!

Рассмотрим свойства логарифмов на примерах.

Логарифмический ноль и логарифмическая единица

Это следствия из определения логарифма. И их нужно обязательно запомнить. Эти простейшие свойства нередко вводят учеников в ступор.

Запомните, что логарифм от a по основанию а всегда равен единице:

log_a a = 1 – это логарифмическая единица.

Если же в аргументе стоит единица, то такой логарифм всегда равен нулю независимо от основания, так как a 0 = 1:

log_a 1 = 0 – логарифмический ноль.

Основное логарифмическое тождество

В первой формуле число m становится степенью, которая стоит в аргументе. Данное число может быть любым. Некоторые выражения могут быть решены только с помощью этого тождества.

Вторая формула по сути является просто переформулированным определением логарифма

Разберем применение тождества на примере:

Необходимо найти значение выраженияСначала преобразуем логарифм

Вернемся к исходному выражению и применим правило умножения степеней с одинаковым основанием:Теперь применим основное логарифмическое тождество и получим:

Сумма логарифмов. Разница логарифмов

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

Обратите внимание, что формулы суммы и разности логарифмов верны только для логарифмов с одинаковыми основаниями! Если основания разные, то данные свойства применять нельзя!

Вынесение показателя степени из логарифма

Вынесение показателя степени из логарифма:

Переход к новому основанию

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

Такие формулы чаще всего нужны при решении логарифмических уравнений и неравенств.

Разберем на примере.

Необходимо найти значение такого выраженияДля начала преобразуем каждый логарифм с помощью свойства вынесения показателя степени из логарифма:

Теперь применим переход к новому основанию для второго логарифма:Подставим полученные результаты в исходное выражение:

10 примеров логарифмов с решением

1. Найти значение выражения2. Найти значение выражения3. Найти значение выражения4. Найти значение выражения5. Найти значение выражения6. Найти значение выраженияСначала найдем значениеДля этого приравняем его к Х:Тогда изначальное выражение принимает вид:

7. Найти значение выраженияПреобразуем наше выражение:Теперь воспользуемся свойством вынесения показателя степени из логарифма и получим: 8. Найти значение выраженияТак как основания логарифмов одинаковые, воспользуемся свойством разности логарифмов:9. Найти значение выраженияТак как основания логарифмов разные, применять свойство суммы логарифмов нельзя. Поэтому решаем каждый логарифм по отдельности:Подставляем полученные значения в исходное выражение:

10. Найти значение выраженияОбращаем внимание, что данное выражение – это не произведение логарифмов. У логарифма по основанию 4 подлогарифным выражением является log₂16. Поэтому сначала найдем значение log₂16, а затем подставим полученный результат в log₄:

Надеюсь, теперь вы разобрались, что такое логарифм.

Источник

Содержание урока

Измерение информации. Содержательный подход

Формула Хартли

Измерение информации. Содержательный подход

Формула Хартли

Если значение N равно целой степени двойки (4, 8, 16, 32, 64 и т. д.), то показательное уравнение легко решить в уме, поскольку i будет целым числом. А чему равно количество информации в сообщении о результате матча «Динамо»-«Зенит»? В этой ситуации N = 3. Можно догадаться, что решение уравнения

2 i = 3.

будет дробным числом, лежащим между 1 и 2, поскольку 2 1 = 2 2 = 4 > 3. А как точнее узнать это число?

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

Читается это так: «логарифм от N по основанию 2». Смысл очень простой: логарифм по основанию 2 от А — это степень, в которую нужно возвести 2, чтобы получить N. Например, вычисление уже известных вам значений можно представить так:

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

В табличном процессоре Microsoft Excel функция логарифма имеет следующий вид: LOG(apryмент; основание). Аргумент — значение N находится в ячейке А2, а основание логарифма равно 2. В результате получаем с точностью до девяти знаков после запятой: i = log₂3 = 1,584962501 (бита).

Формула для измерения количества информации: i = log₂N была предложена американским ученым Ральфом Хартли — одним из основоположников теории информации.

Формула Хартли: i = log₂ N
Здесь i — количество информации, содержащееся в сообщении об одном из N равновероятных исходов события.

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

Следующая страница Вопросы и задания

Источник

Документация

Основывайте 2 логарифма и рассечение числа с плавающей запятой

Синтаксис

Описание

Примеры

Базирование 2 значений логарифма

Рассечение числа с плавающей запятой

Разделите несколько чисел в экспоненту и мантиссу. Эти операции все следуют за стандартной арифметикой IEEE®.

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

Соберите результаты в таблице. Преобразуйте числа в векторы символов в целях отображения.

Входные параметры

X — Введите матрицу
скаляр | вектор | матрица | многомерный массив

Введите матрицу в виде скаляра, вектора, матрицы или многомерного массива.

Типы данных: single | double
Поддержка комплексного числа: Да

Выходные аргументы

Y Базирование 2 значений логарифма
скаляр | вектор | матрица | многомерный массив

F — Значения мантиссы
скаляр | вектор | матрица | многомерный массив

E — Значения экспоненты
скаляр | вектор | матрица | многомерный массив

Советы

Расширенные возможности

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

Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.

Генерация кода графического процессора
Сгенерируйте код CUDA® для NVIDIA® графические процессоры с помощью GPU Coder™.

Эта функция полностью поддерживает основанные на потоке среды. Для получения дополнительной информации смотрите функции MATLAB Запуска в Основанной на потоке Среде.

Массивы графического процессора
Ускорьте код путем работы графического процессора (GPU) с помощью Parallel Computing Toolbox™.

Указания и ограничения по применению:

Синтаксис [F,E] = log2(X) не поддерживается.

Распределенные массивы
Большие массивы раздела через объединенную память о вашем кластере с помощью Parallel Computing Toolbox™.

Смотрите также

Открытый пример

У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?

Документация MATLAB

Поддержка

© 1994-2021 The MathWorks, Inc.

1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.

2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.

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

5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.

Источник