source: git/Singular/misc_ip.h @ e5db0a

spielwiese
Last change on this file since e5db0a was e5db0a, checked in by Frank Seelisch <seelisch@…>, 14 years ago
extra command "GNUmpLoad" to load bigint from file with digits to the base 10 git-svn-id: file:///usr/local/Singular/svn/trunk@13155 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 3.3 KB
Line 
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 **/
36void 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 **/
45number 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 **/
55void 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 **/
80lists 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 */
Note: See TracBrowser for help on using the repository browser.