[tutor] Do I need to have a strong math skills to program

[Danny Yoo]

On Sun, 3 Nov 2002, Dan Dud wrote:

> Hope everyone weekend is going great. I working through the "how to
> think like a computer scientist" I'm stuck on the part which you have to
> define a hypotenuse triangle. I don't have a lot of math skills. Do I
> have to have a lot of math skills to be good at programming??? I've
> decided to skip that part and move on. I hope everyone weekend is going
> great and I'll talk to you all soon...

Hi Dan,

I just wanted to jump back into this question because it's such a fun one
to revisit.  *grin* There are some advantages for knowing math: with some
math knowledge, we can make analogies between computer techniques and math
techniques.

Warning: this message is very long, and halfway though, I just completely
lose my head and jump into calculus.  I didn't mean to; it just happened!
*grin* You can read up to the middle, and stop there.  But for those
who've taken an introductory course in calculus... I dunno, maybe this
will amuse you.


Here's one problem in particular that shows a particular technique that's
works with both computers and maths.  Let's say that we had a number, and
we'd like to turn it into a string.  How hard would it be to transform
that string into a integer?

(A quick solution would use the string() built-in function, since it knows
how to turn pretty much anything into a string... but let's pretend that
we didn't know about it yet.

Say that we had the number 12345.  How could we turn it into the string
"12345"?  Well, let's try something simpler: let's go for just single
digits: if we're given a number between 0 and 9, we can easily return the
corresponding string:

###
>>> def singleNumberToString(number):
...     if number == 0: return "0"
...     if number == 1: return "1"
...     if number == 2: return "2"
...     if number == 3: return "3"
...     if number == 4: return "4"
...     if number == 5: return "5"
...     if number == 6: return "6"
...     if number == 7: return "7"
...     if number == 8: return "8"
...     if number == 9: return "9"
...
>>> singleNumberToString(3)
'3'
>>> singleNumberToString(3) + singleNumberToString(3)
'33'
###

That definition above is almost silly stupid.  *grin* There are better
ways of defining it, but let's leave it at that for the moment.


So given any single-digit number, it's really easy to peek and figure out
the last character.  That's the "peek" part.

Why does this get us closer?  Well, because if we have something like
12345, we can first divide the whole thing by ten, and take the remainder:

###
>>> 12345 % 10
5
###

and then run that through our little singleNumberToString() function:

###
>>> singleNumberToString(5)
'5'
###

and now we've got the last digit.  The problem is trying to do this sort
of thing to the rest of the digits, and that's the "shift" part.  It turns
out that this isn't so bad: if we divide our number by 10, it's almost as
if all the digits move to the right by one place (and the last digit jumps
off the number);

###
>>> 12345 / 10
1234
###

And now we can repeat our "peeking" process to get the next digit:

###
>>> singleNumberToString(1234 % 10)
'4'
###

And now we've just picked up the second to last character.

If we do this process over and over (peek, shift, peek, shift, ...), we'll
eventually run out of digits, and that's when we know we're done.  Then we
can just join all the characters together, and we've got a stringified
version of our number!

I know I'm going fast, but I hope that made some sort of sense. Here's
some code that implements this idea:

###
>>> def turnNumberIntoString(number):
...     characters = []
...     while number != 0:
...         next_digit = number % 10
...         next_character = singleNumberToString(next_digit)
...         characters.append(next_character)
...         number = number / 10
...     characters.reverse()
...     return ''.join(characters)
...
>>> turnNumberIntoString(12345)
'12345'
###





[Here's where things go weird.  The next section is somewhat advanced, now
that I think about it.  Argh;  I don't know how to explain it well enough
to make sense without calculus!

If you get stuck on it, that's probably because I don't understand it well
enough to explain it well.]



This "peek and shift" trick is something that mathematicians use too!  As
a particular example, mathematicians use the peek-and-shift technique
whenever they apply something called "Taylor's Expansion".  Taylor's
expansion says that some math functions can be transformed into a huge
polynomial, a "power series".

That is, Taylor's theorem says that, for a function --- let's call it f(x)
--- it's possible to transform it into a huge powers series in x.  For
example, the exponential function:

    f(x) = e**x

can be considered to be a power series that looks, oddly enough, like
this:

    e**x = 1 + x/1 + x**2/(1*2) + x**3/(1*2*3) + x**4/(1*2*3*4)...

or, more concisely,

    e**x = sum    (1/n!) * (x**n)
           n > 0


When I saw this, I didn't believe it at first.  Does this even work?  But
we can try it when x is equal to 1:

###
>>> math.e
2.7182818284590451
###

What happens when we plug 1 into the power series?  We should get math.e.
But since we can't evaluate an infinite sum numerically, I'll just satisfy
myself if the first few terms work out.

###
>>> def simulate_e():
...     sum = 0
...     for n in range(10):
...         sum = sum + 1.0 / factorial(n)
...     return sum
...
>>> def factorial(n):
...     if n == 0: return 1
...     return n * factorial(n-1)
...
>>> simulate_e()
2.7182815255731922
###

Wow!  So that comes pretty close, even with just ten terms of that
infinite sum.


In general, for the functions where Taylor's expansion works, the power
series will have the form:

    f(x) = a_0 * x**0  + a_1 * x**1  + a_2 * x**2 + ...

which is just another way of saying:

    f(x) =  sum    a_n    * (x**n)
           n > 0

Nice and general, and totally nondescriptive.  *grin* What all of those
darn a_n's about?!  And how did do we know that the nth coefficient of the
e**x expansion is (1/n!)?


That's where the peek-and-shift technique comes into play.  What's neat
about this is that the only tools we need is the mere _belief_ that such a
series exists.  Well, that and differentiation.


Let's pretend, for the moment, that we do know that e**x can be expanded,
but we have no clue whatsover what the coefficients will look like.  What
to do?


Well, we can at least look at the very first coefficient a_0: we can
"peek" at it by seeing what happens when x=0:

    e**0 = a_0 (0**0) + a_1 (0**1) + a_2 (0**2) + ...

According to the sci.math.faq, 0**0 is equal to 1, if we know what's good
for us.

    http://www.faqs.org/faqs/sci-math-faq/specialnumbers/0to0/

All the other coefficient terms disappear, giving us:

    e**0 = a_0

and now we at least know that a_0 is equal to 1.  Too bad we don't know
what the other terms look like yet.


But that's where "shifting" comes in: we can "differentiate" our function,
a technique in calculus that flattens a power series.  What
differentiation does to a power series is pretty neat: it turns something
that looks like:

    e**x   =  a_0 x**0 + a_1 x**1 + a_2 x**2 + a_3 x**3 + ...

and "shifts" all the coefficients to the left!

    D(e**x) =  1 * a_1 x**0 + 2 * a_2 x**1 + 3 * a_3 x**2 + ...

Differentiation adds a little bit of crud onto each coefficient, so the
shift isn't perfect, but it's conceptually the same as when we divided by
10 in the first half of this long and tortuously twisted message.


e**x is impervious to differentiation, so now we come back to:

    e**x = 1 * a_1 x**0 + 2*a_2 x**1 + 3*a_3 x**2 + ...

With this shifted formula, now we can repeat our peeking by trying to plug
in 0 whenever we see 'x':

    e**0 = 1 * a_1 (0**0) + 0 + 0 + 0 + ...

So a_1 is also equal to 1.


We can continue doing the "peek-shift"  process to pull out any of the
a_n's out.  If we do this a few more times, we start seeing a pattern:

    a_0 = 1
    a_1 = 1/1
    a_2 = 1/(1*2)
    a_3 = 1/(1*2*3)
    a_4 = 1/(1*2*3*4)
    ...

and that's where we can stop and just say that the nth coefficient of our
expansion's going to be:

    a_n = 1/(n!)


In summary, the ideas that help us to convert a number into a string are
very similar to the ideas that mathematicians use to perform Taylor's
expansion.


Sorry about the digression!