Fast Prime Factoring Algorithm

DrABELL

4.88/5 (22 votes)

3 Jul 2015CPOL4 min read

73.3K

Serial and Parallel implementation of efficient Prime Factoriing algorithms

Fast Prime Factoring Algorithm, described below, enables the factoring of large integers (Int64) and correspondingly, the Primality test of integer numbers.

Demo

The Prime factoring algo has been implemented in a variety of Win/Web applications [1-4]. Below is a sample screenshot of the free online Prime Factoring Calculator [1,2], utilizing server-side computation engine capable of running the primality test of the biggest 18-digit prime number (999999999999999989) within seconds (actual time depends on the traffic to the web server).

Online Prime Factoring Calculator

Fig .1 Online Prime Factoring Calculator, demo screenshot

Prime Factoring Calculator for Windows

The algoritm is also powers Prime Factoring Calculator included in the educaltion package 'Edumatter' for Windows 7/8 (see the demo snapshot below) available at online store [5, 6]:

Fig .2 Prime Factoring Calculator for Windows, demo screenshot

Big Prime samples

Following is a sample list of big (14 ... 18 digits) Prime Numbers useful for testing/evaluation purpose:

biggest 18-digit primes

999999999999999989
999999999999999967
999999999999999877

biggest 17-digit primes

99999999999999997
99999999999999977
99999999999999961

biggest 16-digit primes

9999999999999937
9999999999999917
9999999999999887

biggest 15-digit primes

999999999999989
999999999999947
999999999999883

biggest 14-digit primes

99999999999973
99999999999971
99999999999959

Prime Factoring Algorithms

Following code module (see Listing 1) demonstrates the practical implementation of the algorithm, written in C# (4.0).

Listing 1.

//******************************************************************************
// Author           :   Alexander Bell
// Copyright        :   2007-2015 Infosoft International Inc
// Date Created     :   01/15/2007
// Last Modified    :   02/20/2015
// Description      :   Prime Factoring
//******************************************************************************
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//******************************************************************************
//******************************************************************************
// TERMS OF USE     :   This module is copyrighted.
//                  :   You can use it at your sole risk provided that you keep
//                  :   the original copyright note.
//******************************************************************************
using System;
using System.Collections.Generic;
namespace Infosoft.MathShared
{
    /// <summary>Integers: Properties and Operations</summary>
     public  static partial class Integers
    {
        #region Prime Numbers <100
        private static readonly int[] Primes =
        new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23,
                    29, 31, 37, 41, 43, 47, 53, 59,
                    61, 67, 71, 73, 79, 83, 89, 97 };
        #endregion
         // starting number for iterative factorization
        private const int _startNum = 101;
        #region IsPrime: primality Check
        /// <summary>
        /// Check if the number is Prime
        /// </summary>
        /// <param name="Num">Int64</param>
        /// <returns>bool</returns>
        public static bool IsPrime(Int64 Num){
            int j;
            bool ret;
            Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1; ;
            // Check if number is in Prime Array
            for (int i = 0; i < Primes.Length; i++){
                if (Num == Primes[i]) { return true; }
            }
            // Check divisibility w/Prime Array
            for (int i = 0; i < Primes.Length; i++) {
                if (Num % Primes[i] == 0) return false;
            }
            // Main iteration for Primality check
            _upMargin = (Int64)Math.Sqrt(Num) + 1;
            j = _startNum;
            ret = true;
            while (j <= _upMargin)
            {
                if (Num % j == 0) { ret = false; break; }
                else { j=j+2; }
            }
            return ret;
        }
        /// <summary>
        /// Check if number-string is Prime
        /// </summary>
        /// <param name="Num">string</param>
        /// <returns>bool</returns>
        public static bool IsPrime(string StringNum) {
            return IsPrime(Int64.Parse(StringNum));
        }
        #endregion
        #region Fast Factorization
        /// <summary>
        /// Factorize string converted to long integers
        /// </summary>
        /// <param name="StringNum">string</param>
        /// <returns>Int64[]</returns>
        public static Int64[] FactorizeFast(string StringNum) {
            return FactorizeFast(Int64.Parse(StringNum));
        }
        /// <summary>
        /// Factorize long integers: speed optimized
        /// </summary>
        /// <param name="Num">Int64</param>
        /// <returns>Int64[]</returns>
        public static Int64[] FactorizeFast(Int64 Num)
        {
            #region vars
            // list of Factors
            List<Int64> _arrFactors = new List<Int64>();
            // temp variable
            Int64 _num = Num;
            #endregion
            #region Check if the number is Prime (<100)
            for (int k = 0; k < Primes.Length; k++)
            {
                if (_num == Primes[k])
                {
                    _arrFactors.Add(Primes[k]);
                    return _arrFactors.ToArray();
                }
            }
            #endregion
            #region Try to factorize using Primes Array
            for (int k = 0; k < Primes.Length; k++)
            {
                int m = Primes[k];
                if (_num < m) break;
                while (_num % m == 0)
                {
                    _arrFactors.Add(m);
                    _num = (Int64)_num / m;
                }
            }
            if (_num < _startNum)
            {
                _arrFactors.Sort();
                return _arrFactors.ToArray();
            }
            #endregion
            #region Main Factorization Algorithm
            Int64 _upMargin = (Int64)Math.Sqrt(_num) + 1;
            Int64 i = _startNum;
            while (i <= _upMargin)
            {
                if (_num % i == 0)
                {
                    _arrFactors.Add(i);
                    _num = _num / i;
                    _upMargin = (Int64)Math.Sqrt(_num) + 1;
                    i = _startNum;
                }
                else { i=i+2; }
            }
            _arrFactors.Add(_num);
            _arrFactors.Sort();
            return _arrFactors.ToArray();
            #endregion
        }
        #endregion
    }
}
//******************************************************************************

Parallel Algoritm for Primality test

Significant performance boost can be obtained by implementing a parallel algoritm as shown in the code snippet below:

Listing 3. Parallel algorithm for primality test.

#region GetFirstFactorParallel(Int64 Num) algorithm
/// <summary>
/// ===================================================================
/// Copyright(C)2012-2015 Alexander Bell
/// ===================================================================
/// parallel algorithm accepts Int64 Num 
/// and returns either first found not-trivial factor, or number 1.
/// This algo provides performance boost 
/// in comparison to serial implementation on prime factoring of
/// big prime numbers
/// </summary>
/// <param name="Num">Int64</param>
/// <returns>Int64</returns>
internal static Int64 GetFirstFactorParallel(Int64 Num)
{
    // use concurrent stack to store non-trivial factor if found
    ConcurrentStack<Int64> _stack = new ConcurrentStack<Int64>();
            
    // object to specify degrees of parallelism
    ParallelOptions _po = new ParallelOptions();

    try
    {
        // return value initially set to 1
        Int64 _ret = 1;

        // step 1: try to factor on base 2, return if OK
        if (Num % 2 == 0) return 2;

        // step 2: try to factor on base 3, return if OK
        if (Num % 3 == 0) return 3;

        #region parallel algo to find first non-trivial factor if exists

        // set upper limit
        Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1;

        // number of CPU cores
        int _countCPU = System.Environment.ProcessorCount;

        // max degree of parallelism set equal to _cpuCount
        _po.MaxDegreeOfParallelism = _countCPU;

        Parallel.For(0, 2, _po, (i, _plState) =>
        {
            // starting number for inner loops (5 and 7)
            int _seed = 5 + 2 * i;

            // inner loops running in parallel;
            // notice that because input Num was already tested for factors 2 and 3,
            // then increment of 6 is used to speed up the processing,
            // thus in dual core CPU it looks like:
            // 5, 11, 17, 23, 29, etc. in first thread
            // 7, 13, 19, 25, 31, etc, in second thread
            for (Int64 j = _seed; j < _upMargin; j += 6)
            {
                // exit loop if stack contains value
                if (_stack.Count != 0) { break; }

                // check divisibility
                if (Num % j == 0)
                {
                    // push non-trivial factor to ConcurrentStack and exit loop
                    if (_stack.Count == 0) { _stack.Push(j); }
                    break;
                }
            }
        });
        #endregion

        // return the value in ConcurrentStack if exists, or 1
        return (_stack.TryPop(out _ret)) ? _ret : 1;
    }
    catch { throw; }
    finally { _po = null; _stack = null; }

}
#endregion

Notice that because input Num was already tested for factors 2 and 3, two inner loops running in parallel mode are increment by 6 to speed up the processing, thus in dual core CPU it looks like:
5, 11, 17, 23, 29, etc. in first thread
7, 13, 19, 25, 31, etc, in second thread.

Points of Interest

Loop counter increment technique

Note 1: Primality test (i.e. procedure intended to identify if the integer is a prime number) of the biggest 18-digit prime number (999999999999999989) is a good performance benchmark for any prime factoring application software. If the computation takes too long (it might be a case if using mobile platform with relatively low "number crunching" power), then try the smaller number (also 18 digits prime integer): 324632623645234523.

Note 2: in the original code the increment by 2 was implemented as the following (expected to give some performance addvantages over the trivial i=i+2, or i+=2)

i++; i++;

Special kudos to our members AspDotNetDev and irneb, who did a thorough performance evaluation of these various incremental techniques, and also inspired me to further analyze this issue (even though the practical differences could be rather small in comparison with other computational task's complexity/execution time). The following code snippet has been used for performance comparison of three aforementioned integer incremental techniques:

Listing 2. Performance test of 3 different integer incremental techniques

//******************************************************************************
// Module           :   Performance test of 3 integer incremental techniques
// Author           :   Alexander Bell
// Date Created     :   02/20/2015
//******************************************************************************
// DISCLAIMER: This module is provide on AS IS basis without any warranty
//******************************************************************************
using System;
using System.Diagnostics;

namespace IncrementEfficiencyTest
{
    class Program
    {
        private const Int64 _max = 1000000000; // 1 billion
        private const int _cycles = 5;

        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();

            // i++ (AVR: 11.907) ***************************************************************************
            Console.Write("{0} on {1}", "i++;i++:", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max) { i++; i++; }
            }
               sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            // i=i+2 (AVR: 5.589) _FASTEST **************************************************************
            Console.Write("{0} on {1}", "i=i+2", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max) { i = i + 2; }
            }
            sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            // i+=2 (AVR: 5.624 ) | *********************************************************************
            Console.Write("{0} on {1}", "i+=2", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max)  { i += 2;}
            }
            sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            Console.ReadKey();
        }
    }
}

The test is using the same Stopwatch object as in the sample code provided by irneb. However, in order to minimize any potential side effects, it does not implement any function calls (which may distort the timing estimates), and is running in multiple cycles (5 cycles) with subsequent averaging of several test results. Based on the statistical outcome, the fastest way to increment the Int64 integer by 2 was found to be a plain straight: i = i+2 (5.589 sec for entire test routine), closely followed by i += 2 (5.625 sec) and the double i++;i++; "leading from behind" with 11.907 sec performance estimate. Corresponding correction has been made to the original prime-factoring algo (it shows now i = i+2).

Significant performance improvement can be achieved by implementing the parallel prime factoring algorithm, described in the Codeproject article: Edumatter-814: School Math Calculators and Equation Solvers [5].

Multi-core CPU

Parallel implementation of the Prime factoring algo leads to significant performance boost in case of using multi-core CPU. It is not recommended for a single-core PC, where the actual performance may degrade due to the thread-synchrinization overhead vs ordinary serial implementation.

Acknowledgement

I would like to thank our members AspDotNetDev and especially irneb for taking time and efforts running the performance evaluation test on different integer incremental techniques (please refer to their rather thoughtfull comments, which include interesting performance test results).

History

3/2/2015: Sample Parallel implementation of prime factoring algorithm added

References

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)