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 | * @internal @version \$Id$ |
---|
20 | * |
---|
21 | **/ |
---|
22 | /*****************************************************************************/ |
---|
23 | |
---|
24 | #ifndef MISC_H |
---|
25 | #define MISC_H |
---|
26 | |
---|
27 | #include <coeffs/si_gmp.h> |
---|
28 | #include <kernel/structs.h> |
---|
29 | |
---|
30 | // include basic SINGULAR structures |
---|
31 | /* So far nothing is required. */ |
---|
32 | |
---|
33 | /** |
---|
34 | * Converts a non-negative bigint number into a GMP number. |
---|
35 | * |
---|
36 | **/ |
---|
37 | void number2mpz(number n, /**< [in] a bigint number >= 0 */ |
---|
38 | mpz_t m /**< [out] the GMP equivalent */ |
---|
39 | ); |
---|
40 | |
---|
41 | /** |
---|
42 | * Converts a non-negative GMP number into a bigint number. |
---|
43 | * |
---|
44 | * @return the bigint number representing the given GMP number |
---|
45 | **/ |
---|
46 | number mpz2number(mpz_t m /**< [in] a GMP number >= 0 */ |
---|
47 | ); |
---|
48 | |
---|
49 | /** |
---|
50 | * Divides 'n' as many times as possible by 'd' and returns the number |
---|
51 | * of divisions (without remainder) in 'times', |
---|
52 | * e.g., n = 48, d = 4, divTimes(n, d, t) = 3 produces n = 3, t = 2, |
---|
53 | * since 48 = 4*4*3; |
---|
54 | * assumes that d is positive |
---|
55 | **/ |
---|
56 | void divTimes(mpz_t n, /**< [in] a GMP number >= 0 */ |
---|
57 | mpz_t d, /**< [in] the divisor, a GMP number >= 0 */ |
---|
58 | int* times /**< [out] number of divisions without remainder */ |
---|
59 | ); |
---|
60 | |
---|
61 | /** |
---|
62 | * Factorises a given bigint number n into its prime factors less |
---|
63 | * than or equal to a given bound, with corresponding multiplicities. |
---|
64 | * |
---|
65 | * The method finds all prime factors with multiplicities. If a positive |
---|
66 | * bound is given, then only the prime factors <= pBound are being found. |
---|
67 | * In this case, there may remain an unfactored portion m of n. |
---|
68 | * Also, when n is negative, m will contain the sign. If n is zero, m will |
---|
69 | * be zero. |
---|
70 | * The method returns a list L filled with four entries: |
---|
71 | * L[1] a list; L[1][i] contains the i-th prime factor of |n| as int or |
---|
72 | * bigint (sorted in ascending order), |
---|
73 | * L[2] a list; L[2][i] contains the multiplicity of L[1, i] in |n| as int |
---|
74 | * L[3] contains the remainder m as int or bigint, depending on the size, |
---|
75 | * L[4] 1 iff |m| is probably a prime, 0 otherwise |
---|
76 | * |
---|
77 | * We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[1], where |
---|
78 | * k is the number of mutually distinct prime factors (<= a provided non- |
---|
79 | * zero bound). |
---|
80 | * Note that for n = 0, L[2] and L[3] will be emtpy lists and L[4] will be |
---|
81 | * zero. |
---|
82 | * |
---|
83 | * @return the factorisation data in a SINGULAR-internal list |
---|
84 | **/ |
---|
85 | lists primeFactorisation( |
---|
86 | const number n, /**< [in] the bigint > 0 to be factorised */ |
---|
87 | const number pBound /**< [in] bigint bound on the prime factors |
---|
88 | seeked */ |
---|
89 | ); |
---|
90 | |
---|
91 | |
---|
92 | |
---|
93 | #ifdef PDEBUG |
---|
94 | #if (OM_TRACK > 2) && defined(OM_TRACK_CUSTOM) |
---|
95 | // #include <polys/polys.h> |
---|
96 | /* Needed for debug Version of p_SetRingOfLeftv, Oliver */ |
---|
97 | void p_SetRingOfLeftv(leftv l, ring r); |
---|
98 | #endif |
---|
99 | #endif |
---|
100 | |
---|
101 | #endif |
---|
102 | /* MISC_H */ |
---|