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
