Changes commited to PARI GIT during the last two weeks

improve HEADER for number_theoretical

1	1	doc/translations
26	15	src/functions/number_theoretical/HEADER

move kronecker to znstar section

1	1	src/functions/{number_theoretical => znstar}/kronecker

update tutorial

7	13	doc/tutorial.tex

doc updates

15	12	doc/tutorial.tex
2	1	src/functions/number_theoretical/HEADER
2	2	src/functions/number_theoretical/qfbclassno
6	3	src/functions/znstar/zncoppersmith

add znstar HEADER

0	36	src/functions/number_theoretical/HEADER
123	0	src/functions/znstar/HEADER

4- znorder: allow a znstar for the 'order' optional argument

1	0	CHANGES
12	2	src/basemath/arith1.c
15	0	src/basemath/bb_group.c
26	0	src/functions/znstar/znorder
7	1	src/test/32/zn
4	0	src/test/in/zn

newhelp section: znstar, split (Z/NZ)^* functions from number_theoretical

14	13	doc/translations
1	0	src/desc/doc_make
1	0	src/desc/gen_proto
0	76	src/functions/number_theoretical/HEADER
1	1	src/functions/{number_theoretical => znstar}/charconj
1	1	src/functions/{number_theoretical => znstar}/chardiv
1	1	src/functions/{number_theoretical => znstar}/chareval
1	1	src/functions/{number_theoretical => znstar}/chargalois
1	1	src/functions/{number_theoretical => znstar}/charker
1	1	src/functions/{number_theoretical => znstar}/charmul
1	1	src/functions/{number_theoretical => znstar}/charorder
1	1	src/functions/{number_theoretical => znstar}/charpow
1	1	src/functions/{number_theoretical => znstar}/znchar
1	1	src/functions/{number_theoretical => znstar}/zncharconductor
1	1	src/functions/{number_theoretical => znstar}/znchardecompose
1	1	src/functions/{number_theoretical => znstar}/znchargauss
1	1	src/functions/{number_theoretical => znstar}/zncharinduce
1	1	src/functions/{number_theoretical => znstar}/zncharisodd
1	1	src/functions/{number_theoretical => znstar}/znchartokronecker
1	1	src/functions/{number_theoretical => znstar}/znchartoprimitive
1	1	src/functions/{number_theoretical => znstar}/znconreychar
1	1	src/functions/{number_theoretical => znstar}/znconreyconductor
1	1	src/functions/{number_theoretical => znstar}/znconreyexp
1	1	src/functions/{number_theoretical => znstar}/znconreylog
1	1	src/functions/{number_theoretical => znstar}/zncoppersmith
1	1	src/functions/{number_theoretical => znstar}/znlog
1	1	src/functions/{number_theoretical => znstar}/znorder
1	1	src/functions/{number_theoretical => znstar}/znprimroot
1	1	src/functions/{number_theoretical => znstar}/znstar
1	1	src/functions/{number_theoretical => znstar}/znsubgroupgenerators
1	0	src/language/gplib.c
15	14	src/test/32/help

3- [libpari] ZX_realroots

+ fix docs
+ refactor common code in realroots / ZX_realroots_irred

1	0	CHANGES
12	8	doc/usersch5.tex
2	4	src/basemath/base1.c
53	46	src/basemath/rootpol.c
1	0	src/headers/paridecl.h

5- Don't assume irreducibility in polred, polredabs, polredbest [#2689]

The routines could break in presence of rational roots in the totally
real case. E.g., polredbest(x^3-2*x+1) -> SEGV

3	0	CHANGES
30	32	src/basemath/base1.c
7	5	src/functions/number_fields/polred
13	7	src/functions/number_fields/polredabs
11	5	src/functions/number_fields/polredbest
3	4	src/test/32/polred
5	3	src/test/in/polred

improve doc

4	3	doc/usersch5.tex

fix 'help' bench

1	1	doc/translations
1	1	src/functions/programming/HEADER
8	7	src/test/32/help

help gphtml

3	2	src/functions/elliptic_curves/ellheegner

Add section hyperelliptic_curves

6	5	doc/translations
1	0	src/desc/doc_make
2	1	src/desc/gen_proto
12	0	src/functions/hyperelliptic_curves/HEADER
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/genus2charpoly
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/genus2igusa
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/genus2red
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellauto
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellchangecompose
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellchangecurve
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellchangeinvert
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellchangepoint
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellchangepointinv
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellcharpoly
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperelldisc
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellextremalmodels
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellisisom
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellisoncurve
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellminimaldisc
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellminimalmodel
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellordinate
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellpadicfrobenius
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellperiods
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellratpoints
1	1	src/functions/{elliptic_curves => hyperelliptic_curves}/hyperellred
2	1	src/language/gplib.c

whitespace edit

1	1	src/language/gplib.c

fix 'help' bench

27	28	src/test/32/help
1	1	src/test/in/help

make ?? 7 more useful (add GHELPskip markers)

avoid truncation at first subsection

3	4	src/functions/number_theoretical/HEADER
1	1	src/functions/number_theoretical/chargalois

move "chinese" to 'operators' directory

corresponding to its new 'Section'

0	0	src/functions/{number_theoretical => operators}/chinese

kill warnings about signedness

2	2	src/language/es.c
1	1	src/language/gplib.c
1	1	src/language/readline.c

update 'help' bench

18	27	src/test/32/help
1	1	src/test/in/help

split the ?1 help section in 3, as in GP's manual

control statements + GP specific functions + parallel programming

Fewer functions in each sections, more consistent, and allows ??1, ??2, ??3
to print meaningful introductions

18	16	doc/translations
5	7	src/desc/gen_proto
3	1	src/language/gplib.c

improve doc

14	7	src/functions/programming/HEADER

'?' now prints a short introduction + move list of help sections to '?*'

2	0	CHANGES
2	0	COMPAT
1	1	doc/usersch2.tex
39	22	src/language/gplib.c

move functions related to the Euclidean algorithm to the "operators" section

Treat "gcd" (and variants) as as operator: all these functions apply
equally to Z or K[X] (where K is a general field), they fit better here
than among "arithmetic functions".

Also improves content balance between help sections.

2	1	src/functions/number_theoretical/HEADER
1	1	src/functions/number_theoretical/chinese
6	0	src/functions/operators/HEADER
1	1	src/functions/{number_theoretical => operators}/bestappr
1	1	src/functions/{number_theoretical => operators}/bestapprPade
1	1	src/functions/{number_theoretical => operators}/bestapprnf
1	1	src/functions/{number_theoretical => operators}/bezout
1	1	src/functions/{number_theoretical => operators}/content
1	1	src/functions/{number_theoretical => operators}/contfrac
1	1	src/functions/{number_theoretical => operators}/contfracpnqn
1	1	src/functions/{number_theoretical => operators}/gcd
1	1	src/functions/{number_theoretical => operators}/gcdext
1	1	src/functions/{number_theoretical => operators}/halfgcd
1	1	src/functions/{number_theoretical => operators}/lcm

better document \h: now also include information on defaults

7	7	doc/usersch2.tex
3	3	src/language/gplib.c
1	1	src/test/32/help

separate uses of functions_hash and defaults_hash and reduce collisions

1) don't use the same functions_tblsz for both tables. Their sizes
   become functions_hash_MASK + 1 and defaults_hash_MASK + 1

2) make both sizes a power of 2: same number of collisions and cheaper
to convert hash to bucket number (reduce mod a power of 2).

3) functions_hash size was 135. With 1403 built-in symbols,
functions_hash had lots of collisions: up to 23 symbols per bucket on
startup with gp -f, see \h-. Increase size to 8192; now max is initially 3
(which occurs 10 times). This should scale OK up to 6000 symbols or so.

4) defaults_hash size was 135. Reduce to 128 (10 buckets contain 2 entries).
This one is static and the first size with 0 collisions is 1024.
Not worth it ...

4	2	src/headers/paripriv.h
16	16	src/language/anal.c
2	2	src/language/anal.h
3	2	src/language/default.c
29	26	src/language/es.c
1	1	src/language/eval.c
26	7	src/language/gplib.c
13	9	src/language/init.c
5	5	src/language/readline.c

doc typo

1	1	doc/usersch5.tex

print_functions_hash: rewrite diagostics \h- and \h for larger tables

- 3 times as many entries per line
- add total/max to \h-
- add indexmax to both

14	12	src/language/es.c

\h: also print the hash realizing the (first) maximum

5	5	src/language/es.c

fix ?? 7

1	1	doc/translations

divisorslenstra: add complexity

2	1	src/functions/number_theoretical/divisorslenstra

Expand the help text printed when typing '?'

+ improve wording of help sections

26	16	src/language/gplib.c
29	17	src/test/32/help

add a CHANGES entry for numbpart improvements

+ minor improvement to memory use

1	0	CHANGES
1	1	src/modules/part.c

rename L -> SelbergL and compute cosines via roots of unity with caching

- compute cos((6l+1)/(6q) * Pi) as real(r^(1+6l)), r = e(1/(12q))

- compute r^(1+6l) as r^(1+6lastl) * R^d, d = l - last, R = r^6

- compute the successive R^d via a naive addition chain for d, caching
  values. N.B. There are few values of d, with collisions, this improves
  further on caching the R^d by reusing all powers. One could implement
  other improvements, sliding 2^k window or Yao's multipowering,
  but d is "small" and almost all the time is spent computing e(1/(12q)).

N.B there's an optimal formula for L(n,q) in terms of the factorization of q.
Not worth the complication for now.

Before:
    numbpart(10^7); \\ time = 45 ms.
    numbpart(10^8); \\ time = 181 ms.
    numbpart(10^9); \\ time = 4,050 ms.
    numbpart(10^10);\\ time = 56,031 ms.
    numbpart(10^11);\\ time = 54min, 41,505 ms.

After:
    numbpart(10^7); \\ time = 43 ms.
    numbpart(10^8); \\ time = 147 ms.
    numbpart(10^9); \\ time = 1,793 ms.
    numbpart(10^10);\\ time = 17,593 ms.
    numbpart(10^11);\\ time = 8min, 12,924 ms.

44	15	src/modules/part.c

psi: remove unused argument

6	6	src/modules/part.c

2- abs(t_QUAD) would not return exact answer even if possible

For instance
  abs(3 + 4*I) -> 5
but
  abs(3 + 4*quadgen(-4)) -> 5.000000000000
Now the latter is 5 as well.

1	0	CHANGES
14	3	src/basemath/gen2.c
11	2	src/functions/transcendental/abs
5	0	src/test/32/quad
5	0	src/test/in/quad

cgetr(realprec()) -> rtor_lg

2	3	src/headers/pariinl.h

numbpart: reorganize computation + allow n < 2^54

- factor out sqrt(q) term in Psi and sqrt(q/3) in L: avoid square roots
  and replace full precision multiplication by simple multiplication by q

- avoid low precision exponentials: with Selberg formula the neglectible
  sum is actually 0

- precompute pi / 6*q in L

- simplify pinit

- rename estim -> log2pn and return a double

- bound 10^15 was somewhat arbitrary, increase to 2^54. Both would require
  hundreds of years to compute using current implementation.

Asymptotic complexity remains the same (and bad, more than quadratic in
output size instead of almost linear). But 25% improvement for small values,
with diminishing returns.

Before:
  numbpart(10^7); \\ time = 54 ms.
  numbpart(10^8); \\ time = 289 ms.
  numbpart(10^9); \\ time = 5,841 ms.
  numbpart(10^10);\\ time = 1min, 11, 975 ms.
  numbpart(10^11);\\ time = 1h, 9min, 14,433 ms

After:
  numbpart(10^7); \\ time = 45 ms.
  numbpart(10^8); \\ time = 181 ms.
  numbpart(10^9); \\ time = 4,050 ms.
  numbpart(10^10);\\ time = 56,031 ms.
  numbpart(10^11);\\ time = 54min, 41,505 ms.

6	2	src/functions/combinatorics/numbpart
60	71	src/modules/part.c
4	4	src/test/32/partition
3	1	src/test/in/partition

fix make test-kernel: link with dummy Z_ispow2

1	0	src/test/dummy.c

rdivsi, rdivis, rdivss: use cgetg(l, t_REAL)

9	6	src/kernel/none/level1.h

cgetc: improve + fix doc

2	2	doc/usersch5.tex
5	1	src/headers/pariinl.h

update trans bench after commit cb6dca75d7

incgam(4,1,6) incgamm uses 2 more words

1	1	src/test/in/trans

stack corruption in mplog1p due to lg / prec confusion

fixlg argument is a length, not a prec

1	1	src/basemath/trans1.c

cleanup exp1r_abs

17	16	src/basemath/trans1.c

rpowuu: cgetr -> cgetg(,t_REAL)

1	2	src/basemath/trans1.c

bessel: confusions between lg and prec

+ 1 => + EXTRAPREC64

5	4	src/basemath/trans3.c

final prec2nbits cleanups

2	3	doc/usersch5.tex
10	10	src/language/sumiter.c

further prec2nbits cleanups

9	9	src/basemath/rootpol.c

fix bestappr doc and comment in code

4	2	src/basemath/arith1.c
4	1	src/functions/number_theoretical/bestappr

rootpol.c: prec2nbits cleanups

Also fix incorrect paranoia setting in mygprec
  if (bit < 0) bit = 0
to
  if (bit < BITS_IN_LONG) bit = BITS_IN_LONG

26	30	src/basemath/rootpol.c

simple rewrite of prec2nbits uses (= identity now)

3	4	src/basemath/alglin2.c
12	14	src/basemath/bern.c
15	15	src/basemath/bibli2.c
21	23	src/basemath/elltrans.c
13	14	src/basemath/grossenchar.c
41	45	src/basemath/hypergeom.c
7	6	src/basemath/lambert.c
10	10	src/basemath/lerch.c
4	4	src/basemath/lll.c
20	21	src/basemath/mftrace.c
3	5	src/basemath/random.c
65	82	src/basemath/trans1.c
38	43	src/basemath/trans2.c
71	84	src/basemath/trans3.c
14	16	src/basemath/zetamult.c

remove uses of prec2nbits_mul

2	3	src/basemath/bern.c
3	4	src/basemath/bibli1.c
2	3	src/basemath/elliptic.c
3	3	src/basemath/elltrans.c
1	1	src/basemath/hypergeom.c
1	1	src/basemath/mftrace.c
1	1	src/basemath/trans1.c
3	3	src/basemath/trans2.c
11	11	src/basemath/trans3.c

divri: handle divisions by powers of 2 more efficiently

+ document how to input an exact floating point number (in binary).

8	5	doc/usersch2.tex
1	0	src/kernel/gmp/mp.c
1	0	src/kernel/none/mp.c

doc clarifications

9	4	doc/usersch2.tex

absrtostr_width_frac: confusion between lg / prec [similar to f3d63fab9]

4	4	src/language/es.c

deprecate real_1_bit: use real_1

5	0	CHANGES
1	0	COMPAT
2	5	doc/usersch5.tex
1	1	src/basemath/rootpol.c
2	2	src/basemath/trans1.c
1	1	src/basemath/trans2.c
1	1	src/basemath/trans3.c
0	1	src/headers/paridecl.h
1	0	src/headers/pariold.h
1	1	src/kernel/none/add.c
1	3	src/kernel/none/level1.h
8	8	src/language/sumiter.c

fix mpatanh: confusion EXTRAPREC64 -> BITS_IN_LONG + wrong exponent bound

2	2	src/basemath/trans2.c

2- [libpari] rename real_0_bit -> real_0_expo

The argument is not a bitprec, but an exponent. Inconsistent naming with
- real_1_bit (argument is actually a bitpec)
- real_0 (argument is actually a prec)

And inconsistent semantic with real_0(prec) = real_0_bit(- prec).

1	0	CHANGES
6	0	COMPAT
5	3	doc/usersch5.tex
2	2	src/basemath/bibli2.c
1	1	src/basemath/lfun.c
1	1	src/basemath/mftrace.c
2	2	src/basemath/random.c
9	9	src/basemath/rootpol.c
13	13	src/basemath/trans1.c
8	8	src/basemath/trans2.c
1	1	src/headers/paridecl.h
4	4	src/headers/pariinl.h
2	1	src/headers/pariold.h
2	2	src/kernel/gmp/mp.c
4	4	src/kernel/none/add.c
2	2	src/kernel/none/level1.h
2	2	src/kernel/none/mp.c
11	11	src/kernel/none/mp_indep.c
1	1	src/language/anal.c

absrtostr: confusion between lg / prec

lx = lg(x) was changed to lx = realprec(x) without updating occurences of
lx + 1 or lx++

10	10	src/language/es.c

fix prec / length confusions

12	10	doc/usersch4.tex
38	22	doc/usersch5.tex
11	10	src/functions/transcendental/HEADER

update 32-bit benches (getheap) after 859750f9a

EXTRAPRECWORD -> EXTRAPREC64 causes mplog2 to cache a value with one
more word of accuracy

1	1	src/test/in/analyz
1	1	src/test/in/elliptic
1	1	src/test/in/number
1	1	src/test/in/polyser
1	1	src/test/in/program
1	1	src/test/in/sumiter

2- [libpari] fractor_lg, itor_lg, rdivii_lg, rtor_lg, stor_lg, utor_lg

The experimental change of 'prec' parameter from a word length to a bit
precision has created 2 paradigms 'lg' vs. 'prec' and conversions
between each all over the code.

Both still coexist in ugly ways, with conversions that were introduced
to ensure backward compatibility through search and replace. This commit
introduces variants of conversion routines accepting 'lg' parameters in
case it's available.

Goal: avoid direct or indirect uses of consructions like nbits2lg(lg2prec(l)).
If we have an 'lg' l we might as well use it.

For instance

  r = cgetr(l, t_REAL);

instead of

  r = cgetr(lg2prec(l));

cgetr doesn't need its full 'prec' parameter and only needs an 'lg'
(it performs an nbits2lg on its argument)

Or tests comparing lg2prec(lg(x)) against some constant 'prec' where we
might as well compare lg(x) with some 'lg'.

Design choice: introducing a constant EXTRALG64 = EXTRAPREC64 / BITS_IN_LONG
(= 1 or 2) would simplify some code. Don't do this: the default is to
use 'prec', unless 'l' is cleaner and more efficient.

1	0	CHANGES
36	13	doc/usersch5.tex
1	1	src/basemath/F2x.c
4	4	src/basemath/trans1.c
18	17	src/basemath/trans2.c
6	0	src/headers/paridecl.h
12	10	src/kernel/none/add.c
27	10	src/kernel/none/level1.h
15	14	src/kernel/none/mp.c
4	4	src/kernel/none/mp_indep.c
6	5	src/language/intnum.c

typo

1	1	src/basemath/mellininv.c

add proto.c to src/desc/.gitignore

1	0	src/desc/.gitignore

Kderivsmallinit: simplify code

2	6	src/basemath/mellininv.c

fix conceptual difference 32/64-bit due to EXTRAPRECWORD/EXTRAPREC64

The logic of EXTRAPRECWORD is to add "a few" guard bits,actually BITS_IN_LONG,
to cater for terms bounded by log2(ulong).

The logic of incrprec(bit) or bit + EXTRAPREC64 is to do it in an
architecture-independent way (add 64 bits no matter what).

This commit replaces EXTRAPRECWORD by EXTRAPREC64. The odd speed gain on
32-bit architectures is not worth the lack of consistency and potential
for bizarre bugs (further differences in behaviour between 32/64 bits).

EXTRAPRECWORD wasn't actually used consistently or frequently (15 occurences)
and it wasn't documented.

CAVEAT: This is about the precreal ~ bitprec world. A parallel issue
in the 'lg' world is lgprec + 1 or lx++ instead of
  lgprec + EXTRAPREC64 / BITS_IN_LONG
This is much more frequent than EXTRAWORD and will be dealt with later.
For historical reasons a 'bitprec' is actually a "bit accuracy" whereas
a 'prec' is a multiple of BITS_IN_LONG (making the range of attainable
precs depend on the architecture. This is an issue: it should be a
multiple of 64 always.

N.B. It is worth keeping 2 notions of "bit precision" and "mantissa size
in words" even though the latter can be inferred from the former.

1	1	src/basemath/base1.c
3	3	src/basemath/dirichlet.c
2	2	src/basemath/ellanal.c
1	1	src/basemath/ellrank.c
1	1	src/basemath/hyperell.c
1	1	src/basemath/mellininv.c
3	3	src/basemath/trans1.c
3	3	src/basemath/trans2.c
0	1	src/headers/parigen.h

expQ: fix conceptual bug introduced 499574bea

lx++ for t_REAL is achitecture dependent, one should use
  lx += EXTRAPREC64 / BITS_IN_LONG
This occurs elsewhere in the code and will be fixed in other commits.

1	1	src/basemath/trans1.c