source: git/Singular/misc_ip.h @ dcd92d

spielwiese
Last change on this file since dcd92d was 65b813, checked in by Hans Schoenemann <hannes@…>, 11 years ago
fix: primefactors(): result and algorithm, bound enabled again Conflicts: Singular/ChangeLog Singular/iparith.cc
  • Property mode set to 100644
File size: 2.6 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 *
20 **/
21/*****************************************************************************/
22
23#ifndef MISC_H
24#define MISC_H
25
26#include <misc/auxiliary.h>
27
28#include <coeffs/si_gmp.h>
29#include <coeffs/coeffs.h>
30
31#include <Singular/lists.h>
32
33/**
34 * Factorises a given bigint number n into its prime factors less
35 * than or equal to a given bound, with corresponding multiplicities.
36 *
37 * The method finds all prime factors with multiplicities. If a positive
38 * bound is given, then only the prime factors <= pBound are being found.
39 * In this case, there may remain an unfactored portion m of n.
40 * Also, when n is negative, m will contain the sign. If n is zero, m will
41 * be zero.
42 * The method returns a list L filled with three entries:
43 * L[1] a list; L[1][i] contains the i-th prime factor of |n| as int or
44 *                      bigint (sorted in ascending order),
45 * L[2] a list; L[2][i] contains the multiplicity of L[1, i] in |n| as int
46 * L[3] contains the remainder m as int or bigint, depending on the size,
47 *
48 * We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[3], where
49 * k is the number of mutually distinct prime factors (<= a provided non-
50 * zero bound).
51 * Note that for n = 0, L[1] and L[2] will be emtpy lists and L[3] will be
52 * zero.
53 *
54 * @return the factorisation data in a SINGULAR-internal list
55 **/
56lists primeFactorisation(
57       const number n,     /**< [in]  the bigint > 0 to be factorised   */
58       const int pBound    /**< [in]  bound on the prime factors
59                                      seeked                            */
60                        );
61
62
63
64#ifdef PDEBUG
65#if (OM_TRACK > 2) && defined(OM_TRACK_CUSTOM)
66// #include <kernel/polys.h>
67/* Needed for debug Version of p_SetRingOfLeftv, Oliver */
68#include <kernel/structs.h>
69void p_SetRingOfLeftv(leftv l, ring r);
70#endif
71#endif
72
73#endif
74/* MISC_H */
Note: See TracBrowser for help on using the repository browser.