1 | /*****************************************************************************\ |
---|
2 | * Computer Algebra System SINGULAR |
---|
3 | \*****************************************************************************/ |
---|
4 | /** @file misc.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 basic SINGULAR structures |
---|
28 | /* So far nothing is required. */ |
---|
29 | |
---|
30 | /** |
---|
31 | * Computes an approximation of the square root of a bigint number. |
---|
32 | * |
---|
33 | * Expects a non-negative bigint number n and returns the bigint |
---|
34 | * number m which satisfies m*m <= n < (m+1)*(m+1). This implementation |
---|
35 | * does not require a valid currRing. |
---|
36 | * |
---|
37 | * @return an approximation of the square root of n |
---|
38 | **/ |
---|
39 | number approximateSqrt(const number n /**< [in] a number */ |
---|
40 | ); |
---|
41 | |
---|
42 | /** |
---|
43 | * Factorises a given positive bigint number n into its prime factors less |
---|
44 | * than or equal to a given bound, with corresponding multiplicities. |
---|
45 | * |
---|
46 | * The method is capable of finding only prime factors < 2^31, and it looks |
---|
47 | * only for those less than or equal the given bound, if this bound is not 0. |
---|
48 | * Therefore, after dividing out all prime factors which have been found, |
---|
49 | * some number m > 1 may survive. |
---|
50 | * The method returns a list L filled with three entries: |
---|
51 | * L[1] contains m as int or bigint, depending on the size, |
---|
52 | * L[2] a list; L[2][i] contains the i-th prime factor as int |
---|
53 | * (sorted in ascending order), |
---|
54 | * L[3] a list; L[3][i] contains the multiplicity of L[2, i] in n as int |
---|
55 | * |
---|
56 | * We thus have: n = L[1] * L[2][1]^L[3][1] * ... * L[2][k]^L[3][k], where |
---|
57 | * k is the number of mutually distinct prime factors < 2^31 and <= the |
---|
58 | * provided bound (if this is not zero). |
---|
59 | * |
---|
60 | * @return the factorisation data in a list |
---|
61 | **/ |
---|
62 | lists primeFactorisation( |
---|
63 | const number n, /**< [in] the bigint to be factorised */ |
---|
64 | const int pBound /**< [in] bound on the prime factors seeked */ |
---|
65 | ); |
---|
66 | |
---|
67 | #endif |
---|
68 | /* MISC_H */ |
---|