Hi, This lost the dev@commons in the to address. I am forwarding to the list to include the history.
On Sun, 20 Mar 2022 at 16:49, Sumanth Rajkumar <rajkumar.suma...@gmail.com> wrote: > Thanks for the feedback Alex! > > As suggested, I reviewed the JTransforms and ComplexUtils class in the > complex streams package. > > The existing complex utils class has methods to convert to and from Array > data structures (the forms used in JTransform) to Complex class. > > I can come up with a Java 8/Streams based API for implementing complex > FFT algorithms of the types in JTransforms and support various methods in > ComplexUtils > The streams based complex operations API should allow for decoupling the > backing data structures. > This should make it possible to use single API to create an unit test > suite to benchmark/compare different backing data structures such as single > arrays, floats or even polar representations > > As part of the project, I could implement a subset of the FFT operations > in JTransform using the new streams based Complex Numbers API and > benchmark it against JTransform implementation > > > I understand that we are in the GSOC discussion phase. I am trying to > understand the background of this project and the requirements in order to > come up with my GSOC proposal > > Can you provide with more information on the envisaged usage of > Commons-Numbers (especially Complex Numbers), its current usage/users and > the vision/roadmap for future enhancements > > Are we expecting complex-numbers to be an efficient pure java library that > could be used by other java libraries such as commons-imaging for data > compression (DCT /JPEG lossy compression)? > > Are there other Java/Non-Java (C/Python) libraries that provide similar > features that I can look into for design inspiration and also benchmark > Complex Numbers with? > > Thanks > Sumanth > > > On Tue, 15 Mar 2022 at 20:50, Alex Herbert <alex.d.herb...@gmail.com> > wrote: > >> Hi Sumanth, >> >> These changes to use static methods with functional interfaces is an >> improvement. However I would advise that we consider the use cases for this >> functionality to ensure that any design does not prevent extension and also >> allows full flexibility to achieve various tasks. >> >> For example: >> >> - multiply all the complex numbers in one list with another >> - wrap an existing complex number data structure, for example the FFT >> result produced by JTransforms [1] >> >> This project originates from a previous enhancement request that was made >> to store a large set of complex numbers efficiently. The argument was that >> the 16 bytes to store 2 doubles is inflated by the object allocation to >> store a Complex, perhaps by even double the 16 bytes. The natural storage >> would be two arrays of doubles, but what about 1 linear array packed as >> real/imag for each number. This will be able to store half as many numbers >> but access to each will take advantage of efficient caching when >> reading/writing memory. The JTransforms library (and others) may have ideas >> for useful data structures. >> >> Unfortunately I cannot find if there was a Jira ticket for this or it is >> only in the mailing archives. I've added links to the GSoC ticket for the >> other tickets that mention complex number array utils and streams. However >> these do not have a use case. Perhaps an investigation of the functionality >> in the unreleased commons-number-complex-streams package would be the place >> to start. The original author of that package is not actively involved in >> the development any more. >> >> I should also point out the process for GSoC. It is outlined here [2]. In >> short the initial period is about understanding what a project may involve. >> Then you create a proposal for the project that is ranked with all the >> other potential coders. Some projects are selected. It is only then that >> the formal coding process begins and you have 12 weeks to create some code. >> Previous years have had a timeline but this year the only date on the info >> page is April 4 - 19 for when applications open. So right now we are in the >> discussion phase. Any code developed now technically cannot be part of >> GSoC, although this is not strictly enforced. >> >> Regards, >> >> Alex >> >> [1] https://github.com/wendykierp/JTransforms >> [2] https://summerofcode.withgoogle.com/how-it-works >> >> >> On Tue, 15 Mar 2022 at 02:23, Sumanth Rajkumar < >> rajkumar.suma...@gmail.com> wrote: >> >>> Hi Alex/Gilles >>> >>> Thank you both for the detailed review. I think I have a better >>> understanding now. >>> >>> 1) Refactor using Functional Interfaces and move current instance >>> methods to static methods >>> >>> As suggested, I have attempted to refactor the Complex class to extract >>> the functions out to static methods and use Functional interfaces >>> >>> I have added following Complex Functional interfaces similar to >>> Functions and Operators defined in java.util.function but only using >>> primitive doubles and avoiding any Object creation overheads >>> >>> @FunctionalInterface >>> public interface ComplexFunction { >>> <R> R apply(double r, double i, ComplexResult<R> result); >>> } >>> >>> @FunctionalInterface >>> public interface ComplexBiFunction { >>> <R> R apply(double r1, double i1, double r2, double i2, >>> ComplexResult<R> result); >>> } >>> >>> >>> @FunctionalInterface >>> public interface ComplexResult<R> { >>> R apply(double r, double i); >>> default <V> ComplexResult<V> andThen(Function<? super R, ? extends >>> V> after) { >>> Objects.requireNonNull(after); >>> return (r, i) -> after.apply(apply(r, i)); >>> } >>> default ComplexResult<R> compose(ComplexFunction before) { >>> Objects.requireNonNull(before); >>> return (r, i) -> before.apply(r, i, (x, y) -> apply(x, y)); >>> } >>> } >>> >>> >>> >>> I have refactored a few Functions (exp, conj, asin) and a few >>> BFunctions (multiply, divide) as static functions into a new >>> ComplexFunctions class >>> >>> I have modified the existing implementations for above in the Complex >>> class to use the new static functions using the new Function interfaces >>> >>> I have also refactored ComplexList to apply the above function >>> interfaces in forEach methods as suggested. These apply the results in >>> place without incurring object overheads >>> >>> Refactored source is available here for review >>> >>> https://github.com/sumanth-rajkumar/commons-numbers/tree/sumanth-gsoc-22/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex >>> >>> Please let me know if the above changes are on expected lines? >>> >>> 2) List Implementation >>> >>> Thanks for the feedback on the license issue. I should be able >>> refactor this as suggested just using the javadoc specifications >>> >>> >>> -Sumanth. >>> >>> >>> On Sun, 13 Mar 2022 at 21:39, Alex Herbert <alex.d.herb...@gmail.com> >>> wrote: >>> >>>> Hi, >>>> >>>> Thanks for your interest in Commons Numbers. >>>> >>>> On Mon, 14 Mar 2022 at 00:09, Gilles Sadowski <gillese...@gmail.com> >>>> wrote: >>>> >>>> > > >>>> > > My partial implementation (with TODOs for many operations) is >>>> available >>>> > > here. >>>> > > >>>> > >>>> https://github.com/sumanth-rajkumar/commons-numbers/blob/sumanth-gsoc-22/commons-numbers-complex/src/main/java/org/apache/commons/numbers/complex/ComplexList.java >>>> >>>> >>>> Thanks for the implementation idea. This is a literal implementation of >>>> a >>>> List<Complex>. I think we should take a step back and find use cases >>>> for a >>>> large set of complex numbers. That should drive the API design. >>>> >>>> For example a common operation with complex numbers is to conjugate >>>> multiply the fast fourier transform of two data arrays. The conjugate >>>> multiply in the frequency domain is equivalent to the correlation in the >>>> spatial domain. So I would require: >>>> >>>> ComplexList a; >>>> ComplexList b; >>>> >>>> a.conj().multiply(b); >>>> >>>> But what is the most appropriate method to do this? I do not think we >>>> want >>>> to implement full matrix functionality for multiplication of arrays. >>>> But we >>>> should allow an API that makes this type of work efficient in terms of >>>> memory usage, i.e. zero object allocation during computation (avoid >>>> creating Complex instances) and ideally no intermediate array >>>> allocation. >>>> So in the above I do not want to create an entire list of conjugates >>>> before >>>> multiplying by another complex number. I also want the option to write >>>> to a >>>> new array or back to the original one. >>>> >>>> So should we have some type of generic interface for an operation on a >>>> Complex: >>>> >>>> interface ComplexFunction { >>>> interface ComplexResult { >>>> void complex(double real, double imag); >>>> } >>>> void apply(double re, double im, ComplexResult); >>>> } >>>> >>>> Then a list to allow operations on elements in place. For example to >>>> compute the conjugate: >>>> >>>> ComplexList a; >>>> a.forEach((re, im, result) -> result.complex(re, -im)); >>>> >>>> All operations in the Complex class can be rewritten as static methods >>>> using a minimal set of functional interfaces. >>>> >>>> static void conj(double re, double im, ComplexResult result) { >>>> result.complex(re, -im); >>>> } >>>> >>>> The operation then becomes: >>>> >>>> ComplexList a; >>>> a.forEach(Complex::conj); >>>> >>>> Which is a bit less cumbersome to write. >>>> >>>> Operations could be chained using a 'andThen' method in the interface: >>>> >>>> ComplexList a; >>>> a.forEach(((ComplexFunction) Complex::conj).andThen(Complex::sin)); >>>> >>>> I've not considered exactly how this will work in practice. >>>> >>>> Functions that convert to a real number (such as abs()) could write 0 to >>>> the imaginary. >>>> >>>> The specifics will depend on all the operations in Complex. So a start >>>> point may be to refactor the class to expose all the instance methods as >>>> static methods that take input and write the result to a destination. >>>> These >>>> can be used by (all) the Complex instance methods. I say (all) as some >>>> may >>>> be more efficient to leave as is, namely the simple methods like negate >>>> or >>>> conjugate, and the operations with real numbers. >>>> >>>> Re: Your code implementation >>>> >>>> I notice that the implementation for the expandable array backed list >>>> and >>>> hash code generation are "heavily reliant" on the JDK (11?) source for >>>> ArrayList and Arrays. It is good practice to be aware of the license >>>> terms >>>> of any open source code project you may wish to use. The Oracle Open >>>> JDK license terms are here [1]. This is under the GNU GPL v2 license >>>> which >>>> is not permissible to be used in an ASF project [2]. In general it is >>>> fine >>>> to look at the JDK source code to see how the function works or find >>>> bugs. >>>> However any new code reimplementing the functionality should be done as >>>> if >>>> blind to the code and only using a contractual specification of what the >>>> code is meant to do. The modern javadoc effort by the JDK tries to >>>> provide >>>> a very good specification of each method contract. So it is often >>>> possible >>>> to write the same function from the javadoc description. An ideal >>>> javadoc >>>> should have this as its goal. Effectively this would be someone telling >>>> you >>>> what the code does but not showing you how: >>>> >>>> 1. A default array size of 10 >>>> 2. Backing array will grow using a factor of 50% up to the maximum array >>>> size >>>> 3. Overflow of the maximum array size will result in OutOfMemoryError >>>> 4. Index operations outside of the current list size [0, size) will >>>> throw >>>> ArrayIndexOutOfBoundException >>>> 5. etc >>>> >>>> Alex >>>> >>>> [1] http://openjdk.java.net/legal/gplv2+ce.html >>>> [2] https://www.apache.org/legal/resolved.html#category-x >>>> >>>
