Sorry, I was wrong. In fact: > 3 : '6!:2 ''p*q'' [ p=: ?10x^y [ q=: ?10x^y' "0 ]100 200 400 800 > 1.35285e_5 3.40545e_5 0.000132952 0.000496822
2 %~/\ 1.35285e_5 3.40545e_5 0.000132952 0.000496822 2.51724 3.90409 3.73685 Doubling the number of digits more than doubles the time: quadratic behaviour. On Wed, Feb 3, 2021 at 1:38 PM Henry Rich <[email protected]> wrote: > But Roger, that's showing time proportional to the product of the number > of digits, while FFT should be proportional to (n log n) of the size of > the larger. I don't see the FFT in the source - I'm looking at vx.c:113. > > Henry Rich > > On 2/3/2021 3:52 PM, Roger Hui wrote: > >> The multiplication algorithm is brute-force. FFT methods are orders of > >> magnitude faster for large numbers. > > J extended precision multiplication is not brute force, as the following > > benchmark demonstrates: > > > > 3 : '6!:2 ''p*q'' [ p=: ?10x^y [ q=: ?10x^y' "0 ]100 200 400 800 > > 1.35285e_5 3.40545e_5 0.000132952 0.000496822 > > > > In fact, it uses FFT as devised by one Henry H. Rich ( > > https://code.jsoftware.com/wiki/Essays/FFT). It is however not as good > as > > GMP. > > > > > > > > On Wed, Feb 3, 2021 at 12:22 PM Henry Rich <[email protected]> wrote: > > > >> The multiplication algorithm is brute-force. FFT methods are orders of > >> magnitude faster for large numbers. > >> > >> Numbers are actually stored in base 10000 IIRC. > >> > >> Extended arithmetic is not a mainstream use, but if we support it we > >> might as well do it as well as we can. > >> > >> Henry Rich > >> > >> On 2/3/2021 3:05 PM, 'Pascal Jasmin' via Programming wrote: > >>> The core performance bottleneck with extended precision numbers in J is > >> that they are stored in base 10. That decision does come with a > >> performance advantage of its own: input and display. I'd favour the > move > >> to 32/64 bit storage even if it "broke" the 3!:1 format (although 3!:1 > >> could convert to old storage style). J is already shipping with openssl > >> that has large integer operations. Is there that big a case to add GMP > as > >> a dependency? > >>> > >>> > >>> > >>> > >>> > >>> On Wednesday, February 3, 2021, 09:47:51 a.m. EST, Henry Rich < > >> [email protected]> wrote: > >>> > >>> > >>> > >>> > >>> IF you want to get yourself in shape to make JE changes, I have a > >>> starter project for you: replace the extended-integer and rational > >>> support with GMP (or some other equally-good library). The current > code > >>> is serviceable but sized for 32-bit machines, and lacks fast > >> multiplication. > >>> The code resides in vx.c and vq.c, which would be replaced with new > >>> versions. There are also bits in k.c (conversions) and d.c (display). > >>> > >>> I will help as needed. > >>> > >>> Henry Rich > >>> > >>> On 2/1/2021 11:25 PM, ethiejiesa via Programming wrote: > >>>> Raul Miller <[email protected]> wrote: > >>>>> https://github.com/jsoftware/jsource/commits/master might interest > >> you... > >>>> Indeed, I have the repo cloned locally! > >>>> > >>>> However, when digging through old bug reports, I find it quite > >> challenging to > >>>> match up the "fixed" notices with the corresponding code commits. In > >> cases with > >>>> a clear test case demonstrating the bug, we can use git-bisect to > >> sleuth out > >>>> the commit that eliminates the failure. However, cases without this > >> almost > >>>> invariably defeat my investigative skills. > >>>> > >>>> For posterity's sake, and if it's not too much of a hassle, I thought > >> it might > >>>> be helpful to have some commits/diffs/comments attached to those > "fixed" > >>>> messages. > >>>> > >>>> I will admit to a bit of an ulterior motive here, though. > >>>> > >>>> Bill, Eric, and Henry have deep domain knowledge about JE. I am > >> personally > >>>> hoping that sharing the diffs would also spark discussion and give a > >> natural > >>>> avenue to share and spread such expertise. > >>>> > >>>> The gory details are exceptionally interesting! > >>>> > >>>> > >>>> Permit me to query a broader point, though. > >>>> > >>>> It strikes me that the git-shortlog on the repo is very short: > >>>> > >>>> $ git shortlog --summary > >>>> 6 Chris Burke > >>>> 231 Eric Iverson > >>>> 1430 HenryHRich > >>>> 1 bill > >>>> 597 bill lam > >>>> 3 cdb > >>>> 3 kbi > >>>> > >>>> For the most part, we only have 3 devs, with all of them part of the > >> old guard, > >>>> per se. Better yet, Henry has authored over 62% of all commits! > >> Granted, this > >>>> only reflects the history from 2016 onward, but my question is this: > Do > >> we have > >>>> up and coming JE hackers that can pick up the torch when the time > comes? > >>>> > >>>> > >>>> Anyway, maybe JSoftware has a vision for the future that I've failed > to > >> pick up > >>>> on. The ulterior motive behind my "share a bit about the fix" is to > >> perhaps > >>>> open a channel with the community that sucks in potential JE devs like > >> myself! > >>>> I was just trying to be sneaky about things by suggesting something > >> very simple > >>>> and, hopefully, hassle-free. > >>>> > >>>> > >>>> 2!:55 > >>>> ---------------------------------------------------------------------- > >>>> For information about J forums see > http://www.jsoftware.com/forums.htm > >> > >> -- > >> This email has been checked for viruses by AVG. > >> https://www.avg.com > >> > >> ---------------------------------------------------------------------- > >> 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 AVG. > https://www.avg.com > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
