Karim Belabas on Wed, 29 Nov 2017 19:15:02 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Segmentation Fault in PARI library related to factoru_pow()


* Max Alekseyev [2017-11-29 18:23]:
> Bill, thank you for clarification!
> I wonder though about the general idea behind using vectors vs small
> vectors. Say, why factoru_pow() returns 3-component vector while its
> components are small vectors? Why not using just small vectors (or just
> vectors) here?

The general rule is : don't use a libpari function without checking
thoroughly the documentation first. It should accurately describe the
preconditions and result types (which may be non obvious).

In general, when a functions takes a (signed or unsigned) long as argument
we strive to keep C integers for the output. [ Not a hard rule. ]

Here are the pros and cons of using t_VEC instead of t_VECSMALL:

* Pros :
 - generic, able to hold arbitrary types and integers of arbitrary sizes;
 - more general, almost all functions are able to handle t_VEC; far
   fewer operate on t_VECSMALL;
 - safe, no overflow

* Cons
 - space complexity; about 4 times the size
 - time complexity; operations with C integers are much faster than the
   equivalent using pari t_INTs (between 20 and 40 times faster);
   conversions between t_INTs and C integers are not very expensive
   but are not free either (each cost about 4 or 5 additions between C longs)

In short, t_VECSMALL (and C integers) are harder to manipulate, but
more efficient. Whether they are worth the trouble and effort for any given
function is left as an exercise to the programmer.

E.g. you can certainly write your code using Z_factor() and use powii() to
compute the primary factors, it will be a little slower but almost all
the time should be spent by the factorization: the gains will be
negligible [ in particular compared to any scheme that will avoid some
or all factorizations, e.g. vecfactoru for consecutive integers, or
caches/memoization, or representing integers by their factorizations, or ... ] 

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`