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:

• 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 emtpy 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 357 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;
}