We're back from the Pub Quiz - 4th place, so "just outside the money"
Raul asked about roundreal - it's one of the utilities in the J wiki
article on FFT multiplication:
roundreal
[: (<.) 0.5 + 9&o.
Henry wondered about dividing ffts when non-zero remainders would
exist. it seems to fail, so we
can only use it safely when assured of divisibility:
fft"1 ] 8 {."1 ] 1 5 20 10 5 1,: 1 3 3 1
42 _8.2426407j29.899495 _14j_4 0.24264069j_10.100505 10
0.24264069j10.100505 _14j4 _8.2426407j_29.899495
8 2.4142136j5.8284271 _2j2 _0.41421356j_0.17157288 0
_0.41421356j0.17157288 _2j_2 2.4142136j_5.8284271
%/fft"1 ] 8 {."1 ] 1 5 20 10 5 1,: 1 3 3 1
5.25 3.8786797j3.0208153 2.5j4.5 8.1213203j21.020815 _
8.1213203j_21.020815 2.5j_4.5 3.8786797j_3.0208153
ifft %/fft"1 ] 8 {."1 ] 1 5 20 10 5 1,: 1 3 3 1
_ __ _ __ _ __ _ __
OK - here's ctfft without the inadvertent calls to ct :
ctfft=: {{ assert.0<y
if. y = 1 do. _1 1 return. end.
'q p'=. __ q: y
if. 1=#q do.
,(y%*/q) {."0 q#1
elseif.2={.q do.
,(y%*/q) {."0 (* 1 _1 $~ #) ctfft */}.q
elseif. 1 e. 1 < p do.
,(y%*/q) {."0 ctfft */q
else.
lgl =. {:$ ctlist =. ctfft "0 }:*/@>,{1,each q NB. ctlist
is 2-d table of polynomial divisors
lgd =. # dividend =. _1,(-y){.1 NB. (x^n) -
1, and its size
lg =. >.&.(2&^.) lgl >. lgd NB. required
lengths of all polynomials for fft transforms
fftdivis=. */ fft"1 lg{."1 ctlist NB. FFT
article doesn't deal with lists of multiplicands
unpad roundreal ifft"1 fftdivis %~ fft lg{.dividend NB. similar
to FFT article's multiplication
end.
}} M.
NB. ... and crude measure of performance
NB. timer returns elpased time in minutes & seconds
timer'cyclotomic taskorderu 5' NB. before cache/memoisation
established!
┌─────────┬───────────────────┐
│1.0940018│1 105 385 1365 1785│
└─────────┴───────────────────┘
timer'ctfft taskorderu 5'
┌─────────┬───────────────────┐
│4.3660049│1 105 385 1365 1785│
└─────────┴───────────────────┘
NB. continuing with cache/memoisation as above
timer'cyclotomic taskorderu 10'
┌───────────┬─────────────────────────────────────────────┐
│4 35.623001│1 105 385 1365 1785 2805 3135 6545 6545 10465│
└───────────┴─────────────────────────────────────────────┘
timer'ctfft taskorderu 10' NB. some improvement cf cyclotomic
┌───────────┬─────────────────────────────────────────────┐
│3 58.355003│1 105 385 1365 1785 2805 3135 6545 6545 10465│
└───────────┴─────────────────────────────────────────────┘
So not much significant difference in the running times from those in my
earlier report.
Cheers,
Mike
On 01/03/2022 19:17, 'Michael Day' via Programming wrote:
Oops - ct was my memoised version of cyclotomic, while still using pDiv.
I expect the results will be much the same, but I'll have a look
later as I've
got to go out now. I'll have to replace ct by ctfft - perhaps you'd
like to try
while I'm pub-quizzing!
Cheers,
Mike
On 01/03/2022 19:02, Raul Miller wrote:
Ah, I had forgotten about that bit of code. Thanks.
Next question:
What is 'ct' here?
Thanks again,
--
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
