วันศุกร์ที่ 30 เมษายน พ.ศ. 2553

Re: [sage-devel] Re: Exactly when to build R with X11 support, etc.

Hi,

Continuing this thread, I think that building Sage shouldn't require
X11. E.g., on t2, the new R png tests fail:

File "/scratch/wstein/build/sage-4.4.1.alpha2/devel/sage/sage/interfaces/r.py",
line 993:
sage: r.png(filename='"%s"'%filename) # filename not needed in
notebook, used for doctesting
Exception raised:
...
sage: r.png(filename='"%s"'%filename) # filename not needed in
notebook, used for doctesting
File "/scratch/wstein/build/sage-4.4.1.alpha2/local/lib/python/site-packages/sage/interfaces/r.py
", line 356, in png
raise RuntimeError, "R was not compiled with PNG support"
RuntimeError: R was not compiled with PNG support
*******************************************************************

---

Unfortunately, this really means that those tests should all be changed to be

# optional -- x11

They won't get tested by "make test". However, doing

./sage -t -only_optional=x11 devel/sage/sage/

will test them. The release manager checklist will suggest to do this check.

I've opened a ticket for this:


http://trac.sagemath.org/sage_trac/ticket/8834

I hope maybe Karl or somebody can make those tests optional.

William

On Fri, Apr 30, 2010 at 7:48 PM, kcrisman <kcrisman@gmail.com> wrote:
>
>
>>
>> > Maybe we should just *always* build it with X support except on Mac?
>> > But presumably it needs some X library to connect to to do that...?
>>
>> sphg-install in R has numerous problems. Someone updated it which
>> caused major hassles on Solaris, with more fallout on Linux. They
>> obviously did not read the documentation, or notice the warnings
>> generated by unknown options passed to the configure script
>>
>> I'm aware the method that was (is) used to build X is stupid. I fixed
>> this for Solaris, but whoever implemented it was using the wrong
>> approach.
>>
>> I created
>>
>> http://trac.sagemath.org/sage_trac/ticket/8274
>>
>> to highlight some of the issues.
>
> Yes, I think that's appeared elsewhere on the list, and I for one
> appreciate your thoroughness.  My fear is that the someone who did
> much of the install script is someone who is no longer working with
> Sage. My own goal with R has been to improve our support of it in the
> ways I can; unfortunately, that doesn't extend to the issues you or
> Dan mention :(   I would point out that (other than the iconv issue,
> which ended up being a bonus for Sage thanks to your work) all the
> recent changes have been improvements, not regressions :)
>
> So that said, it would be great for someone who actually knows
> something about configuring and building (other than Dave, who has
> already put in far more work on it than we could reasonably expect)
> could look at that install script and compare it with the R
> documentation.  But since we have relatively few active developers who
> use R through Sage on a daily basis (at least, it seems so from the
> lists), it may take a while to find someone.  I'm cc:ing John Verzani,
> who has previously interacted with Sage and was quite helpful on the
> latest plotting update, in case he has any ideas of an R devel who is
> knowledgeable about such things and also supportive enough of OSS in
> general to perhaps spend some time looking at it.  We can hope!
>
> - kcrisman
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: sage-4.4.1.alpha2 built with gcc-4.5 segfaults on ia64

William,
I am subscribed to sage-release. OK, I'll cc there and then move over
to there.

The upgrade of polybori to
http://sage.math.washington.edu/home/mvngu/spkg/standard/polybori/polybori-0.6.4.p0.spkg
does not quite help in my case.
Did you have any problems on ia64 with gcc-4.5?

The bug seems strange: e.g. I get:

sage -t -long "devel/sage/sage/groups/abelian_gps/
abelian_group_element.py"
The doctested process was killed by signal 11
[4.3 s]
..............

This file (abelian_group_element.py) has a preamble like
"""
Abelian group elements
[...]
"""

###########################################################################

So if I remove everything above the "##################" line (line
47) it passes!

Dima

On May 1, 1:20 pm, William Stein <wst...@gmail.com> wrote:
> On Fri, Apr 30, 2010 at 9:39 PM, Mike Hansen <mhan...@gmail.com> wrote:
> > On Fri, Apr 30, 2010 at 9:27 PM, Dima Pasechnik <dimp...@gmail.com> wrote:
> >> Seems that this is connected to the reported
> >> *** glibc detected *** python: corrupted double-linked list:
> >> 0x600000000140b350 ***
> >> troubles.
>
> > My guess is that it is indeed
> >http://trac.sagemath.org/sage_trac/ticket/8830.  You can try
> > installing the polybori spkg there.
>
> Yes, that's the issue.  Thanks Mike.
>
> Dima -- you might want to subscribe to sage-release
>
>    http://groups.google.com/group/sage-release
>
> William
>
>
>
> > --Mike
>
> > --
> > To post to this group, send an email to sage-devel@googlegroups.com
> > To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
> > For more options, visit this group athttp://groups.google.com/group/sage-devel
> > URL:http://www.sagemath.org
>
> --
> William Stein
> Professor of Mathematics
> University of Washingtonhttp://wstein.org
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
> For more options, visit this group athttp://groups.google.com/group/sage-devel
> URL:http://www.sagemath.org

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] sage-4.4.1.alpha2 built with gcc-4.5 segfaults on ia64

On Fri, Apr 30, 2010 at 9:39 PM, Mike Hansen <mhansen@gmail.com> wrote:
> On Fri, Apr 30, 2010 at 9:27 PM, Dima Pasechnik <dimpase@gmail.com> wrote:
>> Seems that this is connected to the reported
>> *** glibc detected *** python: corrupted double-linked list:
>> 0x600000000140b350 ***
>> troubles.
>
> My guess is that it is indeed
> http://trac.sagemath.org/sage_trac/ticket/8830 .  You can try
> installing the polybori spkg there.

Yes, that's the issue. Thanks Mike.

Dima -- you might want to subscribe to sage-release

http://groups.google.com/group/sage-release

William

>
> --Mike
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] sage-4.4.1.alpha2 built with gcc-4.5 segfaults on ia64

On Fri, Apr 30, 2010 at 9:27 PM, Dima Pasechnik <dimpase@gmail.com> wrote:
> Seems that this is connected to the reported
> *** glibc detected *** python: corrupted double-linked list:
> 0x600000000140b350 ***
> troubles.

My guess is that it is indeed
http://trac.sagemath.org/sage_trac/ticket/8830 . You can try
installing the polybori spkg there.

--Mike

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] sage-4.4.1.alpha2 built with gcc-4.5 segfaults on ia64

I've built sage-4.4.1.alpha2 on ia64 (Skynet's iras), with gcc-4.5.0,
to investigate recently made GAP patches.
It builds, but during the process, as well as during 'make test' I see
lots of

------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in Sage.
This probably occured because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate (sorry).
------------------------------------------------------------

Seems that this is connected to the reported
*** glibc detected *** python: corrupted double-linked list:
0x600000000140b350 ***
troubles.

Dima

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

On Apr 30, 2010, at 8:00 PM, Bill Hart wrote:

> Finally, the figures for karatsuba with signed coefficients that vary
> wildly. Hardly distinguishable from the figures for classical
> multiplication. With that I finish my little study. And in the
> inimitable words of Adam and Jamie (and with about as much "science"
> to back it up): MYTH BUSTED!!
>
> So what have we learned:
>
> * The Sage timings for multiplication in RR[x] are not great, (please
> note however that my original timings of the classical algorithm in
> flint2 were incorrect due to a bug in my code; flint is actually only
> 10-20% faster for this - the times for the Hartley Transform were also
> misreported and should have been 9ms and 125ms for degree 1000 and
> 10000 multiplications, respectively, still considerably faster than
> Sage).
>
> * Karatsuba does not display noticeably worse behaviour than classical
> multiplication. Toom-Cook is also acceptable.
>
> * There is no such thing as Fateman multiplication.
>
> * The "Fateman multiplication" code is broken.
>
> * The Hartley transform is much better than Rader-Brennen.
>
> * For fixed point arithmetic the FFT techniques are fine, but for
> floating point they will suck when the "magnitude" of the coefficients
> varies greatly.
>
> * To answer the question asked by the OP, yes, there is a better
> algorithm; see the algorithm of Joris vdH
>
> * NO algorithm that we have looked at will deal with the kind of
> cancellation talked about in the docstring which started this whole
> thread off.

May I add another datapoint: rather than looking at random
polynomials, consider power series expansions. Here I compute the
expansion for e^x to 100 terms via classical, karatsuba, and fft over
RR (53-bits) vs. exactly over QQ:

def rel_prec(approx, actual):
return [oo if a==b else -log(abs(a-b)/abs(b), 2) for (a,b) in
zip(approx, actual)]

from numpy.fft import rfft, irfft
def fft_mul(f, g):
n = f.degree() + g.degree() + 1
fft_f = rfft(list(f) + [0] * (n-f.degree()))
fft_g = rfft(list(g) + [0] * (n-g.degree()))
return f.parent()(irfft( fft_f * fft_g ))


sage: R.<x> = QQ[]
sage: f = exp(x+O(x^100)).polynomial()
sage: ff = f.change_ring(RR)

sage: sorted(rel_prec(ff*ff, f*f))
[52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
52, +Infinity, +Infinity, +Infinity, +Infinity, +Infinity, +Infinity,
+Infinity, +Infinity, +Infinity, +Infinity, +Infinity, +Infinity,
+Infinity, +Infinity, +Infinity, +Infinity, +Infinity, +Infinity,
+Infinity, +Infinity, +Infinity]

sage: sorted(rel_prec(ff._mul_karatsuba(ff), f*f))
[7, 9, 10, 11, 12, 12, 12, 14, 15, 16, 20, 21, 21, 25, 25, 26, 26, 28,
30, 30, 33, 35, 39, 40, 41, 41, 43, 44, 45, 45, 46, 50, 50, 50,
+Infinity, +Infinity, +Infinity, +Infinity, +Infinity]

sage: sorted(rel_prec(fft_mul(ff, ff), f*f))
[-61, -54, -46, -44, -42, -35, -32, -24, -24, -18, -13, -12, -8, -3,
-1, 0, 4, 7, 10, 13, 17, 24, 27, 29, 31, 33, 35, 37, 40, 43, 45, 48,
48, 50, 51, 52, 52, 52, +Infinity]

Observation:

- Classical -- Not bad, 1 bit loss max.
- Karatsuba -- Things get pretty bad (especially towards the middle of
the product).
- FFT -- Yes, that's a negative amount of precision, i.e. off by
orders of magnitude, for half the coefficients. It just can't handle a
range of coefficient magnitudes greater than the working precision.

I don't have time to do extensive experiments or draw a conclusion,
but the code above lends itself easily to more investigations in this
direction.

- Robert

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

Finally, the figures for karatsuba with signed coefficients that vary
wildly. Hardly distinguishable from the figures for classical
multiplication. With that I finish my little study. And in the
inimitable words of Adam and Jamie (and with about as much "science"
to back it up): MYTH BUSTED!!

So what have we learned:

* The Sage timings for multiplication in RR[x] are not great, (please
note however that my original timings of the classical algorithm in
flint2 were incorrect due to a bug in my code; flint is actually only
10-20% faster for this - the times for the Hartley Transform were also
misreported and should have been 9ms and 125ms for degree 1000 and
10000 multiplications, respectively, still considerably faster than
Sage).

* Karatsuba does not display noticeably worse behaviour than classical
multiplication. Toom-Cook is also acceptable.

* There is no such thing as Fateman multiplication.

* The "Fateman multiplication" code is broken.

* The Hartley transform is much better than Rader-Brennen.

* For fixed point arithmetic the FFT techniques are fine, but for
floating point they will suck when the "magnitude" of the coefficients
varies greatly.

* To answer the question asked by the OP, yes, there is a better
algorithm; see the algorithm of Joris vdH

* NO algorithm that we have looked at will deal with the kind of
cancellation talked about in the docstring which started this whole
thread off.

If anyone is interested in adding to the module I started off in
flint2 so that we can get some really good code into Sage for this
sort of stuff, please let me know. Missing is code for "Fateman
multiplication", Joris' algorithm, approximate GCD and lots of lower
level stuff, like addition and subtraction of polynomials.

len = 1, min = 0, av = 18, max = 79, prec = 106
len = 2, min = 0, av = 27, max = 101, prec = 106
len = 3, min = 0, av = 22, max = 98, prec = 106
len = 4, min = 0, av = 20, max = 96, prec = 106
len = 6, min = 0, av = 28, max = 85, prec = 106
len = 8, min = 0, av = 31, max = 87, prec = 106
len = 11, min = 0, av = 28, max = 80, prec = 106
len = 15, min = 0, av = 22, max = 85, prec = 106
len = 20, min = 0, av = 26, max = 91, prec = 106
len = 26, min = 0, av = 20, max = 75, prec = 106
len = 34, min = 0, av = 25, max = 104, prec = 106
len = 45, min = 0, av = 26, max = 96, prec = 106
len = 59, min = 0, av = 20, max = 71, prec = 106
len = 77, min = 0, av = 32, max = 86, prec = 106
len = 101, min = 0, av = 29, max = 93, prec = 106
len = 132, min = 0, av = 19, max = 61, prec = 106
len = 172, min = 0, av = 20, max = 88, prec = 106
len = 224, min = 0, av = 28, max = 93, prec = 106
len = 292, min = 0, av = 19, max = 93, prec = 106
len = 380, min = 0, av = 27, max = 98, prec = 106
len = 494, min = 0, av = 27, max = 106, prec = 106
len = 643, min = 0, av = 35, max = 103, prec = 106
len = 836, min = 0, av = 32, max = 89, prec = 106
len = 1087, min = 0, av = 16, max = 90, prec = 106
len = 1414, min = 0, av = 24, max = 89, prec = 106
len = 1839, min = 0, av = 20, max = 83, prec = 106
len = 2391, min = 0, av = 27, max = 82, prec = 106
len = 3109, min = 0, av = 31, max = 100, prec = 106
len = 4042, min = 0, av = 21, max = 104, prec = 106
len = 5255, min = 0, av = 24, max = 62, prec = 106

Bill.


On May 1, 3:25 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> Now karatsuba for signed coefficients:
>
> len = 1, min = 0, av = 0, max = 0, prec = 106
> len = 2, min = 0, av = 1, max = 5, prec = 106
> len = 3, min = 0, av = 1, max = 4, prec = 106
> len = 4, min = 0, av = 0, max = 3, prec = 106
> len = 6, min = 0, av = 0, max = 6, prec = 106
> len = 8, min = 0, av = 1, max = 7, prec = 106
> len = 11, min = 0, av = 0, max = 4, prec = 106
> len = 15, min = 0, av = 1, max = 5, prec = 106
> len = 20, min = 0, av = 1, max = 5, prec = 106
> len = 26, min = 0, av = 1, max = 3, prec = 106
> len = 34, min = 0, av = 1, max = 4, prec = 106
> len = 45, min = 0, av = 0, max = 3, prec = 106
> len = 59, min = 0, av = 1, max = 5, prec = 106
> len = 77, min = 0, av = 0, max = 7, prec = 106
> len = 101, min = 0, av = 1, max = 5, prec = 106
> len = 132, min = 0, av = 1, max = 6, prec = 106
> len = 172, min = 0, av = 1, max = 5, prec = 106
> len = 224, min = 0, av = 0, max = 3, prec = 106
> len = 292, min = 0, av = 1, max = 7, prec = 106
> len = 380, min = 0, av = 0, max = 3, prec = 106
> len = 494, min = 0, av = 0, max = 5, prec = 106
> len = 643, min = 0, av = 0, max = 2, prec = 106
> len = 836, min = 0, av = 0, max = 3, prec = 106
> len = 1087, min = 0, av = 1, max = 2, prec = 106
> len = 1414, min = 0, av = 1, max = 5, prec = 106
> len = 1839, min = 0, av = 0, max = 3, prec = 106
> len = 2391, min = 0, av = 1, max = 5, prec = 106
> len = 3109, min = 0, av = 0, max = 4, prec = 106
> len = 4042, min = 0, av = 0, max = 4, prec = 106
> len = 5255, min = 0, av = 1, max = 8, prec = 106
>
> Bill.
>
> On May 1, 3:19 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > And now for karatsuba. First for unsigned coefficients all about the
> > same magnitude:
>
> > len = 1, min = 0, av = 0, max = 0, prec = 106
> > len = 2, min = 0, av = 1, max = 2, prec = 106
> > len = 3, min = 0, av = 1, max = 3, prec = 106
> > len = 4, min = 0, av = 1, max = 3, prec = 106
> > len = 6, min = 0, av = 0, max = 2, prec = 106
> > len = 8, min = 0, av = 0, max = 3, prec = 106
> > len = 11, min = 0, av = 0, max = 3, prec = 106
> > len = 15, min = 0, av = 0, max = 2, prec = 106
> > len = 20, min = 0, av = 1, max = 3, prec = 106
> > len = 26, min = 0, av = 0, max = 2, prec = 106
> > len = 34, min = 0, av = 0, max = 2, prec = 106
> > len = 45, min = 0, av = 0, max = 2, prec = 106
> > len = 59, min = 0, av = 1, max = 4, prec = 106
> > len = 77, min = 0, av = 1, max = 2, prec = 106
> > len = 101, min = 0, av = 1, max = 3, prec = 106
> > len = 132, min = 0, av = 0, max = 3, prec = 106
> > len = 172, min = 0, av = 1, max = 3, prec = 106
> > len = 224, min = 0, av = 0, max = 2, prec = 106
> > len = 292, min = 0, av = 1, max = 3, prec = 106
> > len = 380, min = 0, av = 0, max = 3, prec = 106
> > len = 494, min = 0, av = 0, max = 3, prec = 106
> > len = 643, min = 0, av = 1, max = 3, prec = 106
> > len = 836, min = 0, av = 1, max = 3, prec = 106
> > len = 1087, min = 0, av = 1, max = 2, prec = 106
> > len = 1414, min = 0, av = 1, max = 3, prec = 106
> > len = 1839, min = 0, av = 0, max = 2, prec = 106
> > len = 2391, min = 0, av = 0, max = 2, prec = 106
> > len = 3109, min = 0, av = 0, max = 2, prec = 106
> > len = 4042, min = 0, av = 1, max = 4, prec = 106
> > len = 5255, min = 0, av = 1, max = 3, prec = 106
>
> > Bill.
>
> > On May 1, 3:13 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > Now for toom cook with wildly varying signed coefficients. A little
> > > over twice the precision loss of the classical algorithm. Hardly what
> > > I'd call an unmitigated disaster. Certainly very usable.
>
> > > len = 1, min = 0, av = 18, max = 79, prec = 106
> > > len = 2, min = 0, av = 27, max = 101, prec = 106
> > > len = 3, min = 0, av = 33, max = 98, prec = 106
> > > len = 4, min = 0, av = 20, max = 96, prec = 106
> > > len = 6, min = 0, av = 39, max = 91, prec = 106
> > > len = 8, min = 1, av = 45, max = 116, prec = 106
> > > len = 11, min = 0, av = 42, max = 145, prec = 106
> > > len = 15, min = 1, av = 28, max = 88, prec = 106
> > > len = 20, min = 0, av = 34, max = 105, prec = 106
> > > len = 26, min = 0, av = 28, max = 75, prec = 106
> > > len = 34, min = 0, av = 39, max = 104, prec = 106
> > > len = 45, min = 0, av = 35, max = 96, prec = 106
> > > len = 59, min = 0, av = 29, max = 82, prec = 106
> > > len = 77, min = 0, av = 40, max = 92, prec = 106
> > > len = 101, min = 0, av = 43, max = 102, prec = 106
> > > len = 132, min = 0, av = 34, max = 92, prec = 106
> > > len = 172, min = 0, av = 29, max = 163, prec = 106
> > > len = 224, min = 2, av = 37, max = 106, prec = 106
> > > len = 292, min = 0, av = 26, max = 99, prec = 106
> > > len = 380, min = 0, av = 35, max = 98, prec = 106
> > > len = 494, min = 0, av = 40, max = 106, prec = 106
> > > len = 643, min = 0, av = 45, max = 103, prec = 106
> > > len = 836, min = 0, av = 39, max = 101, prec = 106
> > > len = 1087, min = 0, av = 27, max = 94, prec = 106
> > > len = 1414, min = 0, av = 37, max = 94, prec = 106
> > > len = 1839, min = 1, av = 31, max = 100, prec = 106
> > > len = 2391, min = 0, av = 32, max = 85, prec = 106
> > > len = 3109, min = 1, av = 47, max = 139, prec = 106
> > > len = 4042, min = 0, av = 36, max = 107, prec = 106
> > > len = 5255, min = 0, av = 33, max = 79, prec = 106
>
> > > Bill.
>
> > > On May 1, 3:07 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > Now toom cook with signed coefficients:
>
> > > > len = 1, min = 0, av = 0, max = 0, prec = 106
> > > > len = 2, min = 0, av = 1, max = 5, prec = 106
> > > > len = 3, min = 0, av = 2, max = 7, prec = 106
> > > > len = 4, min = 0, av = 0, max = 3, prec = 106
> > > > len = 6, min = 0, av = 2, max = 6, prec = 106
> > > > len = 8, min = 0, av = 2, max = 8, prec = 106
> > > > len = 11, min = 0, av = 2, max = 7, prec = 106
> > > > len = 15, min = 0, av = 2, max = 5, prec = 106
> > > > len = 20, min = 0, av = 2, max = 8, prec = 106
> > > > len = 26, min = 0, av = 2, max = 6, prec = 106
> > > > len = 34, min = 0, av = 2, max = 6, prec = 106
> > > > len = 45, min = 0, av = 1, max = 8, prec = 106
> > > > len = 59, min = 0, av = 2, max = 5, prec = 106
> > > > len = 77, min = 0, av = 2, max = 8, prec = 106
> > > > len = 101, min = 0, av = 2, max = 6, prec = 106
> > > > len = 132, min = 0, av = 2, max = 10, prec = 106
> > > > len = 172, min = 0, av = 2, max = 6, prec = 106
> > > > len = 224, min = 0, av = 2, max = 11, prec = 106
> > > > len = 292, min = 0, av = 2, max = 11, prec = 106
> > > > len = 380, min = 0, av = 2, max = 8, prec = 106
> > > > len = 494, min = 0, av = 2, max = 7, prec = 106
> > > > len = 643, min = 0, av = 1, max = 6, prec = 106
> > > > len = 836, min = 0, av = 2, max = 5, prec = 106
> > > > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > > > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > > > len = 1839, min = 0, av = 1, max = 6, prec = 106
> > > > len = 2391, min = 0, av = 1, max = 8, prec = 106
> > > > len = 3109, min = 0, av = 1, max = 8, prec = 106
> > > > len = 4042, min = 0, av = 1, max = 4, prec = 106
> > > > len = 5255, min = 0, av = 2, max = 6, prec = 106
>
> > > > Bill.
>
> > > > On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > As promised, here with toom cook figures, first for unsigned
> > > > > coefficients all about the same magnitude:
>
> > > > > len = 1, min = 0, av = 0, max = 0, prec = 106
> > > > > len = 2, min = 0, av = 1, max = 2, prec = 106
> > > > > len = 3, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 4, min = 0, av = 1, max = 3, prec = 106
> > > > > len = 6, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 8, min = 1, av = 2, max = 6, prec = 106
> > > > > len = 11, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 15, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 20, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 26, min = 0, av = 1, max = 4, prec = 106
> > > > > len = 34, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 45, min = 0, av = 2, max = 4, prec = 106
> > > > > len = 59, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 77, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 101, min = 0, av = 2, max = 4, prec = 106
> > > > > len = 132, min = 0, av = 2, max = 4, prec = 106
> > > > > len = 172, min = 0, av = 2, max = 7, prec = 106
> > > > > len = 224, min = 0, av = 2, max = 7, prec = 106
> > > > > len = 292, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 380, min = 0, av = 2, max = 8, prec = 106
> > > > > len = 494, min = 0, av = 2, max = 4, prec = 106
> > > > > len = 643, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 836, min = 0, av = 2, max = 4, prec = 106
> > > > > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > > > > len = 1839, min = 0, av = 2, max = 6, prec = 106
> > > > > len = 2391, min = 0, av = 2, max = 5, prec = 106
> > > > > len = 3109, min = 0, av = 1, max = 4, prec = 106
> > > > > len = 4042, min = 0, av = 2, max = 7, prec = 106
> > > > > len = 5255, min = 0, av = 2, max = 5, prec = 106
>
> > > > > Bill.
>
> > > > > On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > > And finally, the figures for Rader-Brennan for signed coefficients
> > > > > > whose magnitudes also vary wildly: as with FHT, on average, no usable
> > > > > > information results. No FFT algorithm will be of use in that
> > > > > > situation. Joris vdH's algorithm is your only hope.
>
> > > > > > After dinner, figures for Karatsuba and Toom Cook. I think there may
> > > > > > be a surprise in store for us there....
>
> > > > > > len = 1, min = 0, av = 5, max = 74, prec = 106
> > > > > > len = 2, min = 5, av = 36, max = 106, prec = 106
> > > > > > len = 3, min = 1, av = 46, max = 124, prec = 106
> > > > > > len = 4, min = 2, av = 63, max = 170, prec = 106
> > > > > > len = 6, min = 13, av = 79, max = 140, prec = 106
> > > > > > len = 8, min = 4, av = 95, max = 180, prec = 106
> > > > > > len = 11, min = 8, av = 95, max = 164, prec = 106
> > > > > > len = 15, min = 31, av = 89, max = 163, prec = 106
> > > > > > len = 20, min = 17, av = 107, max = 191, prec = 106
> > > > > > len = 26, min = 26, av = 101, max = 168, prec = 106
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: Exactly when to build R with X11 support, etc.

>
> > Maybe we should just *always* build it with X support except on Mac?
> > But presumably it needs some X library to connect to to do that...?
>
> sphg-install in R has numerous problems. Someone updated it which
> caused major hassles on Solaris, with more fallout on Linux. They
> obviously did not read the documentation, or notice the warnings
> generated by unknown options passed to the configure script
>
> I'm aware the method that was (is) used to build X is stupid. I fixed
> this for Solaris, but whoever implemented it was using the wrong
> approach.
>
> I created
>
> http://trac.sagemath.org/sage_trac/ticket/8274
>
> to highlight some of the issues.

Yes, I think that's appeared elsewhere on the list, and I for one
appreciate your thoroughness. My fear is that the someone who did
much of the install script is someone who is no longer working with
Sage. My own goal with R has been to improve our support of it in the
ways I can; unfortunately, that doesn't extend to the issues you or
Dan mention :( I would point out that (other than the iconv issue,
which ended up being a bonus for Sage thanks to your work) all the
recent changes have been improvements, not regressions :)

So that said, it would be great for someone who actually knows
something about configuring and building (other than Dave, who has
already put in far more work on it than we could reasonably expect)
could look at that install script and compare it with the R
documentation. But since we have relatively few active developers who
use R through Sage on a daily basis (at least, it seems so from the
lists), it may take a while to find someone. I'm cc:ing John Verzani,
who has previously interacted with Sage and was quite helpful on the
latest plotting update, in case he has any ideas of an R devel who is
knowledgeable about such things and also supportive enough of OSS in
general to perhaps spend some time looking at it. We can hope!

- kcrisman

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

Now karatsuba for signed coefficients:

len = 1, min = 0, av = 0, max = 0, prec = 106
len = 2, min = 0, av = 1, max = 5, prec = 106
len = 3, min = 0, av = 1, max = 4, prec = 106
len = 4, min = 0, av = 0, max = 3, prec = 106
len = 6, min = 0, av = 0, max = 6, prec = 106
len = 8, min = 0, av = 1, max = 7, prec = 106
len = 11, min = 0, av = 0, max = 4, prec = 106
len = 15, min = 0, av = 1, max = 5, prec = 106
len = 20, min = 0, av = 1, max = 5, prec = 106
len = 26, min = 0, av = 1, max = 3, prec = 106
len = 34, min = 0, av = 1, max = 4, prec = 106
len = 45, min = 0, av = 0, max = 3, prec = 106
len = 59, min = 0, av = 1, max = 5, prec = 106
len = 77, min = 0, av = 0, max = 7, prec = 106
len = 101, min = 0, av = 1, max = 5, prec = 106
len = 132, min = 0, av = 1, max = 6, prec = 106
len = 172, min = 0, av = 1, max = 5, prec = 106
len = 224, min = 0, av = 0, max = 3, prec = 106
len = 292, min = 0, av = 1, max = 7, prec = 106
len = 380, min = 0, av = 0, max = 3, prec = 106
len = 494, min = 0, av = 0, max = 5, prec = 106
len = 643, min = 0, av = 0, max = 2, prec = 106
len = 836, min = 0, av = 0, max = 3, prec = 106
len = 1087, min = 0, av = 1, max = 2, prec = 106
len = 1414, min = 0, av = 1, max = 5, prec = 106
len = 1839, min = 0, av = 0, max = 3, prec = 106
len = 2391, min = 0, av = 1, max = 5, prec = 106
len = 3109, min = 0, av = 0, max = 4, prec = 106
len = 4042, min = 0, av = 0, max = 4, prec = 106
len = 5255, min = 0, av = 1, max = 8, prec = 106


Bill.

On May 1, 3:19 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> And now for karatsuba. First for unsigned coefficients all about the
> same magnitude:
>
> len = 1, min = 0, av = 0, max = 0, prec = 106
> len = 2, min = 0, av = 1, max = 2, prec = 106
> len = 3, min = 0, av = 1, max = 3, prec = 106
> len = 4, min = 0, av = 1, max = 3, prec = 106
> len = 6, min = 0, av = 0, max = 2, prec = 106
> len = 8, min = 0, av = 0, max = 3, prec = 106
> len = 11, min = 0, av = 0, max = 3, prec = 106
> len = 15, min = 0, av = 0, max = 2, prec = 106
> len = 20, min = 0, av = 1, max = 3, prec = 106
> len = 26, min = 0, av = 0, max = 2, prec = 106
> len = 34, min = 0, av = 0, max = 2, prec = 106
> len = 45, min = 0, av = 0, max = 2, prec = 106
> len = 59, min = 0, av = 1, max = 4, prec = 106
> len = 77, min = 0, av = 1, max = 2, prec = 106
> len = 101, min = 0, av = 1, max = 3, prec = 106
> len = 132, min = 0, av = 0, max = 3, prec = 106
> len = 172, min = 0, av = 1, max = 3, prec = 106
> len = 224, min = 0, av = 0, max = 2, prec = 106
> len = 292, min = 0, av = 1, max = 3, prec = 106
> len = 380, min = 0, av = 0, max = 3, prec = 106
> len = 494, min = 0, av = 0, max = 3, prec = 106
> len = 643, min = 0, av = 1, max = 3, prec = 106
> len = 836, min = 0, av = 1, max = 3, prec = 106
> len = 1087, min = 0, av = 1, max = 2, prec = 106
> len = 1414, min = 0, av = 1, max = 3, prec = 106
> len = 1839, min = 0, av = 0, max = 2, prec = 106
> len = 2391, min = 0, av = 0, max = 2, prec = 106
> len = 3109, min = 0, av = 0, max = 2, prec = 106
> len = 4042, min = 0, av = 1, max = 4, prec = 106
> len = 5255, min = 0, av = 1, max = 3, prec = 106
>
> Bill.
>
> On May 1, 3:13 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > Now for toom cook with wildly varying signed coefficients. A little
> > over twice the precision loss of the classical algorithm. Hardly what
> > I'd call an unmitigated disaster. Certainly very usable.
>
> > len = 1, min = 0, av = 18, max = 79, prec = 106
> > len = 2, min = 0, av = 27, max = 101, prec = 106
> > len = 3, min = 0, av = 33, max = 98, prec = 106
> > len = 4, min = 0, av = 20, max = 96, prec = 106
> > len = 6, min = 0, av = 39, max = 91, prec = 106
> > len = 8, min = 1, av = 45, max = 116, prec = 106
> > len = 11, min = 0, av = 42, max = 145, prec = 106
> > len = 15, min = 1, av = 28, max = 88, prec = 106
> > len = 20, min = 0, av = 34, max = 105, prec = 106
> > len = 26, min = 0, av = 28, max = 75, prec = 106
> > len = 34, min = 0, av = 39, max = 104, prec = 106
> > len = 45, min = 0, av = 35, max = 96, prec = 106
> > len = 59, min = 0, av = 29, max = 82, prec = 106
> > len = 77, min = 0, av = 40, max = 92, prec = 106
> > len = 101, min = 0, av = 43, max = 102, prec = 106
> > len = 132, min = 0, av = 34, max = 92, prec = 106
> > len = 172, min = 0, av = 29, max = 163, prec = 106
> > len = 224, min = 2, av = 37, max = 106, prec = 106
> > len = 292, min = 0, av = 26, max = 99, prec = 106
> > len = 380, min = 0, av = 35, max = 98, prec = 106
> > len = 494, min = 0, av = 40, max = 106, prec = 106
> > len = 643, min = 0, av = 45, max = 103, prec = 106
> > len = 836, min = 0, av = 39, max = 101, prec = 106
> > len = 1087, min = 0, av = 27, max = 94, prec = 106
> > len = 1414, min = 0, av = 37, max = 94, prec = 106
> > len = 1839, min = 1, av = 31, max = 100, prec = 106
> > len = 2391, min = 0, av = 32, max = 85, prec = 106
> > len = 3109, min = 1, av = 47, max = 139, prec = 106
> > len = 4042, min = 0, av = 36, max = 107, prec = 106
> > len = 5255, min = 0, av = 33, max = 79, prec = 106
>
> > Bill.
>
> > On May 1, 3:07 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > Now toom cook with signed coefficients:
>
> > > len = 1, min = 0, av = 0, max = 0, prec = 106
> > > len = 2, min = 0, av = 1, max = 5, prec = 106
> > > len = 3, min = 0, av = 2, max = 7, prec = 106
> > > len = 4, min = 0, av = 0, max = 3, prec = 106
> > > len = 6, min = 0, av = 2, max = 6, prec = 106
> > > len = 8, min = 0, av = 2, max = 8, prec = 106
> > > len = 11, min = 0, av = 2, max = 7, prec = 106
> > > len = 15, min = 0, av = 2, max = 5, prec = 106
> > > len = 20, min = 0, av = 2, max = 8, prec = 106
> > > len = 26, min = 0, av = 2, max = 6, prec = 106
> > > len = 34, min = 0, av = 2, max = 6, prec = 106
> > > len = 45, min = 0, av = 1, max = 8, prec = 106
> > > len = 59, min = 0, av = 2, max = 5, prec = 106
> > > len = 77, min = 0, av = 2, max = 8, prec = 106
> > > len = 101, min = 0, av = 2, max = 6, prec = 106
> > > len = 132, min = 0, av = 2, max = 10, prec = 106
> > > len = 172, min = 0, av = 2, max = 6, prec = 106
> > > len = 224, min = 0, av = 2, max = 11, prec = 106
> > > len = 292, min = 0, av = 2, max = 11, prec = 106
> > > len = 380, min = 0, av = 2, max = 8, prec = 106
> > > len = 494, min = 0, av = 2, max = 7, prec = 106
> > > len = 643, min = 0, av = 1, max = 6, prec = 106
> > > len = 836, min = 0, av = 2, max = 5, prec = 106
> > > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > > len = 1839, min = 0, av = 1, max = 6, prec = 106
> > > len = 2391, min = 0, av = 1, max = 8, prec = 106
> > > len = 3109, min = 0, av = 1, max = 8, prec = 106
> > > len = 4042, min = 0, av = 1, max = 4, prec = 106
> > > len = 5255, min = 0, av = 2, max = 6, prec = 106
>
> > > Bill.
>
> > > On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > As promised, here with toom cook figures, first for unsigned
> > > > coefficients all about the same magnitude:
>
> > > > len = 1, min = 0, av = 0, max = 0, prec = 106
> > > > len = 2, min = 0, av = 1, max = 2, prec = 106
> > > > len = 3, min = 0, av = 2, max = 6, prec = 106
> > > > len = 4, min = 0, av = 1, max = 3, prec = 106
> > > > len = 6, min = 0, av = 2, max = 6, prec = 106
> > > > len = 8, min = 1, av = 2, max = 6, prec = 106
> > > > len = 11, min = 0, av = 2, max = 6, prec = 106
> > > > len = 15, min = 0, av = 2, max = 6, prec = 106
> > > > len = 20, min = 0, av = 2, max = 5, prec = 106
> > > > len = 26, min = 0, av = 1, max = 4, prec = 106
> > > > len = 34, min = 0, av = 2, max = 6, prec = 106
> > > > len = 45, min = 0, av = 2, max = 4, prec = 106
> > > > len = 59, min = 0, av = 2, max = 6, prec = 106
> > > > len = 77, min = 0, av = 2, max = 5, prec = 106
> > > > len = 101, min = 0, av = 2, max = 4, prec = 106
> > > > len = 132, min = 0, av = 2, max = 4, prec = 106
> > > > len = 172, min = 0, av = 2, max = 7, prec = 106
> > > > len = 224, min = 0, av = 2, max = 7, prec = 106
> > > > len = 292, min = 0, av = 2, max = 5, prec = 106
> > > > len = 380, min = 0, av = 2, max = 8, prec = 106
> > > > len = 494, min = 0, av = 2, max = 4, prec = 106
> > > > len = 643, min = 0, av = 2, max = 5, prec = 106
> > > > len = 836, min = 0, av = 2, max = 4, prec = 106
> > > > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > > > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > > > len = 1839, min = 0, av = 2, max = 6, prec = 106
> > > > len = 2391, min = 0, av = 2, max = 5, prec = 106
> > > > len = 3109, min = 0, av = 1, max = 4, prec = 106
> > > > len = 4042, min = 0, av = 2, max = 7, prec = 106
> > > > len = 5255, min = 0, av = 2, max = 5, prec = 106
>
> > > > Bill.
>
> > > > On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > And finally, the figures for Rader-Brennan for signed coefficients
> > > > > whose magnitudes also vary wildly: as with FHT, on average, no usable
> > > > > information results. No FFT algorithm will be of use in that
> > > > > situation. Joris vdH's algorithm is your only hope.
>
> > > > > After dinner, figures for Karatsuba and Toom Cook. I think there may
> > > > > be a surprise in store for us there....
>
> > > > > len = 1, min = 0, av = 5, max = 74, prec = 106
> > > > > len = 2, min = 5, av = 36, max = 106, prec = 106
> > > > > len = 3, min = 1, av = 46, max = 124, prec = 106
> > > > > len = 4, min = 2, av = 63, max = 170, prec = 106
> > > > > len = 6, min = 13, av = 79, max = 140, prec = 106
> > > > > len = 8, min = 4, av = 95, max = 180, prec = 106
> > > > > len = 11, min = 8, av = 95, max = 164, prec = 106
> > > > > len = 15, min = 31, av = 89, max = 163, prec = 106
> > > > > len = 20, min = 17, av = 107, max = 191, prec = 106
> > > > > len = 26, min = 26, av = 101, max = 168, prec = 106
> > > > > len = 34, min = 22, av = 102, max = 199, prec = 106
> > > > > len = 45, min = 9, av = 100, max = 195, prec = 106
> > > > > len = 59, min = 19, av = 101, max = 167, prec = 106
> > > > > len = 77, min = 54, av = 119, max = 187, prec = 106
> > > > > len = 101, min = 46, av = 117, max = 190, prec = 106
> > > > > len = 132, min = 58, av = 103, max = 165, prec = 106
> > > > > len = 172, min = 27, av = 110, max = 199, prec = 106
> > > > > len = 224, min = 47, av = 113, max = 194, prec = 106
> > > > > len = 292, min = 26, av = 110, max = 203, prec = 106
> > > > > len = 380, min = 46, av = 118, max = 203, prec = 106
> > > > > len = 494, min = 38, av = 121, max = 214, prec = 106
> > > > > len = 643, min = 60, av = 132, max = 207, prec = 106
> > > > > len = 836, min = 24, av = 123, max = 198, prec = 106
> > > > > len = 1087, min = 62, av = 111, max = 201, prec = 106
> > > > > len = 1414, min = 27, av = 125, max = 199, prec = 106
> > > > > len = 1839, min = 44, av = 111, max = 194, prec = 106
> > > > > len = 2391, min = 50, av = 120, max = 192, prec = 106
>
> > > > > Bill.
>
> > > > > On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > > I installed Andreas Enge's mpfrcx package:
>
> > > > > >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html
>
> > > > > > which just worked for me.
>
> > > > > > I took a closer look and the Rader-Brennan FFT is a complex FFT taking
> > > > > > mpcx polynomials as input. When multiplying polynomials over the
> > > > > > reals, it simply converts to complex polynomials and uses the complex
> > > > > > RB FFT.
>
> > > > > > Anyhow, this wrapper was very nice for me as it just plugged straight
> > > > > > into my existing profiling code with no modifications whatsoever!!
> > > > > > That sort of thing almost never happens.
>
> > > > > > Anyhow, here is the precision loss figures for unsigned coefficients
> > > > > > all of
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

And now for karatsuba. First for unsigned coefficients all about the
same magnitude:

len = 1, min = 0, av = 0, max = 0, prec = 106
len = 2, min = 0, av = 1, max = 2, prec = 106
len = 3, min = 0, av = 1, max = 3, prec = 106
len = 4, min = 0, av = 1, max = 3, prec = 106
len = 6, min = 0, av = 0, max = 2, prec = 106
len = 8, min = 0, av = 0, max = 3, prec = 106
len = 11, min = 0, av = 0, max = 3, prec = 106
len = 15, min = 0, av = 0, max = 2, prec = 106
len = 20, min = 0, av = 1, max = 3, prec = 106
len = 26, min = 0, av = 0, max = 2, prec = 106
len = 34, min = 0, av = 0, max = 2, prec = 106
len = 45, min = 0, av = 0, max = 2, prec = 106
len = 59, min = 0, av = 1, max = 4, prec = 106
len = 77, min = 0, av = 1, max = 2, prec = 106
len = 101, min = 0, av = 1, max = 3, prec = 106
len = 132, min = 0, av = 0, max = 3, prec = 106
len = 172, min = 0, av = 1, max = 3, prec = 106
len = 224, min = 0, av = 0, max = 2, prec = 106
len = 292, min = 0, av = 1, max = 3, prec = 106
len = 380, min = 0, av = 0, max = 3, prec = 106
len = 494, min = 0, av = 0, max = 3, prec = 106
len = 643, min = 0, av = 1, max = 3, prec = 106
len = 836, min = 0, av = 1, max = 3, prec = 106
len = 1087, min = 0, av = 1, max = 2, prec = 106
len = 1414, min = 0, av = 1, max = 3, prec = 106
len = 1839, min = 0, av = 0, max = 2, prec = 106
len = 2391, min = 0, av = 0, max = 2, prec = 106
len = 3109, min = 0, av = 0, max = 2, prec = 106
len = 4042, min = 0, av = 1, max = 4, prec = 106
len = 5255, min = 0, av = 1, max = 3, prec = 106


Bill.

On May 1, 3:13 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> Now for toom cook with wildly varying signed coefficients. A little
> over twice the precision loss of the classical algorithm. Hardly what
> I'd call an unmitigated disaster. Certainly very usable.
>
> len = 1, min = 0, av = 18, max = 79, prec = 106
> len = 2, min = 0, av = 27, max = 101, prec = 106
> len = 3, min = 0, av = 33, max = 98, prec = 106
> len = 4, min = 0, av = 20, max = 96, prec = 106
> len = 6, min = 0, av = 39, max = 91, prec = 106
> len = 8, min = 1, av = 45, max = 116, prec = 106
> len = 11, min = 0, av = 42, max = 145, prec = 106
> len = 15, min = 1, av = 28, max = 88, prec = 106
> len = 20, min = 0, av = 34, max = 105, prec = 106
> len = 26, min = 0, av = 28, max = 75, prec = 106
> len = 34, min = 0, av = 39, max = 104, prec = 106
> len = 45, min = 0, av = 35, max = 96, prec = 106
> len = 59, min = 0, av = 29, max = 82, prec = 106
> len = 77, min = 0, av = 40, max = 92, prec = 106
> len = 101, min = 0, av = 43, max = 102, prec = 106
> len = 132, min = 0, av = 34, max = 92, prec = 106
> len = 172, min = 0, av = 29, max = 163, prec = 106
> len = 224, min = 2, av = 37, max = 106, prec = 106
> len = 292, min = 0, av = 26, max = 99, prec = 106
> len = 380, min = 0, av = 35, max = 98, prec = 106
> len = 494, min = 0, av = 40, max = 106, prec = 106
> len = 643, min = 0, av = 45, max = 103, prec = 106
> len = 836, min = 0, av = 39, max = 101, prec = 106
> len = 1087, min = 0, av = 27, max = 94, prec = 106
> len = 1414, min = 0, av = 37, max = 94, prec = 106
> len = 1839, min = 1, av = 31, max = 100, prec = 106
> len = 2391, min = 0, av = 32, max = 85, prec = 106
> len = 3109, min = 1, av = 47, max = 139, prec = 106
> len = 4042, min = 0, av = 36, max = 107, prec = 106
> len = 5255, min = 0, av = 33, max = 79, prec = 106
>
> Bill.
>
> On May 1, 3:07 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > Now toom cook with signed coefficients:
>
> > len = 1, min = 0, av = 0, max = 0, prec = 106
> > len = 2, min = 0, av = 1, max = 5, prec = 106
> > len = 3, min = 0, av = 2, max = 7, prec = 106
> > len = 4, min = 0, av = 0, max = 3, prec = 106
> > len = 6, min = 0, av = 2, max = 6, prec = 106
> > len = 8, min = 0, av = 2, max = 8, prec = 106
> > len = 11, min = 0, av = 2, max = 7, prec = 106
> > len = 15, min = 0, av = 2, max = 5, prec = 106
> > len = 20, min = 0, av = 2, max = 8, prec = 106
> > len = 26, min = 0, av = 2, max = 6, prec = 106
> > len = 34, min = 0, av = 2, max = 6, prec = 106
> > len = 45, min = 0, av = 1, max = 8, prec = 106
> > len = 59, min = 0, av = 2, max = 5, prec = 106
> > len = 77, min = 0, av = 2, max = 8, prec = 106
> > len = 101, min = 0, av = 2, max = 6, prec = 106
> > len = 132, min = 0, av = 2, max = 10, prec = 106
> > len = 172, min = 0, av = 2, max = 6, prec = 106
> > len = 224, min = 0, av = 2, max = 11, prec = 106
> > len = 292, min = 0, av = 2, max = 11, prec = 106
> > len = 380, min = 0, av = 2, max = 8, prec = 106
> > len = 494, min = 0, av = 2, max = 7, prec = 106
> > len = 643, min = 0, av = 1, max = 6, prec = 106
> > len = 836, min = 0, av = 2, max = 5, prec = 106
> > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > len = 1839, min = 0, av = 1, max = 6, prec = 106
> > len = 2391, min = 0, av = 1, max = 8, prec = 106
> > len = 3109, min = 0, av = 1, max = 8, prec = 106
> > len = 4042, min = 0, av = 1, max = 4, prec = 106
> > len = 5255, min = 0, av = 2, max = 6, prec = 106
>
> > Bill.
>
> > On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > As promised, here with toom cook figures, first for unsigned
> > > coefficients all about the same magnitude:
>
> > > len = 1, min = 0, av = 0, max = 0, prec = 106
> > > len = 2, min = 0, av = 1, max = 2, prec = 106
> > > len = 3, min = 0, av = 2, max = 6, prec = 106
> > > len = 4, min = 0, av = 1, max = 3, prec = 106
> > > len = 6, min = 0, av = 2, max = 6, prec = 106
> > > len = 8, min = 1, av = 2, max = 6, prec = 106
> > > len = 11, min = 0, av = 2, max = 6, prec = 106
> > > len = 15, min = 0, av = 2, max = 6, prec = 106
> > > len = 20, min = 0, av = 2, max = 5, prec = 106
> > > len = 26, min = 0, av = 1, max = 4, prec = 106
> > > len = 34, min = 0, av = 2, max = 6, prec = 106
> > > len = 45, min = 0, av = 2, max = 4, prec = 106
> > > len = 59, min = 0, av = 2, max = 6, prec = 106
> > > len = 77, min = 0, av = 2, max = 5, prec = 106
> > > len = 101, min = 0, av = 2, max = 4, prec = 106
> > > len = 132, min = 0, av = 2, max = 4, prec = 106
> > > len = 172, min = 0, av = 2, max = 7, prec = 106
> > > len = 224, min = 0, av = 2, max = 7, prec = 106
> > > len = 292, min = 0, av = 2, max = 5, prec = 106
> > > len = 380, min = 0, av = 2, max = 8, prec = 106
> > > len = 494, min = 0, av = 2, max = 4, prec = 106
> > > len = 643, min = 0, av = 2, max = 5, prec = 106
> > > len = 836, min = 0, av = 2, max = 4, prec = 106
> > > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > > len = 1839, min = 0, av = 2, max = 6, prec = 106
> > > len = 2391, min = 0, av = 2, max = 5, prec = 106
> > > len = 3109, min = 0, av = 1, max = 4, prec = 106
> > > len = 4042, min = 0, av = 2, max = 7, prec = 106
> > > len = 5255, min = 0, av = 2, max = 5, prec = 106
>
> > > Bill.
>
> > > On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > And finally, the figures for Rader-Brennan for signed coefficients
> > > > whose magnitudes also vary wildly: as with FHT, on average, no usable
> > > > information results. No FFT algorithm will be of use in that
> > > > situation. Joris vdH's algorithm is your only hope.
>
> > > > After dinner, figures for Karatsuba and Toom Cook. I think there may
> > > > be a surprise in store for us there....
>
> > > > len = 1, min = 0, av = 5, max = 74, prec = 106
> > > > len = 2, min = 5, av = 36, max = 106, prec = 106
> > > > len = 3, min = 1, av = 46, max = 124, prec = 106
> > > > len = 4, min = 2, av = 63, max = 170, prec = 106
> > > > len = 6, min = 13, av = 79, max = 140, prec = 106
> > > > len = 8, min = 4, av = 95, max = 180, prec = 106
> > > > len = 11, min = 8, av = 95, max = 164, prec = 106
> > > > len = 15, min = 31, av = 89, max = 163, prec = 106
> > > > len = 20, min = 17, av = 107, max = 191, prec = 106
> > > > len = 26, min = 26, av = 101, max = 168, prec = 106
> > > > len = 34, min = 22, av = 102, max = 199, prec = 106
> > > > len = 45, min = 9, av = 100, max = 195, prec = 106
> > > > len = 59, min = 19, av = 101, max = 167, prec = 106
> > > > len = 77, min = 54, av = 119, max = 187, prec = 106
> > > > len = 101, min = 46, av = 117, max = 190, prec = 106
> > > > len = 132, min = 58, av = 103, max = 165, prec = 106
> > > > len = 172, min = 27, av = 110, max = 199, prec = 106
> > > > len = 224, min = 47, av = 113, max = 194, prec = 106
> > > > len = 292, min = 26, av = 110, max = 203, prec = 106
> > > > len = 380, min = 46, av = 118, max = 203, prec = 106
> > > > len = 494, min = 38, av = 121, max = 214, prec = 106
> > > > len = 643, min = 60, av = 132, max = 207, prec = 106
> > > > len = 836, min = 24, av = 123, max = 198, prec = 106
> > > > len = 1087, min = 62, av = 111, max = 201, prec = 106
> > > > len = 1414, min = 27, av = 125, max = 199, prec = 106
> > > > len = 1839, min = 44, av = 111, max = 194, prec = 106
> > > > len = 2391, min = 50, av = 120, max = 192, prec = 106
>
> > > > Bill.
>
> > > > On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > I installed Andreas Enge's mpfrcx package:
>
> > > > >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html
>
> > > > > which just worked for me.
>
> > > > > I took a closer look and the Rader-Brennan FFT is a complex FFT taking
> > > > > mpcx polynomials as input. When multiplying polynomials over the
> > > > > reals, it simply converts to complex polynomials and uses the complex
> > > > > RB FFT.
>
> > > > > Anyhow, this wrapper was very nice for me as it just plugged straight
> > > > > into my existing profiling code with no modifications whatsoever!!
> > > > > That sort of thing almost never happens.
>
> > > > > Anyhow, here is the precision loss figures for unsigned coefficients
> > > > > all of about the same magnitude. Looks like about 2.5-3 times the
> > > > > precision loss of the Fast Hartley Transform:
>
> > > > > len = 1, min = 0, av = 0, max = 1, prec = 106
> > > > > len = 2, min = 0, av = 1, max = 3, prec = 106
> > > > > len = 3, min = 0, av = 2, max = 12, prec = 106
> > > > > len = 4, min = 0, av = 2, max = 8, prec = 106
> > > > > len = 6, min = 1, av = 4, max = 9, prec = 106
> > > > > len = 8, min = 2, av = 5, max = 12, prec = 106
> > > > > len = 11, min = 2, av = 5, max = 9, prec = 106
> > > > > len = 15, min = 4, av = 6, max = 12, prec = 106
> > > > > len = 20, min = 6, av = 8, max = 13, prec = 106
> > > > > len = 26, min = 6, av = 8, max = 12, prec = 106
> > > > > len = 34, min = 8, av = 11, max = 18, prec = 106
> > > > > len = 45, min = 9, av = 12, max = 20, prec = 106
> > > > > len = 59, min = 10, av = 12, max = 22, prec = 106
> > > > > len = 77, min = 10, av = 12, max = 17, prec = 106
> > > > > len = 101, min = 10, av = 13, max = 17, prec = 106
> > > > > len = 132, min = 13, av = 15, max = 20, prec = 106
> > > > > len = 172, min = 13, av = 16, max = 21, prec = 106
> > > > > len = 224, min = 14, av = 16, max = 22, prec = 106
> > > > > len = 292, min = 15, av = 17, max = 26, prec = 106
> > > > > len = 380, min = 16, av = 19, max = 27, prec = 106
> > > > > len = 494, min = 16, av = 18, max = 24, prec = 106
> > > > > len = 643, min = 16, av = 18, max = 24, prec = 106
> > > > > len = 836, min = 16, av = 18, max = 22, prec = 106
> > > > > len = 1087, min = 18, av = 20, max = 25, prec = 106
> > > > > len = 1414, min = 19, av = 21, max = 33, prec = 106
> > > > > len = 1839, min = 19, av = 21, max = 30, prec = 106
> > > > > len = 2391, min = 22, av = 24, max = 31, prec = 106
> > > > > len = 3109, min = 23, av = 25, max = 30, prec = 106
> > > > > len = 4042, min = 23, av = 25, max = 30, prec = 106
> > > > > len = 5255, min = 24, av = 26, max = 32, prec = 106
> > > > > len = 6832, min = 25, av = 27, max = 31,
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

Now for toom cook with wildly varying signed coefficients. A little
over twice the precision loss of the classical algorithm. Hardly what
I'd call an unmitigated disaster. Certainly very usable.

len = 1, min = 0, av = 18, max = 79, prec = 106
len = 2, min = 0, av = 27, max = 101, prec = 106
len = 3, min = 0, av = 33, max = 98, prec = 106
len = 4, min = 0, av = 20, max = 96, prec = 106
len = 6, min = 0, av = 39, max = 91, prec = 106
len = 8, min = 1, av = 45, max = 116, prec = 106
len = 11, min = 0, av = 42, max = 145, prec = 106
len = 15, min = 1, av = 28, max = 88, prec = 106
len = 20, min = 0, av = 34, max = 105, prec = 106
len = 26, min = 0, av = 28, max = 75, prec = 106
len = 34, min = 0, av = 39, max = 104, prec = 106
len = 45, min = 0, av = 35, max = 96, prec = 106
len = 59, min = 0, av = 29, max = 82, prec = 106
len = 77, min = 0, av = 40, max = 92, prec = 106
len = 101, min = 0, av = 43, max = 102, prec = 106
len = 132, min = 0, av = 34, max = 92, prec = 106
len = 172, min = 0, av = 29, max = 163, prec = 106
len = 224, min = 2, av = 37, max = 106, prec = 106
len = 292, min = 0, av = 26, max = 99, prec = 106
len = 380, min = 0, av = 35, max = 98, prec = 106
len = 494, min = 0, av = 40, max = 106, prec = 106
len = 643, min = 0, av = 45, max = 103, prec = 106
len = 836, min = 0, av = 39, max = 101, prec = 106
len = 1087, min = 0, av = 27, max = 94, prec = 106
len = 1414, min = 0, av = 37, max = 94, prec = 106
len = 1839, min = 1, av = 31, max = 100, prec = 106
len = 2391, min = 0, av = 32, max = 85, prec = 106
len = 3109, min = 1, av = 47, max = 139, prec = 106
len = 4042, min = 0, av = 36, max = 107, prec = 106
len = 5255, min = 0, av = 33, max = 79, prec = 106


Bill.

On May 1, 3:07 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> Now toom cook with signed coefficients:
>
> len = 1, min = 0, av = 0, max = 0, prec = 106
> len = 2, min = 0, av = 1, max = 5, prec = 106
> len = 3, min = 0, av = 2, max = 7, prec = 106
> len = 4, min = 0, av = 0, max = 3, prec = 106
> len = 6, min = 0, av = 2, max = 6, prec = 106
> len = 8, min = 0, av = 2, max = 8, prec = 106
> len = 11, min = 0, av = 2, max = 7, prec = 106
> len = 15, min = 0, av = 2, max = 5, prec = 106
> len = 20, min = 0, av = 2, max = 8, prec = 106
> len = 26, min = 0, av = 2, max = 6, prec = 106
> len = 34, min = 0, av = 2, max = 6, prec = 106
> len = 45, min = 0, av = 1, max = 8, prec = 106
> len = 59, min = 0, av = 2, max = 5, prec = 106
> len = 77, min = 0, av = 2, max = 8, prec = 106
> len = 101, min = 0, av = 2, max = 6, prec = 106
> len = 132, min = 0, av = 2, max = 10, prec = 106
> len = 172, min = 0, av = 2, max = 6, prec = 106
> len = 224, min = 0, av = 2, max = 11, prec = 106
> len = 292, min = 0, av = 2, max = 11, prec = 106
> len = 380, min = 0, av = 2, max = 8, prec = 106
> len = 494, min = 0, av = 2, max = 7, prec = 106
> len = 643, min = 0, av = 1, max = 6, prec = 106
> len = 836, min = 0, av = 2, max = 5, prec = 106
> len = 1087, min = 0, av = 2, max = 5, prec = 106
> len = 1414, min = 0, av = 2, max = 7, prec = 106
> len = 1839, min = 0, av = 1, max = 6, prec = 106
> len = 2391, min = 0, av = 1, max = 8, prec = 106
> len = 3109, min = 0, av = 1, max = 8, prec = 106
> len = 4042, min = 0, av = 1, max = 4, prec = 106
> len = 5255, min = 0, av = 2, max = 6, prec = 106
>
> Bill.
>
> On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > As promised, here with toom cook figures, first for unsigned
> > coefficients all about the same magnitude:
>
> > len = 1, min = 0, av = 0, max = 0, prec = 106
> > len = 2, min = 0, av = 1, max = 2, prec = 106
> > len = 3, min = 0, av = 2, max = 6, prec = 106
> > len = 4, min = 0, av = 1, max = 3, prec = 106
> > len = 6, min = 0, av = 2, max = 6, prec = 106
> > len = 8, min = 1, av = 2, max = 6, prec = 106
> > len = 11, min = 0, av = 2, max = 6, prec = 106
> > len = 15, min = 0, av = 2, max = 6, prec = 106
> > len = 20, min = 0, av = 2, max = 5, prec = 106
> > len = 26, min = 0, av = 1, max = 4, prec = 106
> > len = 34, min = 0, av = 2, max = 6, prec = 106
> > len = 45, min = 0, av = 2, max = 4, prec = 106
> > len = 59, min = 0, av = 2, max = 6, prec = 106
> > len = 77, min = 0, av = 2, max = 5, prec = 106
> > len = 101, min = 0, av = 2, max = 4, prec = 106
> > len = 132, min = 0, av = 2, max = 4, prec = 106
> > len = 172, min = 0, av = 2, max = 7, prec = 106
> > len = 224, min = 0, av = 2, max = 7, prec = 106
> > len = 292, min = 0, av = 2, max = 5, prec = 106
> > len = 380, min = 0, av = 2, max = 8, prec = 106
> > len = 494, min = 0, av = 2, max = 4, prec = 106
> > len = 643, min = 0, av = 2, max = 5, prec = 106
> > len = 836, min = 0, av = 2, max = 4, prec = 106
> > len = 1087, min = 0, av = 2, max = 5, prec = 106
> > len = 1414, min = 0, av = 2, max = 7, prec = 106
> > len = 1839, min = 0, av = 2, max = 6, prec = 106
> > len = 2391, min = 0, av = 2, max = 5, prec = 106
> > len = 3109, min = 0, av = 1, max = 4, prec = 106
> > len = 4042, min = 0, av = 2, max = 7, prec = 106
> > len = 5255, min = 0, av = 2, max = 5, prec = 106
>
> > Bill.
>
> > On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > And finally, the figures for Rader-Brennan for signed coefficients
> > > whose magnitudes also vary wildly: as with FHT, on average, no usable
> > > information results. No FFT algorithm will be of use in that
> > > situation. Joris vdH's algorithm is your only hope.
>
> > > After dinner, figures for Karatsuba and Toom Cook. I think there may
> > > be a surprise in store for us there....
>
> > > len = 1, min = 0, av = 5, max = 74, prec = 106
> > > len = 2, min = 5, av = 36, max = 106, prec = 106
> > > len = 3, min = 1, av = 46, max = 124, prec = 106
> > > len = 4, min = 2, av = 63, max = 170, prec = 106
> > > len = 6, min = 13, av = 79, max = 140, prec = 106
> > > len = 8, min = 4, av = 95, max = 180, prec = 106
> > > len = 11, min = 8, av = 95, max = 164, prec = 106
> > > len = 15, min = 31, av = 89, max = 163, prec = 106
> > > len = 20, min = 17, av = 107, max = 191, prec = 106
> > > len = 26, min = 26, av = 101, max = 168, prec = 106
> > > len = 34, min = 22, av = 102, max = 199, prec = 106
> > > len = 45, min = 9, av = 100, max = 195, prec = 106
> > > len = 59, min = 19, av = 101, max = 167, prec = 106
> > > len = 77, min = 54, av = 119, max = 187, prec = 106
> > > len = 101, min = 46, av = 117, max = 190, prec = 106
> > > len = 132, min = 58, av = 103, max = 165, prec = 106
> > > len = 172, min = 27, av = 110, max = 199, prec = 106
> > > len = 224, min = 47, av = 113, max = 194, prec = 106
> > > len = 292, min = 26, av = 110, max = 203, prec = 106
> > > len = 380, min = 46, av = 118, max = 203, prec = 106
> > > len = 494, min = 38, av = 121, max = 214, prec = 106
> > > len = 643, min = 60, av = 132, max = 207, prec = 106
> > > len = 836, min = 24, av = 123, max = 198, prec = 106
> > > len = 1087, min = 62, av = 111, max = 201, prec = 106
> > > len = 1414, min = 27, av = 125, max = 199, prec = 106
> > > len = 1839, min = 44, av = 111, max = 194, prec = 106
> > > len = 2391, min = 50, av = 120, max = 192, prec = 106
>
> > > Bill.
>
> > > On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > I installed Andreas Enge's mpfrcx package:
>
> > > >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html
>
> > > > which just worked for me.
>
> > > > I took a closer look and the Rader-Brennan FFT is a complex FFT taking
> > > > mpcx polynomials as input. When multiplying polynomials over the
> > > > reals, it simply converts to complex polynomials and uses the complex
> > > > RB FFT.
>
> > > > Anyhow, this wrapper was very nice for me as it just plugged straight
> > > > into my existing profiling code with no modifications whatsoever!!
> > > > That sort of thing almost never happens.
>
> > > > Anyhow, here is the precision loss figures for unsigned coefficients
> > > > all of about the same magnitude. Looks like about 2.5-3 times the
> > > > precision loss of the Fast Hartley Transform:
>
> > > > len = 1, min = 0, av = 0, max = 1, prec = 106
> > > > len = 2, min = 0, av = 1, max = 3, prec = 106
> > > > len = 3, min = 0, av = 2, max = 12, prec = 106
> > > > len = 4, min = 0, av = 2, max = 8, prec = 106
> > > > len = 6, min = 1, av = 4, max = 9, prec = 106
> > > > len = 8, min = 2, av = 5, max = 12, prec = 106
> > > > len = 11, min = 2, av = 5, max = 9, prec = 106
> > > > len = 15, min = 4, av = 6, max = 12, prec = 106
> > > > len = 20, min = 6, av = 8, max = 13, prec = 106
> > > > len = 26, min = 6, av = 8, max = 12, prec = 106
> > > > len = 34, min = 8, av = 11, max = 18, prec = 106
> > > > len = 45, min = 9, av = 12, max = 20, prec = 106
> > > > len = 59, min = 10, av = 12, max = 22, prec = 106
> > > > len = 77, min = 10, av = 12, max = 17, prec = 106
> > > > len = 101, min = 10, av = 13, max = 17, prec = 106
> > > > len = 132, min = 13, av = 15, max = 20, prec = 106
> > > > len = 172, min = 13, av = 16, max = 21, prec = 106
> > > > len = 224, min = 14, av = 16, max = 22, prec = 106
> > > > len = 292, min = 15, av = 17, max = 26, prec = 106
> > > > len = 380, min = 16, av = 19, max = 27, prec = 106
> > > > len = 494, min = 16, av = 18, max = 24, prec = 106
> > > > len = 643, min = 16, av = 18, max = 24, prec = 106
> > > > len = 836, min = 16, av = 18, max = 22, prec = 106
> > > > len = 1087, min = 18, av = 20, max = 25, prec = 106
> > > > len = 1414, min = 19, av = 21, max = 33, prec = 106
> > > > len = 1839, min = 19, av = 21, max = 30, prec = 106
> > > > len = 2391, min = 22, av = 24, max = 31, prec = 106
> > > > len = 3109, min = 23, av = 25, max = 30, prec = 106
> > > > len = 4042, min = 23, av = 25, max = 30, prec = 106
> > > > len = 5255, min = 24, av = 26, max = 32, prec = 106
> > > > len = 6832, min = 25, av = 27, max = 31, prec = 106
>
> > > > Bill.
>
> > > > On Apr 30, 12:12 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > If the coefficients are allowed to vary in sign and vary wildly in the
> > > > > number of bits, then nothing will save you. Here are the figures for
> > > > > classical multiplication:
>
> > > > > len = 1, min = 0, av = 18, max = 79, prec = 106
> > > > > len = 2, min = 0, av = 23, max = 101, prec = 106
> > > > > len = 3, min = 0, av = 19, max = 98, prec = 106
> > > > > len = 4, min = 0, av = 16, max = 96, prec = 106
> > > > > len = 6, min = 0, av = 21, max = 85, prec = 106
> > > > > len = 8, min = 0, av = 26, max = 87, prec = 106
> > > > > len = 11, min = 0, av = 24, max = 80, prec = 106
> > > > > len = 15, min = 0, av = 15, max = 85, prec = 106
> > > > > len = 20, min = 0, av = 25, max = 91, prec = 106
> > > > > len = 26, min = 0, av = 16, max = 75, prec = 106
> > > > > len = 34, min = 0, av = 20, max = 104, prec = 106
> > > > > len = 45, min = 0, av = 20, max = 96, prec = 106
> > > > > len = 59, min = 0, av = 16, max = 71, prec = 106
> > > > > len = 77, min = 0, av = 26, max = 86, prec = 106
> > > > > len = 101, min = 0, av = 24, max = 93, prec = 106
> > > > > len = 132, min = 0, av = 10, max = 61, prec = 106
> > > > > len = 172, min = 0, av = 19, max = 88, prec = 106
> > > > > len = 224, min = 0, av = 21, max = 93, prec = 106
> > > > > len = 292, min = 0, av = 16, max = 93, prec = 106
> > > > > len = 380, min = 0, av = 23, max = 98, prec = 106
> > > > > len = 494, min = 0, av = 25, max = 106, prec = 106
> > > > > len = 643, min = 0, av = 31, max = 103, prec = 106
> > > > > len = 836, min = 0, av = 28, max = 89, prec = 106
> > > > > len = 1087, min = 0, av = 13, max = 90, prec = 106
> > > > > len = 1414, min = 0, av = 22, max = 89, prec = 106
> > > > > len = 1839, min = 0, av = 15, max = 83, prec = 106
> > > > > len = 2391, min = 0, av = 21, max = 82, prec = 106
>
> > > > > And also for FHT:
>
> > > > > len = 1, min = 0, av = 12, max = 79, prec = 106
> > > > > len = 2, min = 0, av = 32, max = 108, prec = 106
> > > > > len = 3, min = 0, av = 39, max = 123, prec = 106
> > > > > len = 4,
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

Now toom cook with signed coefficients:

len = 1, min = 0, av = 0, max = 0, prec = 106
len = 2, min = 0, av = 1, max = 5, prec = 106
len = 3, min = 0, av = 2, max = 7, prec = 106
len = 4, min = 0, av = 0, max = 3, prec = 106
len = 6, min = 0, av = 2, max = 6, prec = 106
len = 8, min = 0, av = 2, max = 8, prec = 106
len = 11, min = 0, av = 2, max = 7, prec = 106
len = 15, min = 0, av = 2, max = 5, prec = 106
len = 20, min = 0, av = 2, max = 8, prec = 106
len = 26, min = 0, av = 2, max = 6, prec = 106
len = 34, min = 0, av = 2, max = 6, prec = 106
len = 45, min = 0, av = 1, max = 8, prec = 106
len = 59, min = 0, av = 2, max = 5, prec = 106
len = 77, min = 0, av = 2, max = 8, prec = 106
len = 101, min = 0, av = 2, max = 6, prec = 106
len = 132, min = 0, av = 2, max = 10, prec = 106
len = 172, min = 0, av = 2, max = 6, prec = 106
len = 224, min = 0, av = 2, max = 11, prec = 106
len = 292, min = 0, av = 2, max = 11, prec = 106
len = 380, min = 0, av = 2, max = 8, prec = 106
len = 494, min = 0, av = 2, max = 7, prec = 106
len = 643, min = 0, av = 1, max = 6, prec = 106
len = 836, min = 0, av = 2, max = 5, prec = 106
len = 1087, min = 0, av = 2, max = 5, prec = 106
len = 1414, min = 0, av = 2, max = 7, prec = 106
len = 1839, min = 0, av = 1, max = 6, prec = 106
len = 2391, min = 0, av = 1, max = 8, prec = 106
len = 3109, min = 0, av = 1, max = 8, prec = 106
len = 4042, min = 0, av = 1, max = 4, prec = 106
len = 5255, min = 0, av = 2, max = 6, prec = 106

Bill.


On May 1, 3:01 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> As promised, here with toom cook figures, first for unsigned
> coefficients all about the same magnitude:
>
> len = 1, min = 0, av = 0, max = 0, prec = 106
> len = 2, min = 0, av = 1, max = 2, prec = 106
> len = 3, min = 0, av = 2, max = 6, prec = 106
> len = 4, min = 0, av = 1, max = 3, prec = 106
> len = 6, min = 0, av = 2, max = 6, prec = 106
> len = 8, min = 1, av = 2, max = 6, prec = 106
> len = 11, min = 0, av = 2, max = 6, prec = 106
> len = 15, min = 0, av = 2, max = 6, prec = 106
> len = 20, min = 0, av = 2, max = 5, prec = 106
> len = 26, min = 0, av = 1, max = 4, prec = 106
> len = 34, min = 0, av = 2, max = 6, prec = 106
> len = 45, min = 0, av = 2, max = 4, prec = 106
> len = 59, min = 0, av = 2, max = 6, prec = 106
> len = 77, min = 0, av = 2, max = 5, prec = 106
> len = 101, min = 0, av = 2, max = 4, prec = 106
> len = 132, min = 0, av = 2, max = 4, prec = 106
> len = 172, min = 0, av = 2, max = 7, prec = 106
> len = 224, min = 0, av = 2, max = 7, prec = 106
> len = 292, min = 0, av = 2, max = 5, prec = 106
> len = 380, min = 0, av = 2, max = 8, prec = 106
> len = 494, min = 0, av = 2, max = 4, prec = 106
> len = 643, min = 0, av = 2, max = 5, prec = 106
> len = 836, min = 0, av = 2, max = 4, prec = 106
> len = 1087, min = 0, av = 2, max = 5, prec = 106
> len = 1414, min = 0, av = 2, max = 7, prec = 106
> len = 1839, min = 0, av = 2, max = 6, prec = 106
> len = 2391, min = 0, av = 2, max = 5, prec = 106
> len = 3109, min = 0, av = 1, max = 4, prec = 106
> len = 4042, min = 0, av = 2, max = 7, prec = 106
> len = 5255, min = 0, av = 2, max = 5, prec = 106
>
> Bill.
>
> On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > And finally, the figures for Rader-Brennan for signed coefficients
> > whose magnitudes also vary wildly: as with FHT, on average, no usable
> > information results. No FFT algorithm will be of use in that
> > situation. Joris vdH's algorithm is your only hope.
>
> > After dinner, figures for Karatsuba and Toom Cook. I think there may
> > be a surprise in store for us there....
>
> > len = 1, min = 0, av = 5, max = 74, prec = 106
> > len = 2, min = 5, av = 36, max = 106, prec = 106
> > len = 3, min = 1, av = 46, max = 124, prec = 106
> > len = 4, min = 2, av = 63, max = 170, prec = 106
> > len = 6, min = 13, av = 79, max = 140, prec = 106
> > len = 8, min = 4, av = 95, max = 180, prec = 106
> > len = 11, min = 8, av = 95, max = 164, prec = 106
> > len = 15, min = 31, av = 89, max = 163, prec = 106
> > len = 20, min = 17, av = 107, max = 191, prec = 106
> > len = 26, min = 26, av = 101, max = 168, prec = 106
> > len = 34, min = 22, av = 102, max = 199, prec = 106
> > len = 45, min = 9, av = 100, max = 195, prec = 106
> > len = 59, min = 19, av = 101, max = 167, prec = 106
> > len = 77, min = 54, av = 119, max = 187, prec = 106
> > len = 101, min = 46, av = 117, max = 190, prec = 106
> > len = 132, min = 58, av = 103, max = 165, prec = 106
> > len = 172, min = 27, av = 110, max = 199, prec = 106
> > len = 224, min = 47, av = 113, max = 194, prec = 106
> > len = 292, min = 26, av = 110, max = 203, prec = 106
> > len = 380, min = 46, av = 118, max = 203, prec = 106
> > len = 494, min = 38, av = 121, max = 214, prec = 106
> > len = 643, min = 60, av = 132, max = 207, prec = 106
> > len = 836, min = 24, av = 123, max = 198, prec = 106
> > len = 1087, min = 62, av = 111, max = 201, prec = 106
> > len = 1414, min = 27, av = 125, max = 199, prec = 106
> > len = 1839, min = 44, av = 111, max = 194, prec = 106
> > len = 2391, min = 50, av = 120, max = 192, prec = 106
>
> > Bill.
>
> > On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > I installed Andreas Enge's mpfrcx package:
>
> > >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html
>
> > > which just worked for me.
>
> > > I took a closer look and the Rader-Brennan FFT is a complex FFT taking
> > > mpcx polynomials as input. When multiplying polynomials over the
> > > reals, it simply converts to complex polynomials and uses the complex
> > > RB FFT.
>
> > > Anyhow, this wrapper was very nice for me as it just plugged straight
> > > into my existing profiling code with no modifications whatsoever!!
> > > That sort of thing almost never happens.
>
> > > Anyhow, here is the precision loss figures for unsigned coefficients
> > > all of about the same magnitude. Looks like about 2.5-3 times the
> > > precision loss of the Fast Hartley Transform:
>
> > > len = 1, min = 0, av = 0, max = 1, prec = 106
> > > len = 2, min = 0, av = 1, max = 3, prec = 106
> > > len = 3, min = 0, av = 2, max = 12, prec = 106
> > > len = 4, min = 0, av = 2, max = 8, prec = 106
> > > len = 6, min = 1, av = 4, max = 9, prec = 106
> > > len = 8, min = 2, av = 5, max = 12, prec = 106
> > > len = 11, min = 2, av = 5, max = 9, prec = 106
> > > len = 15, min = 4, av = 6, max = 12, prec = 106
> > > len = 20, min = 6, av = 8, max = 13, prec = 106
> > > len = 26, min = 6, av = 8, max = 12, prec = 106
> > > len = 34, min = 8, av = 11, max = 18, prec = 106
> > > len = 45, min = 9, av = 12, max = 20, prec = 106
> > > len = 59, min = 10, av = 12, max = 22, prec = 106
> > > len = 77, min = 10, av = 12, max = 17, prec = 106
> > > len = 101, min = 10, av = 13, max = 17, prec = 106
> > > len = 132, min = 13, av = 15, max = 20, prec = 106
> > > len = 172, min = 13, av = 16, max = 21, prec = 106
> > > len = 224, min = 14, av = 16, max = 22, prec = 106
> > > len = 292, min = 15, av = 17, max = 26, prec = 106
> > > len = 380, min = 16, av = 19, max = 27, prec = 106
> > > len = 494, min = 16, av = 18, max = 24, prec = 106
> > > len = 643, min = 16, av = 18, max = 24, prec = 106
> > > len = 836, min = 16, av = 18, max = 22, prec = 106
> > > len = 1087, min = 18, av = 20, max = 25, prec = 106
> > > len = 1414, min = 19, av = 21, max = 33, prec = 106
> > > len = 1839, min = 19, av = 21, max = 30, prec = 106
> > > len = 2391, min = 22, av = 24, max = 31, prec = 106
> > > len = 3109, min = 23, av = 25, max = 30, prec = 106
> > > len = 4042, min = 23, av = 25, max = 30, prec = 106
> > > len = 5255, min = 24, av = 26, max = 32, prec = 106
> > > len = 6832, min = 25, av = 27, max = 31, prec = 106
>
> > > Bill.
>
> > > On Apr 30, 12:12 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > If the coefficients are allowed to vary in sign and vary wildly in the
> > > > number of bits, then nothing will save you. Here are the figures for
> > > > classical multiplication:
>
> > > > len = 1, min = 0, av = 18, max = 79, prec = 106
> > > > len = 2, min = 0, av = 23, max = 101, prec = 106
> > > > len = 3, min = 0, av = 19, max = 98, prec = 106
> > > > len = 4, min = 0, av = 16, max = 96, prec = 106
> > > > len = 6, min = 0, av = 21, max = 85, prec = 106
> > > > len = 8, min = 0, av = 26, max = 87, prec = 106
> > > > len = 11, min = 0, av = 24, max = 80, prec = 106
> > > > len = 15, min = 0, av = 15, max = 85, prec = 106
> > > > len = 20, min = 0, av = 25, max = 91, prec = 106
> > > > len = 26, min = 0, av = 16, max = 75, prec = 106
> > > > len = 34, min = 0, av = 20, max = 104, prec = 106
> > > > len = 45, min = 0, av = 20, max = 96, prec = 106
> > > > len = 59, min = 0, av = 16, max = 71, prec = 106
> > > > len = 77, min = 0, av = 26, max = 86, prec = 106
> > > > len = 101, min = 0, av = 24, max = 93, prec = 106
> > > > len = 132, min = 0, av = 10, max = 61, prec = 106
> > > > len = 172, min = 0, av = 19, max = 88, prec = 106
> > > > len = 224, min = 0, av = 21, max = 93, prec = 106
> > > > len = 292, min = 0, av = 16, max = 93, prec = 106
> > > > len = 380, min = 0, av = 23, max = 98, prec = 106
> > > > len = 494, min = 0, av = 25, max = 106, prec = 106
> > > > len = 643, min = 0, av = 31, max = 103, prec = 106
> > > > len = 836, min = 0, av = 28, max = 89, prec = 106
> > > > len = 1087, min = 0, av = 13, max = 90, prec = 106
> > > > len = 1414, min = 0, av = 22, max = 89, prec = 106
> > > > len = 1839, min = 0, av = 15, max = 83, prec = 106
> > > > len = 2391, min = 0, av = 21, max = 82, prec = 106
>
> > > > And also for FHT:
>
> > > > len = 1, min = 0, av = 12, max = 79, prec = 106
> > > > len = 2, min = 0, av = 32, max = 108, prec = 106
> > > > len = 3, min = 0, av = 39, max = 123, prec = 106
> > > > len = 4, min = 0, av = 59, max = 145, prec = 106
> > > > len = 6, min = 10, av = 76, max = 136, prec = 106
> > > > len = 8, min = 2, av = 90, max = 175, prec = 106
> > > > len = 11, min = 5, av = 91, max = 162, prec = 106
> > > > len = 15, min = 29, av = 85, max = 160, prec = 106
> > > > len = 20, min = 14, av = 102, max = 186, prec = 106
> > > > len = 26, min = 20, av = 96, max = 162, prec = 106
> > > > len = 34, min = 11, av = 95, max = 191, prec = 106
> > > > len = 45, min = 0, av = 92, max = 189, prec = 106
> > > > len = 59, min = 10, av = 93, max = 160, prec = 106
> > > > len = 77, min = 40, av = 111, max = 179, prec = 106
> > > > len = 101, min = 44, av = 110, max = 181, prec = 106
> > > > len = 132, min = 47, av = 93, max = 156, prec = 106
> > > > len = 172, min = 19, av = 100, max = 184, prec = 106
> > > > len = 224, min = 38, av = 104, max = 186, prec = 106
> > > > len = 292, min = 13, av = 97, max = 187, prec = 106
> > > > len = 380, min = 31, av = 105, max = 192, prec = 106
> > > > len = 494, min = 27, av = 109, max = 198, prec = 106
> > > > len = 643, min = 47, av = 120, max = 198, prec = 106
> > > > len = 836, min = 13, av = 111, max = 185, prec = 106
> > > > len = 1087, min = 51, av = 96, max = 184, prec = 106
> > > > len = 1414, min = 6, av = 110, max = 184, prec = 106
> > > > len = 1839, min = 30, av = 97, max = 180, prec = 106
> > > > len = 2391, min = 30, av = 102, max = 177, prec = 106
>
> > > > Clearly, in this situation, one wants to double the precision one is
> > > > working at, at least.
>
> > > > Bill.
>
> > > > On Apr 29, 11:02 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > > I wrote a little program to compute the "exact" product of two
> > > > > polynomials with uniformly random unsigned coefficients < 2^prec for
> > > > > some precision prec. I then compute the number of bits that are
> > > > > correct in each coefficient and subtract from the
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: numerically stable fast univariate polynomial multiplication over RR[x]

As promised, here with toom cook figures, first for unsigned
coefficients all about the same magnitude:

len = 1, min = 0, av = 0, max = 0, prec = 106
len = 2, min = 0, av = 1, max = 2, prec = 106
len = 3, min = 0, av = 2, max = 6, prec = 106
len = 4, min = 0, av = 1, max = 3, prec = 106
len = 6, min = 0, av = 2, max = 6, prec = 106
len = 8, min = 1, av = 2, max = 6, prec = 106
len = 11, min = 0, av = 2, max = 6, prec = 106
len = 15, min = 0, av = 2, max = 6, prec = 106
len = 20, min = 0, av = 2, max = 5, prec = 106
len = 26, min = 0, av = 1, max = 4, prec = 106
len = 34, min = 0, av = 2, max = 6, prec = 106
len = 45, min = 0, av = 2, max = 4, prec = 106
len = 59, min = 0, av = 2, max = 6, prec = 106
len = 77, min = 0, av = 2, max = 5, prec = 106
len = 101, min = 0, av = 2, max = 4, prec = 106
len = 132, min = 0, av = 2, max = 4, prec = 106
len = 172, min = 0, av = 2, max = 7, prec = 106
len = 224, min = 0, av = 2, max = 7, prec = 106
len = 292, min = 0, av = 2, max = 5, prec = 106
len = 380, min = 0, av = 2, max = 8, prec = 106
len = 494, min = 0, av = 2, max = 4, prec = 106
len = 643, min = 0, av = 2, max = 5, prec = 106
len = 836, min = 0, av = 2, max = 4, prec = 106
len = 1087, min = 0, av = 2, max = 5, prec = 106
len = 1414, min = 0, av = 2, max = 7, prec = 106
len = 1839, min = 0, av = 2, max = 6, prec = 106
len = 2391, min = 0, av = 2, max = 5, prec = 106
len = 3109, min = 0, av = 1, max = 4, prec = 106
len = 4042, min = 0, av = 2, max = 7, prec = 106
len = 5255, min = 0, av = 2, max = 5, prec = 106

Bill.


On Apr 30, 8:30 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
> And finally, the figures for Rader-Brennan for signed coefficients
> whose magnitudes also vary wildly: as with FHT, on average, no usable
> information results. No FFT algorithm will be of use in that
> situation. Joris vdH's algorithm is your only hope.
>
> After dinner, figures for Karatsuba and Toom Cook. I think there may
> be a surprise in store for us there....
>
> len = 1, min = 0, av = 5, max = 74, prec = 106
> len = 2, min = 5, av = 36, max = 106, prec = 106
> len = 3, min = 1, av = 46, max = 124, prec = 106
> len = 4, min = 2, av = 63, max = 170, prec = 106
> len = 6, min = 13, av = 79, max = 140, prec = 106
> len = 8, min = 4, av = 95, max = 180, prec = 106
> len = 11, min = 8, av = 95, max = 164, prec = 106
> len = 15, min = 31, av = 89, max = 163, prec = 106
> len = 20, min = 17, av = 107, max = 191, prec = 106
> len = 26, min = 26, av = 101, max = 168, prec = 106
> len = 34, min = 22, av = 102, max = 199, prec = 106
> len = 45, min = 9, av = 100, max = 195, prec = 106
> len = 59, min = 19, av = 101, max = 167, prec = 106
> len = 77, min = 54, av = 119, max = 187, prec = 106
> len = 101, min = 46, av = 117, max = 190, prec = 106
> len = 132, min = 58, av = 103, max = 165, prec = 106
> len = 172, min = 27, av = 110, max = 199, prec = 106
> len = 224, min = 47, av = 113, max = 194, prec = 106
> len = 292, min = 26, av = 110, max = 203, prec = 106
> len = 380, min = 46, av = 118, max = 203, prec = 106
> len = 494, min = 38, av = 121, max = 214, prec = 106
> len = 643, min = 60, av = 132, max = 207, prec = 106
> len = 836, min = 24, av = 123, max = 198, prec = 106
> len = 1087, min = 62, av = 111, max = 201, prec = 106
> len = 1414, min = 27, av = 125, max = 199, prec = 106
> len = 1839, min = 44, av = 111, max = 194, prec = 106
> len = 2391, min = 50, av = 120, max = 192, prec = 106
>
> Bill.
>
> On Apr 30, 8:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
>
>
> > I installed Andreas Enge's mpfrcx package:
>
> >http://www.multiprecision.org/index.php?prog=mpfrcx&page=html
>
> > which just worked for me.
>
> > I took a closer look and the Rader-Brennan FFT is a complex FFT taking
> > mpcx polynomials as input. When multiplying polynomials over the
> > reals, it simply converts to complex polynomials and uses the complex
> > RB FFT.
>
> > Anyhow, this wrapper was very nice for me as it just plugged straight
> > into my existing profiling code with no modifications whatsoever!!
> > That sort of thing almost never happens.
>
> > Anyhow, here is the precision loss figures for unsigned coefficients
> > all of about the same magnitude. Looks like about 2.5-3 times the
> > precision loss of the Fast Hartley Transform:
>
> > len = 1, min = 0, av = 0, max = 1, prec = 106
> > len = 2, min = 0, av = 1, max = 3, prec = 106
> > len = 3, min = 0, av = 2, max = 12, prec = 106
> > len = 4, min = 0, av = 2, max = 8, prec = 106
> > len = 6, min = 1, av = 4, max = 9, prec = 106
> > len = 8, min = 2, av = 5, max = 12, prec = 106
> > len = 11, min = 2, av = 5, max = 9, prec = 106
> > len = 15, min = 4, av = 6, max = 12, prec = 106
> > len = 20, min = 6, av = 8, max = 13, prec = 106
> > len = 26, min = 6, av = 8, max = 12, prec = 106
> > len = 34, min = 8, av = 11, max = 18, prec = 106
> > len = 45, min = 9, av = 12, max = 20, prec = 106
> > len = 59, min = 10, av = 12, max = 22, prec = 106
> > len = 77, min = 10, av = 12, max = 17, prec = 106
> > len = 101, min = 10, av = 13, max = 17, prec = 106
> > len = 132, min = 13, av = 15, max = 20, prec = 106
> > len = 172, min = 13, av = 16, max = 21, prec = 106
> > len = 224, min = 14, av = 16, max = 22, prec = 106
> > len = 292, min = 15, av = 17, max = 26, prec = 106
> > len = 380, min = 16, av = 19, max = 27, prec = 106
> > len = 494, min = 16, av = 18, max = 24, prec = 106
> > len = 643, min = 16, av = 18, max = 24, prec = 106
> > len = 836, min = 16, av = 18, max = 22, prec = 106
> > len = 1087, min = 18, av = 20, max = 25, prec = 106
> > len = 1414, min = 19, av = 21, max = 33, prec = 106
> > len = 1839, min = 19, av = 21, max = 30, prec = 106
> > len = 2391, min = 22, av = 24, max = 31, prec = 106
> > len = 3109, min = 23, av = 25, max = 30, prec = 106
> > len = 4042, min = 23, av = 25, max = 30, prec = 106
> > len = 5255, min = 24, av = 26, max = 32, prec = 106
> > len = 6832, min = 25, av = 27, max = 31, prec = 106
>
> > Bill.
>
> > On Apr 30, 12:12 am, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > If the coefficients are allowed to vary in sign and vary wildly in the
> > > number of bits, then nothing will save you. Here are the figures for
> > > classical multiplication:
>
> > > len = 1, min = 0, av = 18, max = 79, prec = 106
> > > len = 2, min = 0, av = 23, max = 101, prec = 106
> > > len = 3, min = 0, av = 19, max = 98, prec = 106
> > > len = 4, min = 0, av = 16, max = 96, prec = 106
> > > len = 6, min = 0, av = 21, max = 85, prec = 106
> > > len = 8, min = 0, av = 26, max = 87, prec = 106
> > > len = 11, min = 0, av = 24, max = 80, prec = 106
> > > len = 15, min = 0, av = 15, max = 85, prec = 106
> > > len = 20, min = 0, av = 25, max = 91, prec = 106
> > > len = 26, min = 0, av = 16, max = 75, prec = 106
> > > len = 34, min = 0, av = 20, max = 104, prec = 106
> > > len = 45, min = 0, av = 20, max = 96, prec = 106
> > > len = 59, min = 0, av = 16, max = 71, prec = 106
> > > len = 77, min = 0, av = 26, max = 86, prec = 106
> > > len = 101, min = 0, av = 24, max = 93, prec = 106
> > > len = 132, min = 0, av = 10, max = 61, prec = 106
> > > len = 172, min = 0, av = 19, max = 88, prec = 106
> > > len = 224, min = 0, av = 21, max = 93, prec = 106
> > > len = 292, min = 0, av = 16, max = 93, prec = 106
> > > len = 380, min = 0, av = 23, max = 98, prec = 106
> > > len = 494, min = 0, av = 25, max = 106, prec = 106
> > > len = 643, min = 0, av = 31, max = 103, prec = 106
> > > len = 836, min = 0, av = 28, max = 89, prec = 106
> > > len = 1087, min = 0, av = 13, max = 90, prec = 106
> > > len = 1414, min = 0, av = 22, max = 89, prec = 106
> > > len = 1839, min = 0, av = 15, max = 83, prec = 106
> > > len = 2391, min = 0, av = 21, max = 82, prec = 106
>
> > > And also for FHT:
>
> > > len = 1, min = 0, av = 12, max = 79, prec = 106
> > > len = 2, min = 0, av = 32, max = 108, prec = 106
> > > len = 3, min = 0, av = 39, max = 123, prec = 106
> > > len = 4, min = 0, av = 59, max = 145, prec = 106
> > > len = 6, min = 10, av = 76, max = 136, prec = 106
> > > len = 8, min = 2, av = 90, max = 175, prec = 106
> > > len = 11, min = 5, av = 91, max = 162, prec = 106
> > > len = 15, min = 29, av = 85, max = 160, prec = 106
> > > len = 20, min = 14, av = 102, max = 186, prec = 106
> > > len = 26, min = 20, av = 96, max = 162, prec = 106
> > > len = 34, min = 11, av = 95, max = 191, prec = 106
> > > len = 45, min = 0, av = 92, max = 189, prec = 106
> > > len = 59, min = 10, av = 93, max = 160, prec = 106
> > > len = 77, min = 40, av = 111, max = 179, prec = 106
> > > len = 101, min = 44, av = 110, max = 181, prec = 106
> > > len = 132, min = 47, av = 93, max = 156, prec = 106
> > > len = 172, min = 19, av = 100, max = 184, prec = 106
> > > len = 224, min = 38, av = 104, max = 186, prec = 106
> > > len = 292, min = 13, av = 97, max = 187, prec = 106
> > > len = 380, min = 31, av = 105, max = 192, prec = 106
> > > len = 494, min = 27, av = 109, max = 198, prec = 106
> > > len = 643, min = 47, av = 120, max = 198, prec = 106
> > > len = 836, min = 13, av = 111, max = 185, prec = 106
> > > len = 1087, min = 51, av = 96, max = 184, prec = 106
> > > len = 1414, min = 6, av = 110, max = 184, prec = 106
> > > len = 1839, min = 30, av = 97, max = 180, prec = 106
> > > len = 2391, min = 30, av = 102, max = 177, prec = 106
>
> > > Clearly, in this situation, one wants to double the precision one is
> > > working at, at least.
>
> > > Bill.
>
> > > On Apr 29, 11:02 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
>
> > > > I wrote a little program to compute the "exact" product of two
> > > > polynomials with uniformly random unsigned coefficients < 2^prec for
> > > > some precision prec. I then compute the number of bits that are
> > > > correct in each coefficient and subtract from the precision. That
> > > > gives a measure of how many bits are "lost". I take the maximum number
> > > > of bits lost over the coefficients of the entire product polynomial. I
> > > > printed the results by length of polynomials multiplied. I give the
> > > > minimum number of bits lost, the average and the maximum, for 30
> > > > iterations in each case.
>
> > > > Here are the results for the Fast Hartley Transform multiplication.
> > > > The column prec just shows the working precision I used (of course it
> > > > doesn't significantly change the results if I change prec - the same
> > > > number of bits are lost regardless of the initial working precision):
>
> > > > len = 1, min = 0, av = 0, max = 1, prec = 106
> > > > len = 2, min = 0, av = 0, max = 3, prec = 106
> > > > len = 3, min = 0, av = 0, max = 8, prec = 106
> > > > len = 4, min = 0, av = 1, max = 10, prec = 106
> > > > len = 6, min = 0, av = 0, max = 4, prec = 106
> > > > len = 8, min = 0, av = 1, max = 8, prec = 106
> > > > len = 11, min = 0, av = 1, max = 4, prec = 106
> > > > len = 15, min = 0, av = 2, max = 7, prec = 106
> > > > len = 20, min = 0, av = 2, max = 8, prec = 106
> > > > len = 26, min = 0, av = 2, max = 7, prec = 106
> > > > len = 34, min = 0, av = 3, max = 7, prec = 106
> > > > len = 45, min = 0, av = 3, max = 11, prec = 106
> > > > len = 59, min = 0, av = 4, max = 15, prec = 106
> > > > len = 77, min = 0, av = 4, max = 10, prec = 106
> > > > len = 101, min = 1, av = 4, max = 9, prec = 106
> > > > len = 132, min = 1, av = 4, max = 8, prec = 106
> > > > len = 172, min = 3, av = 5, max = 9, prec = 106
> > > > len = 224, min = 0, av = 5, max = 10, prec = 106
> > > > len = 292, min = 3, av = 5, max = 12, prec = 106
> > > > len = 380, min = 3, av = 7, max = 16, prec = 106
> > > > len = 494, min = 3, av = 6, max = 12, prec = 106
> > > > len = 643, min = 4, av = 7, max = 14, prec = 106
> > > > len = 836, min = 4, av = 7, max = 10, prec = 106
> > > > len = 1087, min = 2, av =
>
> ...
>
> read more »

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org