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
