CLN/ginac: factoring announce, questions

[Ralf Stephan]

> > your comments that, while factor() will go into CLN, divisors() won't.
> 
> No, I didn't say that.

Ah, noted.

> What's the implementation of divisors anyways?
> You factorize, and then build all possible permutations of the factors,
> taking into account their multiplicities, right?  Is there anything else
> one can do that I'm not aware of?

Well, I don't claim to be able to understand pari innards but they
build divisors up while factoring. As speed is dependent on the number
of distinct prime factors, there is no big difference IMHO. And their
code is a mess, though fast.

> Anyways, I see no reason why it shouldn't go into CLN, even if it is only
> a minor wrapper function for factor().  Is there any?

I understood you were cautious to put anything new into CLN but you
clarified that now.

> > int factor (const cl_I& n, std::vector<std::pair<cl_I,cl_I> >& pv);
> 
> We don't need a cl_I for the multiplicities - machine precision integers
> are more than enough.  Also, I would recommend to declare a type
> representing factors and their multiplicity instead of using
> pair<cl_I,uintC>.

These natural changes were done already, I use now long for the exponent,
and the type becomes (in cln/numtheory.h)

// prime factor-exponent pair. A vector of these is written by factor().
typedef struct cl_factexp
{
  cl_I fact;
  long exp;
  cl_factexp (const cl_I& i, long l)  { fact = i; exp = l; }
  bool operator== (const struct cl_factexp& other) 
                      { return fact==other.fact && exp==other.exp; }
  bool operator!= (const struct cl_factexp& other) { return !(*this == other); }
  void *operator new (size_t size)    { return malloc_hook (size); }
  void operator delete (void *p)      { free_hook (p); }
} cl_IFE;

typedef std::vector<cl_IFE*> cl_IFEV;

> Also, what's the integer return value, anyway?

I had meanwhile changed it to bool: false if factoring is incomplete---which
can only happen if one changes the code---but pending the following
discussion this will change again.

> Wouldn't the prototype
> 
>   std::vector<somethingContaining_cl_I_and_unsigned> factor(const cl_I&);
> 
> give us more natural syntax?  I can't see much sense in C-like
> argument shuttling.

First, you want to have signed exponents, it costs only one bit.
Then, who is going to delete the vector? The cl_Is are garbage collected
but not the STL vector itself.


Thanks,
ralf