Re: Quick n-th Square of BigInteger
On 6/9/2012 10:44 AM, Leif Roar Moldskred wrote:
*shrugs* Which algorithm you should use depends on the purpose you
need to use it for. What constraints are you working under? Which
factor has highest priority? Average speed, worst-case speed,
accuracy, precision, memory footprint, degree of parallism, time of
development, ease of maintenance?
To illustrate this, I had a prototype working about 30 to 40 minutes I
first answered Jan's question. It seems to converge quickly and run
correctly, and in many cases I'd guess it's fast enough, no need to
optimize more.
Now of course I'm unwilling to post the full code. Jan can do his own
coding. But here's the driver and output.
static BigInteger[] testVectors = {
new BigInteger( "1" ), new BigInteger( "1" ),
new BigInteger( "2" ), new BigInteger( "4" ),
new BigInteger( "3" ), new BigInteger( "9" ),
new BigInteger( "4" ), new BigInteger( "16" ),
};
public static void main(String[] args) {
for ( int i = 0; i < testVectors.length; i+=2 ) {
BigInteger root = nthRoot( testVectors[i+1], 2 );
BigInteger expected = testVectors[i];
if( root.compareTo( expected ) != 0 ){
throw new AssertionError( "Expected " + expected +
", got "+root );
}
}
System.out.println("All passed.");
for( int i = 1; i <= 10 ; i++ ) {
System.out.println( "root( 100, "+i+") = "+nthRoot(
new BigInteger( "100" ), i ) );
}
for( int i = 1; i <= 10 ; i++ ) {
System.out.println( "root( 1000000000000000, "+i +
") = "+nthRoot(
new BigInteger( "1000000000000000" ), i ) );
}
}
run:
All passed.
root( 100, 1) = 100
root( 100, 2) = 10
root( 100, 3) = 4
root( 100, 4) = 3
root( 100, 5) = 2
root( 100, 6) = 2
root( 100, 7) = 1
root( 100, 8) = 1
root( 100, 9) = 1
root( 100, 10) = 1
root( 1000000000000000, 1) = 1000000000000000
root( 1000000000000000, 2) = 31622776
root( 1000000000000000, 3) = 100000
root( 1000000000000000, 4) = 5623
root( 1000000000000000, 5) = 1000
root( 1000000000000000, 6) = 316
root( 1000000000000000, 7) = 138
root( 1000000000000000, 8) = 74
root( 1000000000000000, 9) = 46
root( 1000000000000000, 10) = 31
BUILD SUCCESSFUL (total time: 0 seconds)