tags : Math, Big Oh Notation, Complexity Theory, Algorithms

## Intro

A logarithm is the power to which a number must be raised in order to get some other number. Some references refer logarithm as an exponent. It can find the cause for an effect, i.e the **input for some output**.

John Napier introduced Logarithm as a means of simplifying calculations in 1614, that’s about 400 years ago. It can do amazing and boring(?) things like counting zeros of a number($log_{10}(1000)=3$), extracting the fifth root of 27, list goes on. This page contains information mostly about real logs, there are something called the complex log aswell! and there’s Discrete logarithm which has uses in Cryptography.

- $y=27_{0.2}$
- Taking log on both sides
- Solving and later taking the antilog.
We can do the same for multiplying large numbers aswell.

- Convert multiplication problem into an addition problem : $log_{b}xy=log_{b}x+log_{b}y$
- Convert division problem into a subtraction problem : $log_{b}yx =log_{b}x−log_{b}y$
- Convert exp. problem into a multiplication problem : $log_{b}x_{y}=ylog_{b}x$

### A look into the definition

- If $x>0$ and $b∈(0,∞),b=1$ then $y=log_{b}(x)$ iff $b_{y}=x$
- In the equation $y=log_{b}(x)$, $y$ is called the
**logarithm.** - Logarithmic functions are
**only defined for positive real numbers**. - The function $log_{b}(x)$ is continuous for $x>0$

Proving that $x$ needs to be positive is simple; If $x$ were negative or 0, $b_{y}$ has to result in a negative number or 0. No matter what $y$ is, since $b$ is a positive number it’s never going to be a negative number or 0.

Some interesting discussions negative base:

Now why does $b$(the base) has to be a positive real number not equal to 1?

$b_{y}=x⟹b_{log_{b}(x)}=x$

#### Base 1

- For $x=5$, $log_{1}(5)$ has no solution.
- For $x=1$, $log_{1}(1)$ can be anything.

#### Base 0

For $x=0$, $log_{0}(0)$ can be anything, otherwise it does not have a solution. We also know that $x$ can’t be $0$

#### Base -2

- $(−2)_{2}=4$ $⟹$ $log_{−2}(4)=2=log_{2}(−2)log_{2}(4) ⟹log_{2}(−2)=1⟹2_{1}=−2$ which is untrue.
- It’s also because you can’t take even roots of negative numbers. Eg. $(−2)_{1.01}=(−2)_{100101}=100−2_{101} $ is not defined and we lose some properties such as continuity in the real plane.

## Bases

In logarithm the value of a positive number depends not only on the number but also on the base of the logarithm. There are some well known bases.

- Natural Log: $log_{e}$ written as ln
- Common Log: $log_{10}$ written as lg
- Binary Log: $log_{2}$ written as lb

### Natural Log

The natural logarithm has the number e (that is b ≈ 2.718) as its base; its use is widespread in mathematics and physics because it is immune to integration and differentiation.i.e. $dxd(e_{x}) =e_{x}$. Natural log is a continuous function.

### Common Log

The logarithm base 10 (that is b = 10) is called the common logarithm and has many applications in science and engineering.

#### Numbers greater than 1 ($x$)

When it’s about $lg$ of numbers greater than 1 that differ by a factor of a power of 10 all have the same fractional part. This fractional part is called the `mantissa`

; The integer part, called the `characteristic`

```
>>> math.log10(3)
0.47712125471966244
>>> math.log10(30)
1.4771212547196624
>>> math.log10(300)
2.4771212547196626
```

$log_{10}$ and number of digits:If $n$ has $d$ digits, then $10_{d−1}≤n<10_{d}$

$⟹d−1≤log_{10}(n)<d$ $(∵log_{10}10_{y}=y)$

$⌊log_{10}(n)⌋=d−1$ gives the integer part(the

`characteristic`

)$⟹⌊log_{10}(n)⌋+1=d$, total number of digits in $n$

#### Numbers greater than 0 but less than 1

Numbers greater than 0 and less than 1 have negative logarithms for the $log_{10}$ and other usual bases; but that’s not true for something like $log_{0.2}(0.8)$

### Binary Log

The binary logarithm uses base 2 (that is b = 2) and is commonly used in computer science.

### Base does not matter?

As far as big-Oh notation is concerned, the base of the logarithms doesn’t make any real difference, because of **Change of Base** property and logarithms are related by some constant. So it’s common to see just $log(x)$ notation in big-Oh as the base does not matter.

## Characteristic and Mantissa

- Log of +ve number(2 parts)
- Integer part: +ve, -ve or 0
- Positive fraction: or 0