forked from flintlib/flint
-
Notifications
You must be signed in to change notification settings - Fork 0
/
NEWS
1162 lines (999 loc) · 41.5 KB
/
NEWS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
v 1.0 -- 2-Dec-07 :
* First version of FLINT, includes fmpz_poly, fmpz and mpQS
v 1.0.1 -- 7-Dec-07 :
* Fixed a bug in _fmpz_poly_maxbits1 on 32 bit machines, reported by Michael Abshoff and Carl Witty
* Removed some instances of u_int64_t and replaced them with uint64_t, reported by Michael Abshoff
* Replaced sys/types.h with stdint.h
* Added FLINT macros to documentation
* Corrected numerous typos in documentation
v 1.0.2 -- 10-Dec-07
* Rewrote tuning code for integer multiplication functions, making it more robust and fixing a bug
which showed up on 32 bit machines (reported by Michael Abshoff and Jaap Spies). Factored the tuning
code out into a number of macros.
v 1.0.3 -- 16-Dec-07
* Fixed a bug in the polynomial memory managment code which caused a segfault
* Fixed a bug in the pseudo division code which caused a block overrun
v 1.0.4 -- 04-Jan-08
* Fixed a bug in the bernoulli_zmod example program and associated polynomial zmod code which caused memory corruption.
* Fixed a bug in the fmpz-test code which manifested on 32 bit machines, reported by David Harvey.
* Fixed some bugs in the pari profiling code.
v 1.0.5 -- 05-Jan-08
* Fixed some inline issues which cause problems because of the C99 inline rules (reported by David Harvey).
* Fixed a makefile issue reported (and solved) by David Harvey when *not* linking against NTL.
v 1.0.6 -- 17-Jan-08
* Fixed an issue with FLINT_BIT_COUNT on certain machines (probably due to arithmetic shift issues)
v 1.0.7 -- 22-Jan-08
* Made F_mpn_mul binary compatible with the way mpn_mul *operates* in practice.
v 1.0.8 -- 15-Feb-08
* Fixed a bug in fmpz_poly_right_shift (reported by Kiran Kedlaya)
v 1.0.9 -- 11-Mar-08
* Fixed a memory allocation bug in fmpz_poly_power
v 1.0.10 -- 16-Jun-08:
* integer gcd (this just wraps the GMP gcd code)
* polynomial content
* convert to and from FLINT and NTL integers and polynomials
* get a coefficient of a polynomial efficiently as a read only mpz_t
* print polynomials in a prettified format with a specified variable
v 1.0.11 -- 9-Jul-08
* Fixed a bug in z_ll_mod_precomp on ia64 (reported by Michael Abshoff and William Stein)
v 1.0.12 -- 11-Jul-08
* Removed some Opteron tuning flags which cause illegal instruction errors on Pentium4
* Fixed numerous memory leaks in fmpz_poly test code
* Fixed memory leak in fmpz_poly_power_trunc_n
* Fixed major memory leaks in fmpz_poly_xgcd_modular
* Rewrote __fmpz_poly_mul_karatrunc_recursive and _fmpz_poly_mul_karatsuba_trunc to "prove code" and got rid of some dirty memory issues
* Fixed some potential illegal memory accesses to do with cache prefetching in fmpz_poly.c
v 1.0.13 -- 13-Jul-08
* Fixed memory leaks and dirty memory issues in test code for numerous modules.
* Removed further issues with cache prefetching in mpn_extras.c
v 1.0.14 -- 23-Sep-08
* Update long_extras and test code for the sake of new quadratic sieve (new functions in long_extras remain undocumented)
* Removed many bugs from tinyQS and mpQS and joined them into a single program for factoring integers
v 1.0.15 -- 15-Oct-08
* Fixed a bug which causes a segfault when setting a coefficient of the zero polynomial to zero
* Fixed build bug in longlong.h on s390 platform
v 1.0.16 -- 22-Oct-08
* Fixed a segfault when trying to truncate a polynomial to an longer length than it currently is, with the function fmpz_poly_truncate (reported by Craig Citro)
v 1.0.17 -- 30-Nov-08
* Fixed a segfault caused by left shifting of polynomials with zero limbs allocated in division and pseudo division functions.
* Fixed a bound used in fmpz_gcd_modular to use a proven bound
* Fixed a bug in fmpz_poly-profile where the top bit of random coefficients of n bits was always set
v 1.0.18 -- 05-Dec-08
* Fixed another bug in the fmpz_poly_set_coeff_* functions which resulted in dirty coefficients
v 1.0.19 -- 12-Dec-08
* Fixed a bug in z_remove_precomp
v 1.0.20 -- 13-Dec-08
* Fixed some bugs in conversion of zmod_poly's to and from strings
v 1.0.21 -- 25-Dec-08
* Fixed the Christmas bug reported by Michael Abshoff which causes a test failure in fmpz_poly_gcd_modular and a hang in fmpz_poly_invmod_modular on 32 bit machines
v 1.1.0 -- 21-Dec-08 (some of the following features were previewed in FLINT 1.0.11):
* integer gcd (this just wraps the GMP gcd code)
* polynomial content
* primitive part
* convert to and from FLINT and NTL integers and polynomials
* get a coefficient of a polynomial efficiently as a read only mpz_t
* print polynomials in a prettified format with a specified variable
* Sped up integer multiplication
* Convert to and from zmod_polys from fmpz_polys
* Chinese remainder for fmpz_polys
* Leading coeff macro
* Euclidean norm of polynomials
* Exact division testing of polynomials
* Polynomial GCD (subresultant, heuristic, modular)
* Modular inversion of polynomials
* Resultant
* XGCD (Pohst-Zassenhaus)
* Multimodular polynomial multiplication
* Rewritten karatsuba_trunc function
* Rewritten division functions
* Polynomial derivative
* Polynomial evaluation
* Polynomial composition
* Addition and subtraction of zmod_polys
* Sped up multiplication of zmod_polys
* Extended multiplication of zmod_polys to allow up to 63 bit moduli
* zmod_poly subpolynomials
* zmod_poly reverse
* Truncated multiplication for zmod_polys (left, right, classical and KS)
* Scalar multiplication
* Division for zmod_polys (divrem and div, classical, divide and conquer and newton)
* Series inversion for zmod_polys
* Series division for zmod_polys
* Resultant for zmod_polys
* GCD for zmod_polys including half-gcd
* Inversion modulo a polynomial for zmod_polys
* XGCD for zmod_polys
* Squarefree factorisation for zmod_polys
* Berlekamp factorisation for zmod_polys
* Irreducibility testing for zmod_polys
* Derivative for zmod_polys
* Middle product for zmod_polys (sped up newton division)
* addmod, submod and divmod for ulongs
* Sped up limb sized integer square root
* Partial factoring of ulongs
* z_randbits
* Pocklington-Lehmer primality testing
* BSPW pseudo-primality testing
* Fermat pseudo-primality testing
* Fast Legendre symbol computation
* Chinese remainder for fmpzs
* Square root with remainder for fmpzs
* Left and right shift for fmpzs
* Reduction modulo a ulong for fmpzs
* Montgomery redc, mulmod, divmod and mod for fmpzs
* Multimodular reduction and CRT for fmpzs
* fmpz_mulmod and fmpz_divmod
* fmpz_invert for inversion modulo an fmpz
* Dramatically sped up gcd for small fmpzs
* Computation of 1D, 2D and some 3D theta functions
* Example program for multiplying theta functions
* Test code now times test functions
* Quick and dirty timing function for profiler
* Tiny quadratic sieve for small one and two limb integers
* Completely rewritten self initialising multiple polynomial quadratic sieve
* Build fix for 64 bit OSX dylibs (reported by Michael Abshoff)
v 1.1.1 -- 11-Feb-09
* Fixed bugs in _fmpz_poly_scalar_mul_fmpz, fmpz_poly_gcd_heuristic and fmpz_poly_gcd_subresultant and fixed bugs in test__fmpz_poly_scalar_div_fmpz, test_fmpz_poly_scalar_div_fmpz and test_fmpz_poly_scalar_div_mpz.
v 1.1.2 -- 1-Mar-09
* Fixed some memory allocation slowdowns and bugs in fmpz_poly division and pseudo division functions (reported by William Stein).
v 1.1.3 -- 1-Mar-09
* Inserted some missing return values in zmod_poly test code.
v 1.2.0 -- 10-Mar-09
* made memory manager, fmpz and fmpz_poly threadsafe
* Code for running tests in parallel (not activated)
* Sped up fmpz_poly_scalar_div_ui/si when scalar is 1/-1
* Parallelise _fmpz_poly_mul_modular
* fmpz_mul_modular_packed to pack coefficients to the byte before running _fmpz_poly_mul_modular
* fmpz_poly_pseudo_rem_cohen (not documented)
* special case for leading coeff 1/-1 in fmpz_poly_pseudo_divrem_basecase
* removed a memory allocation bug which caused a massive slowdown in fmpz_poly_pseudo_divrem_basecase
* fmpz_poly_pseudo_rem_basecase (not documented)
* fmpz_poly_pseudo_rem (not asymptotically fast)
* fmpz_poly_signature (not asymptotically fast)
* basic fmpz_poly_is_squarefree function
* included zn_poly in trunk and made FLINT build zn_poly as part of its build process
* switched to using zn_poly for polynomial multiplication, newton inversion, scalar multiplication in zmod_poly
* Integer cube root of word sized integers
* Fibonacci pseudoprime test
* BSPW probable prime test
* n - 1 primality test
* Complete implementation of z_issquarefree
* Significantly improved the thetaproduct example program.
* Fixed bug in fmpz_poly_byte_pack which is triggered when trying to pack into fields a multiple of 8 bytes (could cause a segfault)
* Fixed a bug in fmpz_poly_pseudo_divrem (relied on an uninitialised poly to have length 0)
* Fixed bug in fmpz_multi_CRT_ui (could segfault)
* Fixed bug in fmpz_multi_mod_ui (could segfault)
* Fixed memory leak in zmod_poly_factor_squarefree
* Fixed memory leak in zmod_poly_from_string
v 1.2.1 -- 14-Mar-09
* Removed some FLINT 2.0 code which was interfering with the build of the NTL-interface
* Removed an omp.h from fmpz_poly.c.
v 1.2.2 -- 20-Mar-09
* Fixed a memory leak in zmod_poly_factor
* Fixed zmod_poly-profile build
v 1.2.3 -- 31-Mar-09
* Fixed bugs in all fmpz_poly evaluation functions, identified by Burcin Erocal.
v 1.2.4 -- 4-Apr-09
* Defined THREAD to be blank on Apple CC and __thread for thread local storage on other gcc's (where it's defined)
* #undef ulong in profiler.h where time.h and other system time headers are included (both reported by M. Abshoff)
v 1.2.5 -- 18-Apr-09
* Upgraded to zn_poly-0.9 to avoid a serious error in squaring of large polynomials over Z/nZ
v 1.3.0 -- 09-Jun-09
* Added new code for checking 2nd, 3rd and 5th roots
* Fixed a bug in z_factor
* Connected quadratic sieve for factoring large ulongs
* Added one line factor algorithm
* constructed best of breed factor algorithm
* Fixed termination conditions for z_intcuberoot and z_intfifthroot which were broken
* Added some code for special cases which cause infinite loops in cuberoot and fifthroot
* Went back to ceil(pow(n, 0.33333333)) and ceil(pow(n, 0.2)) for initial guesses in cube and fifth root functions as these were about 50% faster than sqrt(n) and sqrt(sqrt(n)) respectively.
* Added test code for z_intfifthroot
* Added test code for z_factor_235power
* Fixed some uninitialised data found by valgrind in intcuberoot and intfifthroot
* Fixed multiply defined PRIME_COUNT in long_extras-test
* Got rid of gotos in some functions in long_extras
* Knocked optimisation level back to -O2 because it miscompiles on sage.math
* Changed tables to use uint64_t's instead of ulongs which are not 64 bits on a 32 bit machine
* Only checked MAX_HOLF on 64 bit machine
* Changed MAX_SQUFOF to WORD(-1)
* Check constant 0x3FFFFFFFFUL only on a 64 bit machine
* Fixed a bug in z_oddprime_lt_4096 on 32 bit machines
* Fixed some TLS issues with Cygwin
* Fixed some typos in makefile
* Fixed a wrong path in fmpz.c
v 1.4.0 -- 06-Jul-09
* Sped up zmod_poly division in case where operands are the same length
* Sped up zmod_poly division in case where operands have lengths differing by 1
* Fixed a bug in zmod_poly_gcd for polynomials of zero length
* Sped up zmod_poly_gcd considerably (both euclidean and half gcd)
* Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably
* Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast
* Made zmod_poly_resultant asymptotically fast
* Added optimised zmod_poly_rem function
* Fixed a divide by zero bug in zmod_poly_factor_berlekamp
* Added test code for z_factor_tinyQS and z_factor_HOLF
* Fixed many bugs in the z_factor code, tinyQS and mpQS
* Corrected numerous typos in the documentation and added missing descriptions
* Added F_mpz_cmp function
* Added documentation to the manual for the new F_mpz module
v 1.5.0 -- 22-Sep-09
* Added multimodular reduction and CRT to F_mpz module
* Fixed some bugs in F_mpz module and numerous bugs in test code
* Added zmod_poly_compose
* Added zmod_poly_evaluate
* Added functions for reduced evaluation and composition to fmpz_poly module (contributed by Burcin Erocal)
* Fixed bugs in the primality tests in long_extras
* Removed all polynomial multimodular multiplication functions
* Added new thetaproduct code used in the 1 trillion triangles computation
* Fixed a severe bug in the fmpz_poly_pseudo_div function reported by Sebastian Pancratz
* Added fmpz_comb_temp_init/clear functions
* Fixed a normalisation buglet in fmpz_poly_pack_bytes
* Added F_mpz_pow_ui function (contributed by Andy Novocin)
* Fixed a severe bug in the FFT reported by William Stein and Mariah Lennox (fix contributed by David Harvey)
* Removed some memory leaks from F_mpz test code
* Fixed bug in zmod_poly_evaluate test code
v 1.6.0 -- 24-Dec-10
Bugs:
====
* Fixed a memory leak in mpz_poly_to_string_pretty
* Fixed a bug inherited from an old version of fpLLL
* Makefile to respect CC and CXX
* Fixed bug in F_mpz_set_si
* Fixed bug in F_mpz_equal
* Most for loops to C90 standard (for easier MSVC porting)
* Better Cygwin support
* Fixed a bug in zmod_poly_resultant
* Fixed bug in F_mpz_mul_KS/2
* Fixed bug in tinyQS
* Worked around some known bugs in older GMP/MPIR's
Major new functionality
=======================
* F_mpz_poly_factor_zassenhaus
* F_mpz_poly_factor (incl. fmpz_poly_factor wrapper) using new vH-N approach
(see the paper of van Hoeij and Novocin and the paper of van Hoeij, Novocin
and Hart)
* Implementation of new CLD bounds function for polynomial factors
(see the paper of van Hoeij, Novocin and Hart
* Restartable Hensel lifting
* Heuristic LLL implementations using doubles and mpfr
* LLL implementations optimised for knapsack lattices
* New (probably subquadratic) LLL implementation (ULLL)
* zmod_poly_factor_cantor_zassenhaus
* New F_mpz_mod_poly module for polynomials over Z/pZ for multiprec. p
Some of the other new functions added
=====================================
F_mpz:
* F_mpz_gcd
* F_mpz_smod
* F_mpz_mod_preinv
* F_mpz_fdiv_qr
* F_mpz_get/set_mpfr/2exp
* F_mpz_sscanf
* F_mpz_set_d
F_mpz_poly:
* read F_mpz_poly to_string/from_string/fprint/print/fread/pretty
* F_mpz_poly_to/from_zmod_poly
* F_mpz_poly_scalar_div_exact
* F_mpz_poly_smod
* F_mpz_poly_derivative, F_mpz_poly_content, F_mpz_poly_eval_horner_d/2exp
* F_mpz_poly_scalar_abs
* F_mpz_poly_set_d_2exp
* F_mpz_poly_div/divrem
* F_mpz_poly_gcd
* F_mpz_poly_is_squarefree
* F_mpz_poly_factor_squarefree
* F_mpz_poly_mul_trunc_left
* F_mpz_poly_pseudo_div
* F_mpz_poly_set_coeff
* F_mpz_poly_pow_ui
* Inflation/deflation trick for factorisation
zmod_poly:
* Inflation/deflation trick for factorisation
mpz_mat:
* mpz_mat_from_string/to_string/fprint/fread/pretty
mpq_mat:
* mpq_mat_init/clear
* Gramm-schmidt Orthogonalisation
F_mpz_mat:
* F_mpz_mat_print/fprint/fread/pretty
* F_mpz_mat_mul_classical
* F_mpz_mat_max_bits/2
* F_mpz_mat_scalar_mul/div_2exp
* F_mpz_mat_col_equal
* F_mpz_mat_smod
* F_mpz_vec_scalar_product/norm
* F_mpz_vec_add/submul_ui/si/F_mpz/2exp
zmod_mat:
* classical multiplication
* strassen multiplication
* scalar multiplication
* zmod_mat_equal
* zmod_mat_add/sub
* zmod_mat_addmul_classical
d_mat:
* d_vec_norm, d_vec_scalar_product
mpfr_mat:
* mpfr_vec_scalar_product/norm
v 2.0 -- 16 Jan 2011
N.B: FLINT 2 is a complete rewrite of flint from scratch
It includes the following modules:
ulong_extras: (word sized integers and modular arithmetic)
* random numbers (randint, randbits, randprime, randint)
* powering
* reverse binary
* mod, divrem, mulmod all with precomputed inverses
* gcd, invgcd, xgcd
* jacobi symbols
* addmod, submod, invmod, powmod
* prime sieve, nextprime, prime-pi, nth-prime
* primality testing (small, binary search, Pocklington-Lehmer, Pseudosquare)
* probably prime tests (strong base-a, Fermat, Fibonacci, BPSW, Lucas)
* sqrt, sqrtrem, is-square, perfect-power (2,3,5)
* remove, is-squarefree
* factorisation (trial-range, trial, power (2,3,5), one-line, SQUFOF)
* Moebius mu, Euler phi
fmpz: (memory managed multiple precision integers)
* memory management (init, clear)
* random numbers (randbits, randm)
* conversion to and from long, ulong, doubles, mpz's, strings
* read/write to file, stdin, stdout
* sizeinbase, bits, size, sgn, swap, set, zero
* cmp, cmp-ui, cmpabs, equal, is-zero, is-one
* neg, abs, add, add-ui, sub, sub-ui, mul, mul-si, mul-ui, mul-2exp
* addmul, addmul-ui, submul, submul-ui
* cdiv-q, cdiv-q-si, cdiv-q-ui
* fdiv-q, fdiv-q-si, fdiv-q-ui, fdiv-qr, fdiv-q-2exp
* tdiv-q, tdiv-q-si
* divexact, divexact-si, divexact-ui
* mod, mod-ui
* powering
* sqrt, sqrt-rem
* factorial
* gcd, invmod
* bit-pack, bit-unpack
* multimodular reduction, CRT
fmpz_vec: (vectors over fmpz's)
* memory management (init, clear)
* random vectors
* max-bits, max-limbs
* read/write to file/stdin/stdout
* set, swap, zero, neg
* equal, is-zero
* sort
* add, sub
* scalar multiplication by fmpz, ulong, long, 2exp
* exact division by fmpz, long, ulong
* fdiv-q by fmpz, long, ulong, 2exp
* tdiv-q by fmpq, long, ulong
* addmul by fmpz, long, long by 2exp
* submul by fmpz, long, long by 2exp
* Gaussian content
fmpz_poly: (polys over fmpz's)
* memory management (init, realloc, fit-length, clear)
* random polys
* normalise, set-length, truncate
* length, degree, max-limbs, max-bits
* set, set-si, set-ui, set-fmpz, set-str
* get-str, get-str-pretty
* zero, one, zero-coeffs
* swap, reverse
* get/set coeffs from fmpz, long, ulong
* get-coeff-ptr, lead
* equal, is-zero
* add, sub
* scalar multiplication by fmpz, long, ulong
* scalar addmul/submul by fmpz
* scalar fdiv by fmpz, long, ulong
* scalar tdiv by fmpz, long, ulong
* scalar divexact by fmpz, long, ulong
* bit pack, bit unpack
* multiplication (classical, karatsuba, KS)
* mullow (classical, karatsuba, KS)
* mulhigh (classical, karatsuba)
* middle product (classical)
* powering (small, binary exponent, binomial, multinomial, addition chains)
* truncated powering (binary exponent)
* shift left/right
* euclidean norm
* gcd (subresultant)
* resultant
* content, primitive part
* divrem (basecase, divide-and-conquer)
* div (basecase, divide-and-conquer)
* rem (basecase)
* invert series (basecase, Newton)
* div series
* pseudo divrem (basecase, divide-and-conquer, Cohen)
* rem (Cohen)
* div
* evaluate (Horner) at fmpz, mpq, a mod n
* composition (Horner, divide-and-conquer)
* signature
* read/write to file/stdin/stdout
fmpq_poly: (polynomials over Q stored as poly over fmpz with fmpz denominator)
* memory management (init, realloc, fit-length, clear)
* random polys
* set-length, canonicalise, normalise, truncate
* is-canonical, length, degree
* reference to numerator, denominator
* set, set-si, set-ui, set-fmpz, set-mpz, set-mpq
* set-array-mpq, set-str
* get-str, get-str-pretty
* zero, neg, swap
* invert
* set coefficient to mpq, long, ulong, fmpz, mpz
* get coefficient as mpq
* equal, cmp, is-one, is-zero
* add, sub
* scalar multiplication by long, ulong, fmpz, mpq
* scalar division by fmpz, long, ulong, mpq
* multiplication, mullow
* powering
* shift left/right
* divrem, div, rem
* invert series (Newton iteration)
* divide series
* derivative
* evaluate at fmpz, mpq
* composition, scale by constant
* content, primitive part
* make-monic, is-monic
* is-squarefree
* read/write to file/stdin/stdout
nmod_vec: (vectors over Z/nZ for n fitting in a machine word)
* memory management (init/clear)
* macros for efficient reduction of 1, 2 and 3 limb integers mod n
* macro for addmul mod n
* add/sub/neg individual coefficients mod n
* random vectors
* set, zero, swap
* reduce, max-bits
* equal
* add, sub, neg
* scalar multiplication by a value reduced mod n
* scalar addmul by a value reduced mod n
nmod_poly: (polynomials over Z/nZ for n fitting in a machine word)
* memory management (init, realloc, fit-length, clear)
* random polys
* normalise, truncate
* length, degree, modulus, max-bits
* set, swap, zero, reverse
* get/set coefficients as ulongs, strings
* read/write to file, stdin, stdout
* equal, is-zero
* shift left/right
* add, sub, neg
* scalar multiplication by a value reduced mod n
* make-monic
* bit pack, bit unpack
* multiplication (classical, KS)
* mullow (classical, KS)
* mulhigh (classical)
* powering (binary exponent)
* pow-trunc (binary exponent)
* divrem (basecase, divide-and-conquer, Newton iteration)
* div (basecase, divide-and-conquer, Newton iteration)
* invert series (basecase, Newton iteration)
* divide series (Newton iteration)
* derivative
* evaluation at a value taken mod n
* composition (Horner, divide-and-conquer)
* gcd (euclidean)
fmpz_mat: (matrices over fmpz's)
* memory management (init, clear)
* random matrices (bits, integer relations, simultaneous diophantine equations
NTRU-like, ajtai, permutation of rows and cols of a diagonal matrix, random
of given rank, random of given determinant, random elementary operations)
* set, init-set, swap, entry pointer
* write to file or stdout
* equal
* transpose
* multiplication (classical, multimodular)
* inverse
* determinant
* row reduce (Gaussian and Gauss-Jordan fraction-free elimination)
* rank
* solve Ax = b, solve AX = B
* fraction free LU decomposition
nmod_mat: (matrices over Z/nZ for n fitting in a machine word)
* memory management (init, clear)
* random matrices (uniform, full, permutations of diagonal matrix, random of
given rank, random elementary operations)
* set, equal
* print to stdout
* add
* transpose
* multiplication (classical, Strassen, A*B^T)
* row reduction (Gaussian and Gauss-Jordan)
* determinant
* rank
* solve (Ax = b, AX = B, solve with precomputed LU)
* invert
arith: (arithmetic functions)
* Bernoulli numbers
* Bernoulli polynomials
* primorials (product of primes up to n)
* harmonic numbers
* Stirling numbers
* Euler phi function
* Moebius mu function
* Sigma (sum of powers of divisors)
* Ramanujan tau function
examples: (example programs)
* compute coefficients of q-series of Delta function
mpfr_vec: (vectors over mpfr reals)
* memory management (init, clear)
* add
* set, zero
* scalar multiplication by mpfr, 2exp
* scalar product
mpfr_mat: (matrices over mpfr reals)
* memory management (init, clear)
v 2.1 -- 9 Mar 2011
fmpz
----
* Simplified interface for fast multimodular reduction and CRT reconstruction
* Fixed segmentation fault in fmpz_multi_mod_ui when the input exceeds the product of the moduli
* Added simple incremental CRT functions (fmpz_CRT_ui, fmpz_CRT_ui_unsigned) to complement the existing fast ones
* Added example programs for CRT
* Added random number generators designed for testing modular code (fmpz_randtest_mod, fmpz_randtest_mod_signed)
* Added fmpz_fdiv_ui for remainder on division by an ulong
* Added fmpz_bin_uiui for computing binomial coefficients
* Added fmpz_mul2_uiui and fmpz_divexact2_uiui for multiplying or dividing an fmpz by a pair of ulongs (efficiently when their product fits in a single limb)
fmpz_mat
--------
* Added utility functions for basic arithmetic and creating unit matrices
* Added multimodular determinant computation (certified or heuristic)
* Added support for computing right nullspaces (fmpz_mat_kernel). Fast only for small matrices.
* Some internal code cleanup and various small fixes
nmod_mat
--------
* Faster Gaussian elimination for small moduli
* Faster determinants
* Faster matrix inversion and nonsingular solving
nmod_poly
---------
* Added nmod_poly_integral for computing integrals
* Added fast square root and inverse square root of power series
* Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh)
* Made nmod_poly_inv_series_newton more memory efficient
fmpq_poly
---------
* Added fmpq_poly_integral for computing integrals
* Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh)
arith
-----
* Made computation of vectors of Bernoulli numbers faster
* Added fast computation of single Bernoulli numbers
* Added a separate function for computing denominators of Bernoulli numbers
* Added fast computation of Bell numbers (vector and single)
* Added fast computation of Euler numbers (vector and single)
* Added fast computation of Euler polynomials
* Added fast computation of Swinnerton-Dyer polynomials
* Added fast computation of Legendre polynomials
* Added fast vector computation of the partition function
* Added fast vector computation of Landau's function
ulong_extras
------------
* Added a function for computing factorials mod n
build system
------------
* Added support for building static and shared libraries
* All object files and test/profile/example binaries now build in separate build directory
documentation
-------------
* Large number of corrections
v 2.2 -- 4 Jun 2011
fmpq (multiprecision rational numbers)
--------------------------------------
* Basic arithmetic functions
* Utility functions
* Rational reconstruction
* Functions for enumerating the rationals
fmpq_mat (matrices over Q)
--------------------------
* Basic arithmetic functions
* Utility functions
* Fast multiplication
* Classical and fraction-free reduced row echelon form
* Determinants
* Fast non-singular solving
fmpz_poly_mat (matrices over Z[x]
---------------------------------
* Basic arithmetic functions
* Utility functions
* Fraction-free row reduction and determinants
* Fast determinants (experimental)
fmpz_mat
--------
* Added more utility functions (scalar multiplication, etc)
* Added Dixon's p-adic algorithm (used by fast nonsingular rational system
solving)
* Added reduced row echelon form
* Added conversions between fmpz_mat and nmod_mat
* Added CRT functions for fmpz_mats
* Faster matrix multiplication for small to medium dimensions
longlong.h
----------
* Added x86 assembly macros for accumulating sums of two limb operands
nmod_mat
--------
* Sped up arithmetic for moduli close to FLINT_BITS
arith
-----
* Changed interface of various functions to use new fmpq type
fmpz
----
* Added fmpz_set_ui_mod
* Inlined fmpz_neg, fmpz_set_si, fmpz_set_ui for better performance
* Added fmpz_lcm
* Small performance improvement to fmpz_CRT_ui
fmpz_vec
--------
* Added _fmpz_vec_lcm
fmpz_poly_q (rational functions over Q, modeled as quotients of fmpz_polys)
---------------------------------------------------------------------------
* Basic arithmetic functions
* Conversion and IO functions
* Evaluation
padic (p-adic numbers -- experimental)
-------------------------------------
* Basic arithmetic
* Data conversion and IO
* Inverse and square root using Newton iteration
* Teichmuller lifts (not optimised)
* p-adic exponential function (not optimised)
fmpz_poly
---------
* Added fmpz_poly_gcd_modular (and fmpz_poly_gcd wrapper)
* Added fmpz_poly_xgcd_modular (and fmpz_poly_xgcd wrapper)
* Added conversions between fmpz_poly and nmod_poly
* Added CRT functions
* Added multipoint evaluation and interpolation
nmod_poly
---------
* Added nmod_poly_xgcd_euclidean (and nmod_poly_xgcd wrapper)
* nmod_poly_gcd wrapper
mpn_extras
----------
* Added MPN_NORM and MPN_SWAP macros.
* Added mpn_gcd_full to remove some of the restrictions from the usual mpn_gcd
build fixes
------------
* fixed make install to create nonexistent dirs (reported by Serge Torres)
* -L use /usr instead of /usr/local by default (reported by Serge Torres)
* guards for system headers because of flint's use of ulong
v 2.3 -- 1 Jul 2012
general
-------
* many changes to the build system
* added NTL interface
* switched to custom memory allocation functions flint_malloc etc
* in addition to the entries below, fixed a large number of memory leaks,
problems with the test code, and bugs in corner cases of various functions
* added _fmpz_cleanup_mpz_content as an alternative to _fmpz_cleanup
* support MinGW32
* support Cygwin
* bugfix on ia64
* support sparc32/sparc64
* support OSX
* support Solaris, NetBSD, OpenBSD, etc (if bash, GNU Make present)
ulong_extras
------------
* implemented the improved Lehman algorithm
* added n_jacobi_unsigned to allow n > WORD_MAX
* fixed n_sqrtmod for n > WORD_MAX
* fixed bug causing n_sqrtmod to hang
* added sublinear algorithm for computing factorials mod p
* added n_sqrtmod_primepow, n_sqrtmodn and associated functions for
computing square roots modulo composite integers
* fixed bugs in n_is_prime_pocklington
* fixed UWORD_MAX case in powmod and powmod2
* fixed problems with the random number generators
* fixed rare bug in n_mod_precomp
* fixed rare bug in n_is_prime_pseudosquare
long_extras
-----------
* added z_sizeinbase
qsieve
------
* new module implementing a quadratic sieve for numbers up to two limbs
fft
---
* new module providing an efficient Schoenhage-Strassen FFT
longlong
--------
* added assembly code for ia64 and ARM
* fixed bug in fallback version of add_sssaaaaaa
fmpz
----
* added fmpz_fib_ui
* added double precision natural logarithm
* added fmpz_val2 for 2-valuation
* added mul_2exp, div_2exp, cdiv_q_2exp, tdiv_q_2exp, fdiv_r, fdiv_r_2exp,
tdiv_ui, mul_tdiv_q_2exp
* added get_d/set_d
* added fmpz_divisible, divisible_si
* optimised fmpz_powm and fmpz_powm_ui
* added clog, clog_ui, flog, flog_ui for computing logarithms
* added abs_lbound_ui_2exp, ubound_ui_2exp
* added fmpz_rfac_ui and fmpz_rfac_uiui for rising factorials
* added functions to obtain read-only fmpz_t's from mpz_t's
* added fmpz_init_set, init_set_ui
* added fmpz_gcdinv
* added fmpz_is_square
* added fmpz_tstbit, setbit, clrbit, complement, combit, and, or, xor, popcnt
* added a sign flag for CRT instead of using separate methods
* fixed bugs in fmpz_sqrtmod
* fixed a bug in fmpz_bit_unpack that could cause corruption of the global
fmpz array when compiled in single mode
* fixed a bug in fmpz_sub_ui that could cause memory corruption
fmpz_vec
--------
* added functions for obtaining the largest absolute value coefficient
* added functions for computing the sum and product of an integer vector
* made max_bits much faster
* added _fmpz_vec_mod_fmpz
* made randtest produce sparse output
fmpz_poly
---------
* added fmpz_poly_sqr, fmpz_poly_sqrlow for squaring a polynomial
* added fmpz_poly_lcm
* made multipoint interpolation faster by using the Newton basis
* added a function for fast division by a linear polynomial
* added power series composition (classical and Brent-Kung)
* added power series reversion (classical, Newton, fast Lagrange)
* added a function for obtaining the largest absolute value coefficient
* fixed quadratic memory usage and stack overflow when performing
unbalanced division or pseudo division using the divconquer algorithm
* fixed a bug in poly_zero_coeffs
* fixed a bug in xgcd_modular
* allowing +/-1 in the constant term of power series inversion
* fixed aliasing bug in divrem
* added restartable Hensel lifting and associated utility functions
* fixed rem, which used to only call the basecase algorithm
* fixed pseudo_divrem, which used to only call the basecase algorithm
* implemented Schoenhage-Strassen multiplication (mul_SS, mullow_SS)
and enabled this by default
* fixed a bug in the heuristic GCD algorithm
* added functions for Newton basis conversion
* added functions for fast Taylor shift
* added fmpz_poly_sqrt implementing a basecase algorithm
* added scalar mul_2exp, fdiv_2exp, tdiv_2exp
* made randtest produce sparse output
* added fmpz_poly_equal_fmpz
* improved performance by always using basecase multiplicatio
when one polynomial is short
* improved algorithm selection for fmpz_poly_gcd
* fixed several bugs in gcd_modular
* improved performance of gcd_modular
fmpz_poly_factor
----------------
* new module for factorisation of fmpz_polys
* added a naive implementation of the Zassenhaus algorithm
fmpz_mod_poly
-------------
* new module for polynomials modulo over Z/nZ for arbitrary-precision n
* multiplication, powering
* classical and divconquer division
* series inversion
* Euclidean GCD and XGCD
* invmod
* radix conversion
* divconquer composition
* GCD and division functions that test invertibility of the
leading coefficient
fmpz_mat
--------
* added det_divisor for computing a random divisor of the determinant
* faster determinant computation using divisor trick
* faster determinant computation by using multimodular updates
* fixed n x 0 x m product not zeroing the result
* various interface improvements
* faster implementation of Cramer's rule for multiple right hand sides
* added fmpz_mat_fread and read
* added multi CRT/mod functions
* added trace
fmpz_poly_mat
-------------
* fixed n x 0 x m product not zeroing the result
* added inverse
* added rank computation
* added reduced row echelon form and nullspace computation
* added more utility functions
* added squaring and exponentiation
* added balanced product of a sequence of matrices
* added truncate, mullow, sqrlow, pow_trunc
* added trace
fmpz_factor
-----------
* new module providing interface for integer factorisation
* fast expansion of a factored integer
fmpq
----
* cleaned up and improved performance of rational reconstruction code
* allow separate numerator and denominator bounds for rational
reconstruction
* added continued fraction expansion
* added functions for summation using binary splitting
* added fmpq_swap
* added fmpq_print, fmpq_get_str
* added fmpq_pow_si
* added functions to obtain read-only fmpq_t's from mpq_t's
* added fmpq_cmp
fmpq_mat
--------
* fixed n x 0 x m product not zeroing the result
* added fmpq_mat_transpose
* added trace
fmpq_poly
---------
* improved speed of multipoint interpolation using _fmpz_poly_div_root
* fmpq_poly: added power series composition (classical and Brent-Kung)
* fmpq_poly: added power series reversion (classical, Newton, fast Lagrange)
* fixed bug wherein set_array_mpq modified the input
* added gcd, xgcd, lcm, resultant
* added fmpq_poly_set_fmpq
* added fmpq_poly_get_slice, fmpq_poly_reverse
* fixed aliasing bug in divrem
* changed some functions to use FLINT scalar types instead of MPIR data types
* added fmpq_poly_get_numerator
nmod_poly
---------
* implemented the half gcd algorithm for subquadratic gcd and xgcd
* added multipoint evaluation and interpolation
* added asymptotically fast multipoint evaluation and interpolation
* added a function for forming the product of linear factors
* added a function for fast division by a linear polynomial
* added power series composition (classical and Brent-Kung)
* added power series reversion (classical, Newton, fast Lagrange)
* added nmod_poly_mulmod, powmod and related functions
(ported from flint1)
* added squarefree, irreducibility tests (ported from flint1)
* added Berlekamp and Cantor-Zassenhaus factoring (ported from flint1)
* fixed quadratic memory usage and stack overflow when performing
unbalanced division using the divconquer algorithm
* added compose_series_divconquer
* added resultant
* fixed aliasing bug in divrem