Re: [flint-devel] Division in Z/pZ[x]

[Bill H. <goo...@go...>]

I was unable to take the division graph any further as Magma crashed with:

driver(
)
prof2d_sample(
    x: 39130,
    y: 18
)
sampler(
    length: 39130,
    bits: 18,
    count: 4
)
In file "poly-ZpXdivexact.m", line 75, column 23:
>>     d := ExactQuotient(c, a);^M
                         ^
Runtime error in 'ExactQuotient': Argument 1 is not exactly divisible by
argument 2


The following lines from the Magma script should guarantee that this
is impossible (and therefore a bug):

p:=NextPrime(Random(2^bits-1));
S:=Integers(p);
....
a:=Polynomial([Random(S): x in [1..length]]);
b:=Polynomial([Random(S): x in [1..length]]);
if a eq 0 then
   a := 1;
end if;
....
c:=a*b;
....
d := ExactQuotient(c, a);

I'll try debugging the script.

Bill.

2009/3/20 Bill Hart <goo...@go...>:
> For those interested, here is a graph comparing FLINT and Magma for
> exact division of polynomials in Z/pZ[x].
>
> http://sage.math.washington.edu/home/wbhart/zpdiv.png
>
> Magma has a function for exact division, which I use. FLINT has no
> such function, but I use zmod_poly_div which does not try to compute
> the (zero) remainder. I don't think exact division is any faster in
> this ring anyhow, so Magma probably doesn't get any advantage here.
>
> Incidentally, I ran sloccount on FLINT. Here are the statistics:
>
> Total Physical Source Lines of Code (SLOC)                = 81,285
> Development Effort Estimate, Person-Years (Person-Months) = 20.26 (243.06)
>  (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
> Schedule Estimate, Years (Months)                         = 1.68 (20.16)
>  (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
> Estimated Average Number of Developers (Effort/Schedule)  = 12.06
> Total Estimated Cost to Develop                           = $ 2,736,230
>  (average salary = $56,286/year, overhead = 2.40).
> SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
> SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
> SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
> redistribute it under certain conditions as specified by the GNU GPL license;
> see the documentation for details.
> Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."
>
> I like the estimate of 20 person years of development effort and total
> cost of development of $ 2,736,230. :-)
>
> Bill.
>