Re: Segmentation Fault in PARI library related to factoru

Bill, Karim,

Thank for the detailed explanation of the design principles behind t_VEC and t_VECSMALL.

It was surely my oversight in assuming the wrong type of factoru_pow()'s result components. However, I got confused by the "bug in PARI/GP" and "please report" message. This made me think that I may be facing a bug rather than an error in my program.

Btw, speaking about factorization - is there any benefit in using factor_pn_1(p,1) to factor p-1 for prime p as compared to factor(p-1)?

Regards,

Max

On Wed, Nov 29, 2017 at 1:14 PM, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

* 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]
`