Fundamentals

References

• “Numerical Analysis”, Timothy Sauer

Polynomials

What is the best way to evaluate $P(x)=2x^4+3x^3-3x^2+5x-1$ say, at x = 1/2? Try to minimize the number of additions and multiplications.\

Method 1: This method requires 10 multiplications and 4 additions

$$P(\frac{1}{2})=2\ast \frac{1}{2}\ast \frac{1}{2}\ast \frac{1}{2}\ast \frac{1}{2}+3\ast \frac{1}{2}\ast \frac{1}{2}\ast \frac{1}{2}-3\ast \frac{1}{2}\ast \frac{1}{2}+5\ast \frac{1}{2}-1$$

Binary Numbers

Binary numbers are expressed as

$$\cdots b_2{b}_1{b}_0.b_{-1}{b}_{-2}\cdots$$

where each binary digit, or bit, is 0 or 1. The base 10 equivalent to the number is

$$\cdots b_2{2}^2+b_1{2}^1+b_0{2}^0+b_{-1}{2}^{-1}+b_{-2}{2}^{-2}\cdots$$

For example the decimal number 4 is expressed as $(100.{)}_2$ in base 2, and 3/4 is represented as $(0.11{)}_2$.

Decimal to Binary

To convert to binary it is simplest to break the number into integer and fractional parts and convert each part separately. For the number $(53.7{)}_{10}=(53{)}_{10}+(0.7{)}_{10}$ we convert each part to binary and combine.

Integer part Convert decimal integers to binary by dividing by 2 successively and recording the remainders. The remainders, 0 or 1, are recorded by starting at the decimal point (or more accurately, \textbf{radix}) and moving away (to the left). For $(53{)}_{10}$ we would have

$$53÷2=26R1$$ $$26÷2=13R0$$ $$13÷2=7R1$$ $$6÷2=3R0$$ $$3÷2=1R1$$ $$2÷2=0R1$$

Therefore, the base 10 number 53 can be written in bits as $110101$, denoted $(53{)}_{10}=(110101.{)}_2$. $110101=2^5+2^4+2^2+2^0=32+16+3+1=53$

Fractional part Convert $(0.7{)}_{10}$ to binary by reversing the preceding steps. Multiply by 2 successively and record the integer parts, moving away from the decimal point to the right.

$$.7\times 2=.4+1$$ $$.4\times 2=.8+0$$ $$.8\times 2=.6+1$$ $$.6\times 2=.2+1$$ $$.2\times 2=.4+0$$ $$.4\times 2=.8+0$$ $$⋮$$

Notice that the process repeats after four steps and will repeat indefinitely exactly the same way. Therefore,

$$(0.7{)}_{10}=(.1011001100110\cdots {)}_2=(.1\overline{0110}{)}_2$$

Putting the two parts together we get

$$(53{)}_{10}=(110101.1\overline{0110}{)}_2$$