source: git/Singular/misc_ip.h @ c45b8f0

spielwiese
Last change on this file since c45b8f0 was 8acd267, checked in by Frank Seelisch <seelisch@…>, 14 years ago
re-established old ordering in result list of command 'primefactors' (kernel code, LIB code, docu) git-svn-id: file:///usr/local/Singular/svn/trunk@13321 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 3.4 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/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 **/
37void 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 **/
46number 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 **/
56void 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 **/
85lists 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 */
Note: See TracBrowser for help on using the repository browser.