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.
Sunday, December 9, 2012
Saturday, October 6, 2012
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.