root/core/factoring.hpp

/* [<][>][^][v][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. division
  2. monte_carlo

   1 #ifndef LIBJMMCG_CORE_FACTORING_HPP
   2 #define LIBJMMCG_CORE_FACTORING_HPP
   3 
   4 /******************************************************************************
   5 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/hp_timer.hpp 1970 2016-11-13 21:48:21Z jmmcg $
   6 **
   7 ** Copyright (c) 1993 by J.M.McGuiness, coder@hussar.me.uk
   8 **
   9 ** This library is free software; you can redistribute it and/or
  10 ** modify it under the terms of the GNU Lesser General Public
  11 ** License as published by the Free Software Foundation; either
  12 ** version 2.1 of the License, or (at your option) any later version.
  13 **
  14 ** This library is distributed in the hope that it will be useful,
  15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 ** Lesser General Public License for more details.
  18 **
  19 ** You should have received a copy of the GNU Lesser General Public
  20 ** License along with this library; if not, write to the Free Software
  21 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  22 */
  23 
  24 #include "gcd.hpp"
  25 #include "blatant_old_msvc_compiler_hacks.hpp"
  26 
  27 #include <set>
  28 #include <vector>
  29 
  30 namespace jmmcg { namespace factoring {
  31 
  32 using collection_type=std::vector<unsigned long>;
  33 
  34 /// Factoring by division.
  35 /**
  36  * \param       x       The number to be factored. Must be greater than zero.
  37  * \return      The array that has the factors placed in it.
  38  * 
  39  * Thanks to Knuth, et al for this routine. See his book "Seminumerical Algorithms. Vol 2".
  40  * 
  41  * \see factoring::monte_carlo()
  42  */
  43 inline collection_type __fastcall
  44 division(const collection_type::value_type x) noexcept(false) {
  45         assert(x>collection_type::value_type{});
  46         std::set<collection_type::value_type> factors;
  47         collection_type::value_type count=1lu, tst_divs=2lu, n=x;
  48         while (n!=1) {
  49                 if (n%tst_divs) {
  50                         if (n>1) {
  51                                 if (count==1) {
  52                                         ++tst_divs;
  53                                         ++count;
  54                                 } else if (count<3) {
  55                                         tst_divs+=2;
  56                                         ++count;
  57                                 } else {
  58                                         count++&1 ? (tst_divs+=2) : (tst_divs+=4);
  59                                         if ((count>8) && (!(tst_divs%5) || !(tst_divs%7))) {
  60                                                 count++&1 ? (tst_divs+=2) : (tst_divs+=4);
  61                                         }
  62                                 }
  63                         } else {
  64                                 factors.insert(n);
  65                                 return collection_type{factors.begin(), factors.end()};
  66                         }
  67                 } else {
  68                         factors.insert(tst_divs);
  69                         n/=tst_divs;
  70                 }
  71         }
  72         return collection_type{factors.begin(), factors.end()};
  73 }
  74 
  75 /// Monte Carlo factorisation.
  76 /**
  77  * \todo FIXME
  78  * 
  79  * \param       y       The number to be factored.
  80  * \return      The array that has the factors placed in it.
  81  * 
  82  * Thanks to Knuth, et al for this routine. See his book "Seminumerical Algorithms. Vol 2".
  83  * 
  84  * \see factoring::division()
  85  */
  86 inline collection_type __fastcall
  87 monte_carlo(const collection_type::value_type y) noexcept(false) {
  88         collection_type factors;
  89         collection_type::value_type x=5, x_=2, k=1, l=1, n=y, g;
  90 b2:
  91         if (n&1) {
  92                 factors.emplace_back(n);
  93                 return factors;
  94         }
  95 b3:
  96         if ((g=euclid::gcd((x_-x),n))==1) {
  97                 goto b4;
  98         } else if ((g=n)!=0) {
  99                 return factors;
 100         } else {
 101                 n/=g;
 102                 x%=n;
 103                 x_%=n;
 104                 goto b2;
 105         }
 106 b4:
 107         if (!--k) {
 108                 x_=x;
 109                 l<<=1;
 110                 k=l;
 111         }
 112         x=(x*x+1)%n;
 113         goto b3;
 114 }
 115 
 116 } }
 117 
 118 #endif

/* [<][>][^][v][top][bottom][index][help] */