My Project  debian-1:4.1.2-p1+ds-2
misc_ip.h
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file misc_ip.h
5  *
6  * This file provides miscellaneous functionality.
7  *
8  * ABSTRACT: This file provides the following miscellaneous functionality:
9  * - prime factorisation of bigints with prime factors < 2^31
10  * (This will require at most 256 MByte of RAM.)
11  * - approximate square root of a bigint
12  *
13  * Most of the functioanlity implemented here had earlier been
14  * coded in SINGULAR in some library. Due to performance reasons
15  * these algorithms have been moved to the C/C++ kernel.
16  *
17  * @author Frank Seelisch
18  *
19  *
20  **/
21 /*****************************************************************************/
22 
23 #ifndef MISC_H
24 #define MISC_H
25 
26 #include "kernel/mod2.h"
27 
28 #include "coeffs/si_gmp.h"
29 #include "coeffs/coeffs.h"
30 
31 #include "Singular/lists.h"
32 
33 /**
34  * Factorises a given bigint number n into its prime factors less
35  * than or equal to a given bound, with corresponding multiplicities.
36  *
37  * The method finds all prime factors with multiplicities. If a positive
38  * bound is given, then only the prime factors <= pBound are being found.
39  * In this case, there may remain an unfactored portion m of n.
40  * Also, when n is negative, m will contain the sign. If n is zero, m will
41  * be zero.
42  * The method returns a list L filled with three entries:
43  * L[1] a list; L[1][i] contains the i-th prime factor of |n| as int or
44  * bigint (sorted in ascending order),
45  * L[2] a list; L[2][i] contains the multiplicity of L[1, i] in |n| as int
46  * L[3] contains the remainder m as int or bigint, depending on the size,
47  *
48  * We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[3], where
49  * k is the number of mutually distinct prime factors (<= a provided non-
50  * zero bound).
51  * Note that for n = 0, L[1] and L[2] will be emtpy lists and L[3] will be
52  * zero.
53  *
54  * @return the factorisation data in a SINGULAR-internal list
55  **/
57  const number n, /**< [in] the bigint > 0 to be factorised */
58  const int pBound /**< [in] bound on the prime factors
59  seeked */
60  );
61 
62 
63 
64 #ifdef PDEBUG
65 #if (OM_TRACK > 2) && defined(OM_TRACK_CUSTOM)
66 // #include "kernel/polys.h"
67 /* Needed for debug Version of p_SetRingOfLeftv, Oliver */
68 #include "kernel/structs.h"
69 void p_SetRingOfLeftv(leftv l, ring r);
70 #endif
71 #endif
72 
73 #endif
74 /* MISC_H */
primeFactorisation
lists primeFactorisation(const number n, const int pBound)
Factorises a given bigint number n into its prime factors less than or equal to a given bound,...
Definition: misc_ip.cc:367
lists.h
sleftv
Class used for (list of) interpreter objects.
Definition: subexpr.h:81
structs.h
si_gmp.h
mod2.h
slists
Definition: lists.h:22
l
int l
Definition: cfEzgcd.cc:93
coeffs.h