Just checked on the laptop running J903:
Performance not too bad for largish orders, even with extended type,
albeit only
binomial coefficients:
ts'1000 diva&binc 20' NB. presumably overflow in binc
|NaN error: diva
| d=.(ly{.x) -&}.r*y
ts'1000x diva&binc 20x'
0.2399954 1570560
ts'1000x diva&binc 500x'
1.9407032 3000544
ts'1000x div&binc 20x'
0.7021009 3948608
ts'1000x div&binc 500x'
2.1598005 4815264
... and dbho still suffers a domain error for somewhat smaller inputs,
such as here:
ts'50 dbho&binc 20'
|domain error: dbho
| (d{.x) %.(2#d=.<./$M){.M=.y+/ .*y bq x
I forgot to demonstrate that the remainders work as hoped:
E =. 1 5 10 10 7 4
E {{ x - y mul x div y }} 1 2 1
0 0 0 0 2 3
divlo
div&.:|.
(|.E) {{ x - y mul x divlo y }} 1 2 1
3 2 0 0 0 0
Mike
On 20/02/2022 11:31, 'Mike Day' via Programming wrote:
This approach, from my A-level Maths perhaps, seems far too simple compared
to that of the article, but works, on this iPad running J701 (no, it can’t run
Ian’s J902!), including when dbho or dblo throws a domain error for, eg,
dividing order 50 by order 30. I haven’t tried in J903 on the laptop yet.
BTW, I couldn’t understand why the article shows a remainder,
]q=. e dbho c 1 3 3 1
]r=.e-c t q 0 0 0 0 2 3
But I realised there’s a missing definition, eg E =. 1 5 10 10 7 4, with e
replaced by E in the next 2 lines.
Anyway,
NB. binomial coefficients for (1+z)^y
binc =: !~i.@>:
NB. x % y
div =: 3 : 0 NB. similar result to Ken's dbho
:
q =. ''
yx=. y,:x
n =. 2 + x -&# y
while. n =. <: n do.
q =. q, r =. %~/ {."1 yx
yx =. y,: }. -~/ yx * r,1
end.
q
)
divlo =: div&.:|. NB. Like Ken's dblo
diva =: 3 : 0 NB. a bit less elegant. Similar performance
:
q =. ''
n =. 2 + x -&# y
ly=. #y
while. n =. <: n do.
q =. q, r =. x %&{. y
if. |r do.
d =. (ly{.x) -&}. r * y
x =. d, ly}.x
else.
x =. }. x
end.
end.
q
)
5 div&binc 3
1 2 1
5 div&binc 2
1 3 3 1
ts
6!:2 , 7!:2@]
ts'50 diva&binc 10'
0.000554 9216
ts'50 div&binc 10'
0.000661 13824
ts'50 dbho&binc 10'
0.002024 211840
ts'50 dbho&binc 30'
|domain error: dbho
| (d{.x) %.(2#d=.<./$M){.M=.y+/ .*y bq x
I slightly prefer div to diva.
Cheers,
Mike
Sent from my iPad
On 20 Feb 2022, at 03:46, Raul Miller <rauldmil...@gmail.com> wrote:
https://code.jsoftware.com/wiki/Essays/Polynomial+Division
Iverson's method for polynomial division is elegant, but it's a bit
slow for large polynomials (order greater than 2000).
Does anyone have a more efficient approach? Or is this one of those
situations where it doesn't get any better?
Thanks,
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
--
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
