Speed up generation of random number field elements

[craigcitro]

In the process of looking at #3436, I noticed that generation of random number field elements was slow. I was hoping that speeding it up would make it fast enough that we could use a "generic" algorithm for generating matrices over cyclotomic fields. I did get a 100-150X speedup for generating random elements of number fields, but amazingly, this still wasn't quite fast enough to beat the more "quick and dirty" approaches for cyclotomic matrices. However, I think this code is probably still worth merging.

CC: @williamstein @boothby @sagetrac-spancratz

Component: number fields

Author: Craig Citro

Reviewer: David Roe

Merged: sage-4.3.3.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/8007

[craigcitro]

comment:1

I should comment that it's actually not too hard to understand why this still isn't fast enough to beat the code on #3436. A large part of the problem is that we still represent elements of number fields by NTL polynomials -- the lion's share of the difference comes down to the fact that we end up doing several copies of data back and forth between NTL ZZX objects and GMP/MPIR mpz_t and mpq_t objects, which adds up fast.

[robertwb]

comment:2

Looks good, just needs some fixes due to random number generation changes:

	sage -t  devel/sage-main/sage/rings/number_field/number_field.py # 1 doctests failed
	sage -t  devel/sage-main/sage/algebras/quatalg/quaternion_algebra.py # 4 doctests failed

[craigcitro]

comment:3

Cool, fixed. New patch attached.

(Amusingly, the number_field.py failure was a change I made on purpose: I was putting it there for myself as a reminder to doctest everything, because I was habitually only doctesting that directory ... oops.)

[roed314]

comment:4

Attachment: trac_8007.patch.gz

Needs to be rebased against 4.3.2...