Henry Rich wrote:
>
> The code I posted on the Wiki is for understanding, not for performance
> measurement. Several improvements are possible:
>
> 0. The code recomputes roots of _1 (4 times!) every time it runs; a
> serious implementation would reuse the roots
> 1. The final pass, which produces an imaginary-only result, would be
> replaced by a step to halve the size of the final FFT, which would save
> 25% overall
> 2. You would just use the fftw library anyway, which is optimized
> already and is a few times faster
>
> The important point, to me, is that this in an O(*^.) algorithm. It can
> feasibly multiply polynomials of a million terms, or numbers with
> millions of digits.
>
> I wanted to see whether it would work as well as the literature
> suggests, and I think the answer is Yes. I also wondered whether Roger
> should use something like that for multiplication of extended integers,
> and I think the answer is Yes to that too, though for all I know he's
> already doing it.
>
I've been writing for a month or so an implementation of J in clisp
implementation of Common LISP---it's not optimized at the present
and of course implements only a fraction of J. A week ago I noticed
to my surprise that calculation of factorials runs very fast with bigints,
like considerably faster than in J. For instance:
In J I get:
6!:2'*/1+i.1000x'
0.010803
6!:2'*/1+i.10000x'
1.30181
6!:2'*/1+i.100000x'
551.969
while my mini-implementation of J gets:
*/1+i.1000
Real time: 0.011673 sec.
Run time: 0.0 sec.
[...]
*/1+i.10000
Real time: 0.256211 sec.
Run time: 0.25 sec.
[...]
*/1+i.100000
Real time: 37.007885 sec.
Run time: 36.99 sec.
[...]
Multiplication of bigints is done in clisp through CLN library
of Bruno Haible.
> I haven't looked at your obta.
>
> I question your use of tm*sz as a figure of merit. If I am willing to
> trade space for time I am happy to take 3x the space in 0.5x the time.
> That is especially true here, where any operands that are big enough to
> cause a memory problem would take days for the computation.
>
> Henry Rich
>
> On 12/30/2010 1:58 AM, R.E. Boss wrote:
>>> -----Oorspronkelijk bericht-----
>>> Van: [email protected] [mailto:programming-
>>> [email protected]] Namens Henry Rich
>>> Verzonden: dinsdag 28 december 2010 18:42
>>> Aan: Programming forum
>>> Onderwerp: Re: [Jprogramming] Convolution using FFT WAS: Proposal for
>>> special code voor dyadic f/.@:(g/)
>>>
>>> OK, all these suggestions are now in
>>>
>>> http://www.jsoftware.com/jwiki/Essays/FFT
>>>
>>> Henry Rich
>>>
>>
>> Some observations.
>>
>> 'X Y'=. 8192 8193<@(?...@$)"(0) 1000
>> rank'iconvolve~ X';'iconvolve~ Y'
>> +----+-----+----+----+
>> |rank|tm*sz|time|size|
>> +----+-----+----+----+
>> | 0 |1.00 |1.00|1.00|
>> +----+-----+----+----+
>> | 1 |5.22 |2.61|2.00|
>> +----+-----+----+----+
>> NB. jump in performance at 2^n
>>
>> 'X Y' =. 2 400 ?...@$ 1000x
>> datatype&> X;Y;(X +/ obta * Y);X iconvolve Y
>> extended
>> extended
>> extended
>> integer
>> NB. no extended output
>>
>> 'X Y' =. 2 8192 ?...@$ 1000
>> rank'X +/ obta * Y';'X iconvolve Y'
>> +----+-----+----+----+
>> |rank|tm*sz|time|size|
>> +----+-----+----+----+
>> | 0 |1.00 |6.49|1.00|
>> +----+-----+----+----+
>> | 1 |1.36 |1.00|8.83|
>> +----+-----+----+----+
>> NB. fast, not lean
>>
>> 'X Y' =. 2 8193 ?...@$ 1000
>> rank'X +/ obta * Y';'X iconvolve Y'
>> +----+-----+----+-----+
>> |rank|tm*sz|time|size |
>> +----+-----+----+-----+
>> | 0 |1.00 |2.69| 1.00|
>> +----+-----+----+-----+
>> | 1 |6.56 |1.00|17.65|
>> +----+-----+----+-----+
>> NB. overall less efficient
>>
>> 'X Y' =. 8000 9000<@(?...@$)"(0) 1000
>> rank'X +/ obta * Y';'X iconvolve Y'
>> +----+-----+----+-----+
>> |rank|tm*sz|time|size |
>> +----+-----+----+-----+
>> | 0 | 1.00|2.58| 1.00|
>> +----+-----+----+-----+
>> | 1 |13.26|1.00|34.15|
>> +----+-----+----+-----+
>> NB. especially for arbitrary input
>>
>> 'X Y' =. 2 16384 ?...@$ 1000
>> rank'X +/ obta * Y';'X iconvolve Y'
>> +----+-----+----+----+
>> |rank|tm*sz|time|size|
>> +----+-----+----+----+
>> | 1 |1.41 |9.40|1.00|
>> +----+-----+----+----+
>> | 0 |1.00 |1.00|6.65|
>> +----+-----+----+----+
>> NB. finally more efficient
>>
>> 'X Y' =. 16000 17000<@(?...@$)"(0) 1000
>> rank'X +/ obta * Y';'X iconvolve Y'
>> +----+-----+----+-----+
>> |rank|tm*sz|time|size |
>> +----+-----+----+-----+
>> | 0 |1.00 |4.13| 1.00|
>> +----+-----+----+-----+
>> | 1 |5.14 |1.00|21.21|
>> +----+-----+----+-----+
>> NB. However ...
>>
>> If f/.@:(g/) would be replaced by special code like obta, figures would
>> be
>> even (slightly?) more in favor of obta.
>>
>>
>> R.E. Boss
>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
--
View this message in context:
http://old.nabble.com/Poposal-for-special-code-voor-dyadic-f-.%40%3A%28g-%29-tp30535574s24193p30560404.html
Sent from the J Programming mailing list archive at Nabble.com.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
