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 <kernel/structs.h> |
---|
28 | |
---|
29 | // include basic SINGULAR structures |
---|
30 | /* So far nothing is required. */ |
---|
31 | |
---|
32 | /** |
---|
33 | * Converts a non-negative bigint number into a GMP number. |
---|
34 | * |
---|
35 | **/ |
---|
36 | void number2mpz(number n, /**< [in] a bigint number >= 0 */ |
---|
37 | mpz_t m /**< [out] the GMP equivalent */ |
---|
38 | ); |
---|
39 | |
---|
40 | /** |
---|
41 | * Converts a non-negative GMP number into a bigint number. |
---|
42 | * |
---|
43 | * @return the bigint number representing the given GMP number |
---|
44 | **/ |
---|
45 | number mpz2number(mpz_t m /**< [in] a GMP number >= 0 */ |
---|
46 | ); |
---|
47 | |
---|
48 | /** |
---|
49 | * Divides 'n' as many times as possible by 'd' and returns the number |
---|
50 | * of divisions (without remainder) in 'times', |
---|
51 | * e.g., n = 48, d = 4, divTimes(n, d, t) = 3 produces n = 3, t = 2, |
---|
52 | * since 48 = 4*4*3; |
---|
53 | * assumes that d is positive |
---|
54 | **/ |
---|
55 | void divTimes(mpz_t n, /**< [in] a GMP number >= 0 */ |
---|
56 | mpz_t d, /**< [in] the divisor, a GMP number >= 0 */ |
---|
57 | int* times /**< [out] number of divisions without remainder */ |
---|
58 | ); |
---|
59 | |
---|
60 | /** |
---|
61 | * Factorises a given positive bigint number n into its prime factors less |
---|
62 | * than or equal to a given bound, with corresponding multiplicities. |
---|
63 | * |
---|
64 | * The method finds all prime factors with multiplicities. If a non-zero |
---|
65 | * bound is given, then only the prime factors <= pBound are being found. |
---|
66 | * In this case, there may remain an unfactored portion m of n. |
---|
67 | * The method returns a list L filled with four entries: |
---|
68 | * L[1] contains the remainder m as int or bigint, depending on the size, |
---|
69 | * L[2] a list; L[2][i] contains the i-th prime factor as int or bigint |
---|
70 | * (sorted in ascending order), |
---|
71 | * L[3] a list; L[3][i] contains the multiplicity of L[2, i] in n as int |
---|
72 | * L[4] 1 iff the remainder m is probably a prime, 0 otherwise |
---|
73 | * |
---|
74 | * We thus have: n = L[1] * L[2][1]^L[3][1] * ... * L[2][k]^L[3][k], where |
---|
75 | * k is the number of mutually distinct prime factors (<= a provided non- |
---|
76 | * zero bound). |
---|
77 | * |
---|
78 | * @return the factorisation data in a SINGULAR-internal list |
---|
79 | **/ |
---|
80 | lists primeFactorisation( |
---|
81 | const number n, /**< [in] the bigint > 0 to be factorised */ |
---|
82 | const number pBound /**< [in] bigint bound on the prime factors |
---|
83 | seeked */ |
---|
84 | ); |
---|
85 | |
---|
86 | #endif |
---|
87 | /* MISC_H */ |
---|