Archive for August, 2011
I ve been using Ruby for quite a while now and there’s a lot of things I like about it. Somehow I m gonna write about something where Ruby is not really good at. Ruby VM is not really known good for handling concurrency.
Upto Version 1.8.7, Ruby threads were known as ‘Green Threads‘ as these implementations were not using the native OS kernel threads instead they were using the threads created by the MRI in the user space thus making its operations quite costly. In the Ruby version 1.9.2, YARV ( Yet Another Ruby VM) was integrated with the Ruby VM, here although ‘Green Threads’ were mapped in one-to-one relation with the native kernel threads, they never are excecuted in parallel due to ‘Global Interpreter Lock’ put on by Ruby MRI. This version can never utilize the multi-cored systems efficiently thus Ruby 1.9.2 too was devoid from true concurrency.
A better solution for having true concurrency is to rely on the Java VM whose threading model has proven itself over the years and use JRuby. JRuby use system kernel Threads and the threads can run parallely in a multi-cored system.
Although Euler Project questions are designed to be solved sequentially. I wasn’t able to hold myself from giving it a try when I saw some of my roommates trying out this problem.
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Let us list the factors of the first seven triangle numbers:
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
I tried out the above problem and got myself a solution using two basic rules from mathematics.
- The nth triangular number can easily be obtained as : (n * n-1) / 2
- If a number ” n ” can be written as a multiple of two consecutive numbers “p” and “q” ie: if n = p * q then number of factors of n = number of factors of p * number of factors of q – 1
My Solution is available at my git-hub id:
My solution clocked below 1 seconds.( 0.244 seconds to be exact ) .