ITVDN logo
Видеокурсы по
программированию

Доступ более чем к 7700 видеоурокам от $19.99

Подписка
ITVDN logo
Видеокурсы по
программированию

Доступ более чем к 7700 видеоурокам от $19.99

Подписка

Введение

Факторизация целых чисел позволяет раскладывать на множители (факторинг) большие числа (Int64) и проверять простоту целых чисел [1,2].


Приведем пример больших (14 ... 18-ти значных) простых чисел, которые можно использовать для тестирования или оценки.

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

Кодовый модуль демонстрирует практическое использование алгоритма, написанного в C# (4.0).

using System;

using System.Collections.Generic;

namespace Infosoft.MathShared

{

       ///

Integers: Properties and Operations

       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

             ///

             /// Check if the number is Prime

             ///

             /// Int64

             /// bool

             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;

             }

             ///

             /// Check if number-string is Prime

             ///

             /// string

             /// bool

             public static bool IsPrime(string StringNum) {

                    return IsPrime(Int64.Parse(StringNum));

             }

#endregion

#region Fast Factorization

             ///

             /// Factorize string converted to long integers

             ///

             /// string

             /// Int64[]

             public static Int64[] FactorizeFast(string StringNum) {

                    return FactorizeFast(Int64.Parse(StringNum));

             }

             ///

             /// Factorize long integers: speed optimized

             ///

             /// Int64

             /// Int64[]

             public static Int64[] FactorizeFast(Int64 Num)

             {

#region vars

                    // list of Factors

                    List _arrFactors = new List();

                    // 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

       }

}

Точки обзора

Тест на проверку простоты 18-ти значного числа (999999999999999989), т.е. процедура, которая определяет, являются ли целые числа простыми, это лучший способ проверки факторинга программного обеспечения. Если вычисления занимают слишком много времени (например, когда используется мобильная платформа с низким уровнем обработки большого количества численных данных), возьмите меньшее число, но тоже 18-ти значное: 324632623645234523.

Чтобы получить не такую тривиальную запись, как i = i + 2, или i + = 2, необходимо исходный код увеличить в два раза.

i ++; i ++;

Даный фрагмент кода был использован для сравнения производительности трех методов возрастания целых чисел: 

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();

                    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);

                    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);

                    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();

             }

       }

Чтобы минимизировать потенциальные побочные эффекты теста, следует работать в нескольких циклах (5 циклов) с последующей апроксимацией нескольких результатов тестирования и не нужно реализовывать вызовы функций , потому что оценка синхронизации может искажаться. Основываясь на статистических данных, самый быстрый способ увеличения числа Int64 в 2 раза можно достичь через составленное уравнение: i = i + 2 (5,589 сек для всей процедуры тестирования), вместе с i + = 2 (5,625 сек) и удвоением и ++; i ++;  "leading from behind" с оценкой производительности в 11,907 сек. Соответствующая поправка была сделана в факторизации первичных чисел (теперь выводится i = i + 2).

Параллельный алгоритм для факторинг-теста

При использовании параллельных алгоритмов факторизации можно значительно увеличить производительность теста.

Параллельне алгоритмы факторизации

region GetFirstFactorParallel(Int64 Num) algorithm

internal static Int64 GetFirstFactorParallel(Int64 Num)

{

       // use concurrent stack to store non-trivial factor if found

       ConcurrentStack _stack = new ConcurrentStack();

       // 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

Источник: http://www.codeproject.com/Tips/155308/Fast-Prime-Factoring-Algorithm

СТАТЬИ ПО СХОЖЕЙ ТЕМАТИКЕ
ВИДЕО КУРСЫ ПО СХОЖЕЙ ТЕМАТИКЕ

КОМЕНТАРИИ И ОБСУЖДЕНИЯ

ОЦЕНИТЕ ДАННЫЙ МАТЕРИАЛ

ПОДПИСКА НА ITVDN ВЫГОДА ДО 29.95$ НА ОБУЧЕНИЕ ПРЕСТИЖНЫМ ПРОФЕССИЯМ!

1 месяц19.99$
подписка

легкий старт в обучении

3 месяца49.99$
подписка

выгода от подписки до9.98$

6 месяцев89.99$
подписка

выгода от подписки до29.95$