A Warrior to The Fourier Series !

Today I identified a funny teacher in me. My younger brother Thileepan had been preparing for his semester exam. He found  it difficult to go through the so-called Fourier Series. He approached me to help him out. I started going through the stuffs that I had learned/studied exactly 6 years back in my bachelor. I could see the difference in grasping now and then clearly. Though I dived into computer science , I still could pick up the differentiation and the long 'S' , integration. 

After gone through the stuffs, I asked him to sit and clearly decided not to preach the same in the book. The way the lesson started was really due to the impact of the Tamil Historical Novel - Mannan Magal[1]. Just by day before yesterday I finished reading the novel. The hero, Karikalan, brave and wise warrior of Chozha Emperor stayed in my heart.

"Thileep now you are in trouble that you should attack the Fourier Series  in 2 days you have got.  What you need is strong weapon(s), conditions suitable for attacking and finally a strategy to attack". He answered 'No'  for the questions I have shot: " Periodic functions?, Continuous functions? , functions?". Now I realized why he complained  his mathematics teacher ;-) 

I casually listened all his "Nos" which I thought really make him comfort. Then without explaining what is function, cts., function , etc. straightaway jumped into battle field. "Dear brother here is your weapon: Euler's Formula , this is perfect and sufficient conditions to attack : Dirichlet's conditions and finally apply this strategy : Bernoulli's formula" . He then ensured that he understood the main idea. 

What was remaining? Fundamental stuffs and tricks and tips. Started helping him to understand functions , continuous, discontinuous,  periodic functions with diagrams. I tricked him with a test : " When y = mx + c , where m is the only constant then y = f ( ? )". He did answered correctly " f ( x, c ) since y changes w.r.t x and c as well ".  Then discussed left , right limits to explain discontinuous functions. Then the importance of intervals and period. Then after explained about why on earth we need Fourier series asked him to start solving simple problems.

As I expected Integration and Trigonometry attacked him back. So now problem by problem he is asked to learn the tricks for integrating and for using trigonometry formulas. I saw him happy !  Me too happy !

But still lot to go through and also there are people who will only understand when we teach bottom to top. Nature of the problem also influence a lot. Teaching is not that easy truly. It is student's responsibility to understand his very own philosophy  of understanding. Then how teacher teach will not bother him a much.

  - Peramanathan Sathyamoorthy

[1]. Mannan Magal

 

Binary Multiplication - Can we do it better?

It was exciting working on the assignments of the course "Algorithms and Data structures II " this spring. As we kick started the first assignment we finished the first assignment so early, but for the problem of 'binary multiplication' we had many versions and I also had another fresh idea which is so efficient. As the deadline got closure I didn't tried out that idea. 

The idea is inspired from Vethic Mathematics(Nikhilam Sutra-Nikhilam Navataścaramam Daśatah-subtract all from 9 and the last from 10) and the corresponding algorithm explained in [1]. The time complexity is really depends upon the ratio of zeros and ones of the smaller multiplicand unlike most of the other algorithms. 

Before we go into actual problem let me briefly explain Nikhilam Sutra (Sutra means Formula in India). Let us multiply these two numbers 98 and 99. First step is to find the common base(power of 10 close the multiplicands) which is 100 here. This is how the sutra works:

   98         -  2

   99         -  1

-----------------

   100-2-1 | 02

= 9702

-----------------

But it is easy to see this in simple algebra. For the base x the multiplicands A,B can be written as (x - a)  and (x - b). Hence,

 A*B  = (x - a)*(x - b) 

                                                 = x^2 - (a+b) *x + a*b = x(x-a-b) + a*b.

In the same way, if A,B are greater than base then

 A*B   = (x + a)*(x + b) 

                     = x^2 + (a+b) *x + a*b 

             = x(x+a+b) + a*b 

         = x(A+b) + a*b

When the multiplicands are binary numbers the base x is of form 2^n. In the above formula multiplication of deficiencies from the base(a*b) is making us to think the possibility of recurrence in binary number system. Let us now multiply these 2 binary numbers recursively 111 and 111. Here base is 2^2 = 100

Base : 2^2 = 100                       Base: 2 = 10

-----------------------               -------------------------------------

   111 - 11                                    11    - 1

    +       *                          ==>      +       *

   111 - 11                                    11    - 1

------------------------               -------------------------------------

   100*(111+11)+ 1001     <==    10*(11+1) + 1 = 1000 + 1 = 1001

   101000 + 1001

= 110001

-------------------------

Here is the python implementation:



def binary_mult(a,b):


    # Helper Primitive Operations
    lenA = len(a)
    lenB = len(b)
    if lenA >= lenB:
        maxPart = a
        minLen = lenB
        minPart = b[1:]
    else:
        maxPart = b
        minLen = lenA
        minPart = a[1:]


    # Base Cases
    if lenA == 1:
        return b if a[0] == 1 else lenB*[0]
    elif lenB == 1:
        return a if b[0] == 1 else lenA*[0]
    
    # Divide , conquer and combine 
    else:
                        
        cLeft      = binary_add(maxPart,minPart)+[0]*(minLen-1)        
        aNew, bNew = new_parts(maxPart,minPart)        
        cRight     = binary_mult(aNew, bNew)
        c          = binary_add(cLeft,cRight)
        
    return c

As you can see above, the left most part of final product is given by cLeft which is simply the binary addition(x(A+b)).  Then new_parts(maxPart,minPart) is responsible for subtracting the base from both of the multiplicands(as base is always of the form 10[00...], one can implement this subroutine more efficient than trivial subtraction and you can remove all front zeros which is the result of subtraction - ex: for 1100011 * 100010 Base 1: 100000 , Base 2 : 10. It implies that despite bit length if the multiplicands have many contiguous zeros we get the result so faster !!!). Then cRight is recursively calculate the deficiency multiplications(a*b). Finally c does return the result.

I would like to dedicate this article to my teachers Pierre, Joseph, Nikos here in Uppsala University who helped me all the way whenever I was in trouble. Thanks a lot TAs :)

[1].A Generalized Recursive Algorithm for Binary Multiplication based on Vedic Mathematics