[86b2ec4] | 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/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 | /** |
---|
[8acd267] | 62 | * Factorises a given bigint number n into its prime factors less |
---|
[86b2ec4] | 63 | * than or equal to a given bound, with corresponding multiplicities. |
---|
| 64 | * |
---|
[8acd267] | 65 | * The method finds all prime factors with multiplicities. If a positive |
---|
[86b2ec4] | 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. |
---|
[8acd267] | 68 | * Also, when n is negative, m will contain the sign. If n is zero, m will |
---|
| 69 | * be zero. |
---|
[86b2ec4] | 70 | * The method returns a list L filled with four entries: |
---|
[8acd267] | 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 |
---|
[86b2ec4] | 76 | * |
---|
[8acd267] | 77 | * We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[1], where |
---|
[86b2ec4] | 78 | * k is the number of mutually distinct prime factors (<= a provided non- |
---|
| 79 | * zero bound). |
---|
[8acd267] | 80 | * Note that for n = 0, L[2] and L[3] will be emtpy lists and L[4] will be |
---|
| 81 | * zero. |
---|
[86b2ec4] | 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 | #endif |
---|
| 92 | /* MISC_H */ |
---|