Functions
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. More...
 

Detailed Description

This file provides miscellaneous functionality.

ABSTRACT: This file provides the following miscellaneous functionality:

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 emtpy lists and L[3] will be zero.

Returns
the factorisation data in a SINGULAR-internal list
Parameters
[in]nthe bigint > 0 to be factorised
[in]pBoundbound on the prime factors seeked

Definition at line 333 of file misc_ip.cc.

334 {
335  int i;
336  int index=0;
337  mpz_t nn; number2mpz(n, nn);
338  lists primes = (lists)omAllocBin(slists_bin); primes->Init(1000);
339  int* multiplicities = (int*)omAlloc0(1000*sizeof(int));
340  int positive=1;
341 
342  if (!n_IsZero(n, coeffs_BIGINT))
343  {
344  if (!n_GreaterZero(n, coeffs_BIGINT))
345  {
346  positive=-1;
347  mpz_neg(nn,nn);
348  }
349  factor_gmp(nn,primes,multiplicities,index,pBound);
350  }
351 
352  lists primesL = (lists)omAllocBin(slists_bin);
353  primesL->Init(index);
354  for (i = 0; i < index; i++)
355  {
356  primesL->m[i].rtyp = primes->m[i].rtyp;
357  primesL->m[i].data = primes->m[i].data;
358  primes->m[i].rtyp=0;
359  primes->m[i].data=NULL;
360  }
361  primes->Clean(NULL);
362 
363  lists multiplicitiesL = (lists)omAllocBin(slists_bin);
364  multiplicitiesL->Init(index);
365  for (i = 0; i < index; i++)
366  {
367  multiplicitiesL->m[i].rtyp = INT_CMD;
368  multiplicitiesL->m[i].data = (void*)(long)multiplicities[i];
369  }
370  omFree(multiplicities);
371 
373  L->Init(3);
374  if (positive==-1) mpz_neg(nn,nn);
375  L->m[0].rtyp = LIST_CMD; L->m[0].data = (void*)primesL;
376  L->m[1].rtyp = LIST_CMD; L->m[1].data = (void*)multiplicitiesL;
377  setListEntry(L, 2, nn);
378 
379  mpz_clear(nn);
380 
381  return L;
382 }
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
static void factor_gmp(mpz_t t, lists primes, int *multiplicities, int &index, unsigned long bound)
Definition: misc_ip.cc:303
sleftv * m
Definition: lists.h:45
static FORCE_INLINE void number2mpz(number n, mpz_t m)
Definition: misc_ip.cc:46
Definition: tok.h:95
Definition: lists.h:22
void setListEntry(lists L, int index, mpz_t n)
Definition: misc_ip.cc:50
static unsigned short primes[]
primes, primes_len: used to step through possible extensions
coeffs coeffs_BIGINT
Definition: ipid.cc:54
void * data
Definition: subexpr.h:88
#define omFree(addr)
Definition: omAllocDecl.h:261
int i
Definition: cfEzgcd.cc:123
static FORCE_INLINE BOOLEAN n_IsZero(number n, const coeffs r)
TRUE iff &#39;n&#39; represents the zero element.
Definition: coeffs.h:468
static int index(p_Length length, p_Ord ord)
Definition: p_Procs_Impl.h:592
INLINE_THIS void Init(int l=0)
#define NULL
Definition: omList.c:10
slists * lists
Definition: mpr_numeric.h:146
int rtyp
Definition: subexpr.h:91
void Clean(ring r=currRing)
Definition: lists.h:25
Definition: tok.h:117
omBin slists_bin
Definition: lists.cc:23
static FORCE_INLINE BOOLEAN n_GreaterZero(number n, const coeffs r)
ordered fields: TRUE iff &#39;n&#39; is positive; in Z/pZ: TRUE iff 0 < m <= roundedBelow(p/2), where m is the long representing n in C: TRUE iff (Im(n) != 0 and Im(n) >= 0) or (Im(n) == 0 and Re(n) >= 0) in K(a)/<p(a)>: TRUE iff (n != 0 and (LC(n) > 0 or deg(n) > 0)) in K(t_1, ..., t_n): TRUE iff (LC(numerator(n) is a constant and > 0) or (LC(numerator(n) is not a constant) in Z/2^kZ: TRUE iff 0 < n <= 2^(k-1) in Z/mZ: TRUE iff the internal mpz is greater than zero in Z: TRUE iff n > 0
Definition: coeffs.h:498
#define omAlloc0(size)
Definition: omAllocDecl.h:211