Carmichael’s numbers generator – C#

Hi community,

Please find below a code snippet I wrote last night for generating the Carmichael’s numbers.

This demo was written in C# and it implements TPL to take advantage of multiple processors.

It is intended to be demoed at Tech-Ed Australia along with its counterpart written in C++ implementing PPL.

See you in two weeks time at Tech-Ed on the Gold Coast Smile

Best Regards,

Angel

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Runtime.InteropServices;

namespace Test2 {
    class Program {
        [DllImport("kernel32.dll", CallingConvention = CallingConvention.StdCall)]
        private static extern int GetTickCount();


        /// <summary>
        /// Is_carmichaels the specified n.
        /// </summary>
        /// <param name="n">The n.</param>
        /// <returns></returns>
        static bool is_carmichael(int n) {
            if (n < 2) { return false; }

            int k = n;

            for (int i = 2; i <= k / i; ++i) {
                if (k % i == 0) {
                    if ((k / i) % i == 0) { return false; }
                    if ((n - 1) % (i - 1) != 0) { return false; }
                    k /= i;
                    i = 1;
                }
            }
            return k != n && (n - 1) % (k - 1) == 0;
        }

        /// <summary>
        /// Time_calls the specified functor.
        /// </summary>
        /// <param name="functor">The functor.</param>
        /// <returns></returns>
        static int time_call(Action functor) {
            int begin = GetTickCount();
            functor();
            return GetTickCount() - begin;
        }


        /// <summary>
        /// Mains the specified args.
        /// </summary>
        /// <param name="args">The args.</param>
        static void Main(string[] args) {
            int numItems = 10000000;
            int numProcs = Environment.ProcessorCount;

            var vectors = new ConcurrentBag<List<int>>();

            Parallel.For(0, numProcs, (int i) => {
                var v = new List<int>();
                for (int j = numItems / numProcs * i; j < numItems / numProcs * (i + 1); ++j)
                    v.Add(j);
                vectors.Add(v);
            });

            Console.WriteLine("Counting carmichael numbers");

            // Serial
            int sum, sum2, sum3;
            var sums = new List<int>(numProcs);
            var sums2 = new List<int>(numProcs);
            var sums3 = new List<int>(numProcs);

            int serialTime = time_call(() => vectors.ToList().ForEach(x => sums.Add(x.Count(z => is_carmichael(z)))));

            sum = sums.Sum();

            Console.WriteLine(string.Format(" {0} ms, num carmichaels {1}", new object[] { serialTime, sum }));


            // Parallel

            var task1 = Task.Factory.StartNew(() => {
                int parallelTime2 = time_call(() => Parallel.ForEach(vectors, x => sums2.Add(x.Count(z => is_carmichael(z)))));
                sum2 = sums2.AsParallel().Sum();
                Console.WriteLine(string.Format(" {0} ms, num carmichaels {1}", new object[] { parallelTime2, sum2 }));
                var task2 = Task.Factory.StartNew(() => {
                    int parallelTime3 = time_call(() => Parallel.ForEach(vectors, x => sums3.Add(x.Count(z => is_carmichael(z)))));
                    sum3 = sums3.AsParallel().Sum();
                    Console.WriteLine(string.Format(" {0} ms, num carmichaels {1}", new object[] { parallelTime3, sum3 }));
                }, TaskCreationOptions.AttachedToParent);
            });

            task1.Wait();

            Console.ReadKey();
        }
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *