Digits/Life of PI

Well this post comes mainly after watching Life of Pi and being inspired by it. I always wanted to solve this problem PIVAL but never quiet got the kick untill watching the movie.

Till date about 10 million digits of PI have been successfully known. I started with Machin's Machin's formula which gives correct values till 100 decimal places. Then i came upon this formula by Chudnovsky which helped me to calculate around 35000 digits of PI within the time limit specified (~25 secs). On applying binary splitting and a customized square root function (Newton's method) i was able to improve to 37000. Hope to increase more and in search of better results.

Modifying the Euler Totient Funtion

Hi All, Came across an interesting problem and thought of sharing it. Most would know about the ETF , which basically helps one to count the number of integers co-prime and less than N . However to get the count of integers which are co-prime to N but less than a specified limit (say M <= N ) is not so common.

At first i thought of modifying the ETF calculation ETF calculation by initialising result to m . The results were 'almost' accurate but not correct. So as a turnaround , i got a different approach. We can factorise N and then from M do an inclusion-exclusion principle on the factors of N . i.e say the factors of N are p1,p2,p3..pk . Then the required solution would be : M - sum(M/pi) (1<=i<=k) + sum(M/pi*pj) - ..sum(M/pi*pj*..pk)

Though i had got the result but coding it was the next challenge. 1. First step was easy as it involved just factoring N . (O(sqrt(N)))
2. Next we had to get all combinations of the factors, in other words all the subsets. This can be done by bitmask technique, i.e consider binary representation of integers and if the ith bit is set then the integer is in the set . We can store each subset in a vector and then based on the size of the subset calculate the denominator with appropriate sign!
3. Thus we can calculate the answer perfectly. :)

Hope it was useful. Finally a post after almost 6 months.Been really busy , specially after getting into this corporate world.

A tutorial on trees

I came across this site eternally confuzzled which seems really good on data structures, specially trees and thought of sharing it..Hope it's useful :)