My Project
Loading...
Searching...
No Matches
misc_ip.h
Go to the documentation of this file.
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 "kernel/mod2.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 **/
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 */
int l
Definition: cfEzgcd.cc:100
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
Definition: lists.h:24
Coefficient rings, fields and other domains suitable for Singular polynomials.
lists primeFactorisation(const number n, const int pBound)
Factorises a given bigint number n into its prime factors less than or equal to a given bound,...
Definition: misc_ip.cc:357