Java custom numeric interface - square root

Question

The question is on the strategy approach to the problem of defining a square root algorithm in a generic numerical interface. I am aware of the existance of algorithms solving the problem with different conditions. I'm interested in algorithms that:

• Solves the problem using only selected functions;
• Doesn't care if the objects manipulated are integers, floating points or other, provided those objects can be added, mutiplied and confronted;
• Returns an exact solution if the input is a perfect square.

Because the subtlety of the distintion and for the sake of clarity, I will define the problem in a very verbose way. Beware the wall text!

---

Suppose to have a Java Interface Constant<C extends Constant<C>> with the following abstract methods, that we will call base functions:

• C add(C a);
• C subtract(C a);
• C multiply(C a);
• C[] divideAndRemainder(C b);
• C additiveInverse();
• C multiplicativeInverse();
• C additiveIdentity();
• C multiplicativeIdentity();
• int compareTo(C arg1);

Is not known if C represents an integer or a floating point, nor this must be relevant in the following discussion.

Using only those methods is possible to create static or default implementation of some mathematical algorithm regarding numbers: for example, dividerAndRemainder(C b); and compareTo(C arg1); allow to create algorithms for the greater common divisor, the bezout identity, etc etc...

Now suppose our Interface has a default method for the exponentiation:

public default C pow(int n){
    if(n <  0) return this.additiveInverse().pow(-n);
    if(n == 0) return additiveIdentity();
    int m = n;
    C output = this;
    while(m > 1)
        {
        if(m%2 == 0)  output = output.multiply(output);
        else          output = this.multiply(output.multiply(output));
        m = m/2;
        }
    return output;
    }

The goal is to define two default method called C root(int n) and C maximumErrorAllowed() such that:

• x.equals(y.pow(n)) implies x.root(n).equals(y);
• C root(int n); is actually implemented using only base functions and methods created from the base functions;
• The interface can still be applied to any kind of numbers, including but not limiting at both integers and floating points.
• this.root(n).pow(n).compareTo(maximumErrorAllowed()) == -1 for all this such that this.root(n)!=null, i.e. any eventual approximation has an error minor than C maximumErrorAllowed();

Is that possible? If yes, how and what would be an estimation of the computational complexity?

Answer 1

I went through some time working on a custom number interface for Java, it's amazingly hard--one of the most disappointing experiences I've had with Java.

The problem is that you have to start over from scratch--you can't really re-use anything in Java, so if you want to have implementations for int, float, long, BigInteger, rational, Complex and Vector you have to implement all the methods yourself for every single class, and then don't expect the Math package to be of much help.

It got particularly nasty implementing the "Composed" classes like "Complex" which is made from two of the "Generic" floating point types, or "Rational" which composes two generic integer types.

And math operators are right out--this can be especially frustrating.

The way I got it to work reasonably well was to implement the classes in Java and then write some of the higher-level stuff in Groovy. If you name the operations correctly, Groovy can just pick them up, like if your class implements ".plus()" then groovy will let you do instance1+instance2.

IIRC because of being dynamic, Groovy often handled cross-class pieces nicely, like if you said Complex + Integer you could supply a conversion from Integer to complex and groovy would promote Integer to Complex to do the operation and return a complex.

Groovy is pretty interchangeable with Java, You can usually just rename a Java class ".groovy" and compile it and it will work, so it was a pretty good compromise.

This was a long time ago though, now you might get some traction with Java 8's default methods in your "Number" interface--that could make implementing some of the classes easier but might not help--I'd have to try it again to find out and I'm not sure I want to re-open that can o' worms.

Answer 2

Is that possible? If yes, how?

In theory, yes. There are approximation algorithms for root(), for example the n-th root algorithm. You will run into problems with precision, however, which you might want to solve on a case-by-case basis (i. e. use a look-up table for integers). As such, I'd recommend against a default implementation in an interface.

What would be an estimation of the computational complexity?

This, too, is implementation varies based on your type of number, and is dependant on your precision. For integers, you can create an implementation with a look-up table, and the complexity would be O(1).

If you want a better answer for the complexity of the operation itself, you might want to check out Computational complexity of calculating the nth root of a real number.