Loading...
Searching...
No Matches
misc_ip.h File Reference

This file provides miscellaneous functionality. More...

`#include "kernel/mod2.h"`
`#include "coeffs/si_gmp.h"`
`#include "coeffs/coeffs.h"`
`#include "Singular/lists.h"`

Go to the source code of this file.

## Functions

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, with corresponding multiplicities.

## Detailed Description

This file provides miscellaneous functionality.

ABSTRACT: This file provides the following miscellaneous functionality:

- prime factorisation of bigints with prime factors < 2^31 (This will require at most 256 MByte of RAM.)
- approximate square root of a bigint

Most of the functioanlity implemented here had earlier been coded in SINGULAR in some library. Due to performance reasons these algorithms have been moved to the C/C++ kernel.

Author
  Frank Seelisch

Definition in file misc_ip.h.

## Function Documentation

## primeFactorisation()

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, with corresponding multiplicities.

The method finds all prime factors with multiplicities. If a positive bound is given, then only the prime factors <= pBound are being found. In this case, there may remain an unfactored portion m of n. Also, when n is negative, m will contain the sign. If n is zero, m will be zero. The method returns a list L filled with three entries: L[1] a list; L[1][i] contains the i-th prime factor of |n| as int or bigint (sorted in ascending order), L[2] a list; L[2][i] contains the multiplicity of L[1, i] in |n| as int L[3] contains the remainder m as int or bigint, depending on the size,

We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[3], where k is the number of mutually distinct prime factors (<= a provided non- zero bound). Note that for n = 0, L[1] and L[2] will be empty lists and L[3] will be zero.

Returns
  the factorisation data in a SINGULAR-internal list

Parameters

  [in] | n | the bigint > 0 to be factorised
  [in] | pBound | bound on the prime factors seeked

Definition at line 358 of file misc_ip.cc.

{
int i;
int index=0;
mpz_t nn; number2mpz(n, coeffs_BIGINT, nn);
lists primes = (lists)omAllocBin(slists_bin); primes->Init(1000);
int* multiplicities = (int*)omAlloc0(1000*sizeof(int));
int positive=1;
if (!n_IsZero(n, coeffs_BIGINT))
{
if (!n_GreaterZero(n, coeffs_BIGINT))
{
positive=-1;
mpz_neg(nn,nn);
}
factor_gmp(nn,primes,multiplicities,index,pBound);
}
lists primesL = (lists)omAllocBin(slists_bin);
primesL->Init(index);
for (i = 0; i < index; i++)
{
primesL->m[i].rtyp = primes->m[i].rtyp;
primesL->m[i].data = primes->m[i].data;
primes->m[i].rtyp=0;
primes->m[i].data=NULL;
}
primes->Clean(NULL);
lists multiplicitiesL = (lists)omAllocBin(slists_bin);
multiplicitiesL->Init(index);
for (i = 0; i < index; i++)
{
multiplicitiesL->m[i].rtyp = INT_CMD;
multiplicitiesL->m[i].data = (void*)(long)multiplicities[i];
}
omFree(multiplicities);
lists L=(lists)omAllocBin(slists_bin);
L->Init(3);
if (positive==-1) mpz_neg(nn,nn);
L->m[0].rtyp = LIST_CMD; L->m[0].data = (void*)primesL;
L->m[1].rtyp = LIST_CMD; L->m[1].data = (void*)multiplicitiesL;
setListEntry(L, 2, nn);
mpz_clear(nn);
return L;
}
i
int i
Definition cfEzgcd.cc:132
sleftv::rtyp
int rtyp
Definition subexpr.h:91
sleftv::data
void * data
Definition subexpr.h:88
slists::m
sleftv * m
Definition lists.h:46
slists::Init
INLINE_THIS void Init(int l=0)
number2mpz
static FORCE_INLINE void number2mpz(number n, coeffs c, mpz_t m)
Definition coeffs.h:990
n_GreaterZero
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff 'n' is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2),...
Definition coeffs.h:500
n_IsZero
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff 'n' represents the zero element.
Definition coeffs.h:470
primes
STATIC_VAR unsigned short primes[]
primes, primes_len: used to step through possible extensions
Definition gengftables-conway.cc:60
slists_bin
VAR omBin slists_bin
Definition lists.cc:23
factor_gmp
static void factor_gmp(mpz_t t, lists primes, int *multiplicities, int &index, unsigned long bound)
Definition misc_ip.cc:328
setListEntry
void setListEntry(lists L, int index, mpz_t n)
Definition misc_ip.cc:75
lists
slists * lists
Definition mpr_numeric.h:146
omAllocBin
#define omAllocBin(bin)
Definition omAllocDecl.h:205
omFree
#define omFree(addr)
Definition omAllocDecl.h:261
omAlloc0
#define omAlloc0(size)
Definition omAllocDecl.h:211
NULL
#define NULL
Definition omList.c:12
index
static int index(p_Length length, p_Ord ord)
Definition p_Procs_Impl.h:592
coeffs_BIGINT
VAR coeffs coeffs_BIGINT
Definition polys.cc:14
LIST_CMD
@ LIST_CMD
Definition tok.h:118
INT_CMD
@ INT_CMD
Definition tok.h:96