[Tutor] extreme basics

[spir]

Le Mon, 05 Jan 2009 17:59:06 +1000,
Mr Gerard Kelly <s4027340 at student.uq.edu.au> a écrit :

> This is extremely weird, I think.
> 
> Here is a tiny program:
> 
> from math import *
> from Numeric import *
> 
> x=[0]*10
> 
> 
> for counter in rangelen((x)):
>       x[counter]=counter*0.1
> 
> print x
> 
> Here is what I get:
> 
> [0.0, 0.10000000000000001, 0.20000000000000001, 0.30000000000000004,
> 0.40000000000000002, 0.5, 0.60000000000000009, 0.70000000000000007,
> 0.80000000000000004, 0.90000000000000002]
> 
> What on Earth is going on with those decimals at the end? Is this a
> floating point thing?


I will take the opportunity to try and explain that "weird" issue, because I explored the topic a
long time ago. If you /really/ know what "base n", "floating point", and "scientific notation"
mean, just skip first section.

denis


-1- bases

We are so used to the decimal notation that we do not think anymore what it actually means. In
fact, "decimal" both means in base 10 (from latin root dec- = ten) and fractional (from decim- =
tenth). A decimal notation like "1.2" represents 12/10, where /10 expresses the base number and
the fractional feature. in that case, "10" mean ten only because the base is ten: "10" mean
sixteen in base sixteen, three in base three, two in base two.

To generalize the decimal pattern, consider
123.45678
This expresses a number equal to 12345678/100000 = 12345678/(10^5) = 12345678*(10^-5). The
so-called scientific notation represents this as 12345678e-5, or else 1.2345678e2. "e^n" mean
"*base^n".

Now, if we change to another base b, the pattern is exactly the same, except that:
* each digit is a digit in base b
* b is exponentiated
For instance:
base 16:	123af.59	= 123af59 / (16^2) = 123af59e-2
base 3:		123.31		= 12331 / (3^2) = 12331e-2
base 2:		101.01		= 10101 / (2^2) = 10101e-2 (=21/4=5.25)


-2- exactitude

When we write down a number, whatever the notation, it can only be an exact number in the sense
that it has a finite number of digits. The point is that an exact number in decimal base must not
be exact (in that sense) in another base -- and conversely. This may seem weird indeed (I had a
hard time understanding it).

Below, the first version of each number representation (silently given by repr()) shows a real
internal value, while the second (str()) is nicely arranged for normal humans.
>>> 0.5; print 0.5
0.5
0.5
>>> 0.7; print 0.7
0.69999999999999996
0.7

Python computes in base 2, so that each non-integer number is represented as
mantissa / 2^n
For a number to be exact for python, this number must then be so that we can find a proper
mantissa and a proper exponent n that satisfies number = mantissa / 2^n
or
mantissa/number = 2^n
As 2^n can only only be 1,2,4,8... there is no garanty that it is possible at all (in a reasonable
number of digits -- because both mantissa and n must be ints). The output of Gerard's code indeed
shows that a/10 will be an exact number in base 2 only for a=5.

Why 0.5?
0.5 = 5/10 ==> base 2: 101/1010
We can see above that the denominator is a multiple of the numerator, so that we can simplify:
101/1010 = 1/10 (base10:1/2) = 1/2^1 = 1e-1 = 0.1
So that 0.5 in base 10 can be expressed as the exact number 0.1 in base 2.

Now, let us try 0.7:
0.7 = 7/10 ==> base 2: 111/1010
too bad! It won't match so easily. To express 0.7, we must try and find a proper
(mantissa,exponent) pair that together express a result of 0.7. Good luck!

Conversely, as I see it, there is no exact binary number which can't be exactly expressed in
decimal base. The reason simply is, I guess, that 10 is a multiple of 2. Fractions based on 2
(0.1, 0.01, 0.001...) are not as simple in base 10, but they can be written:
>>> for e in range(1,10):
		print repr(1.0 * 2**(-e)),
... ... 
0.5 0.25 0.125 0.0625 0.03125 0.015625 0.0078125 0.00390625 0.001953125

On the contrary, we find problems at once when starting from base 3, as a base three decimal
number expression means mantissa/3^n and 1/3 is already inexact in base 10: base3: 0.1 =
1/10		==> base10: 1/3 = 0.333333... base3: 1.2 = 12/10		==> base10:
5/3 = 1.666666...








------
la vida e estranya