Velocity Reviews > Java > Quick n-th Square of BigInteger

Quick n-th Square of BigInteger

Joshua Cranmer
Guest
Posts: n/a

 06-09-2012
On 6/9/2012 10:54 AM, Jan Burse wrote:
> Leif Roar Moldskred schrieb:
>> Jan Burse <(E-Mail Removed)> wrote:
>>> Dear All,
>>>
>>> What is your favorite algorithm to compute the n-th Square of
>>> a BigInteger, i.e.

>>
>> Whichever algorithm happens to be the best suited to the specific
>> context the problem occurs in, of course.
>>

>
> I was actually waiting for this troll meme: "Could you tell
> us more about your application domain, we are sorry, we can't

I saw it more as a sarcastic response. Of course, why attribute it to
sarcasm when you can attribute it to malice?

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

markspace
Guest
Posts: n/a

 06-09-2012
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, = 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, = 74
root( 1000000000000000, 9) = 46
root( 1000000000000000, 10) = 31
BUILD SUCCESSFUL (total time: 0 seconds)

Jan Burse
Guest
Posts: n/a

 06-09-2012
markspace schrieb:
> To illustrate this, I had a prototype working about 30 to 40 minutes I

@markspace, @Leif
Sorry, won't count a troll more than once. Even if
you show a very artistic trolling, each troll is
only counted once. And there is no jury on the beauty
of the trolling. But I must admit it gets better and better.

So please make space markspace for other trolls,
please get a life Leif there are other trolls probably
waiting. We want to see the full parade here. Use an
alternate e-mail address when you want to see the count
increase.

Jan Burse
Guest
Posts: n/a

 06-09-2012
Joshua Cranmer schrieb:
> I saw it more as a sarcastic response. Of course, why attribute it to
> sarcasm when you can attribute it to malice?

Oops, sorry Cranmer can't count you as a troll.
Although there is no jury on the beauty of a trolling,
a minimal artistic level is required. Somehow the
above comment lacks a certain intimidation coupled with
plain stupidity, it is too rational.

markspace
Guest
Posts: n/a

 06-09-2012
On 6/9/2012 12:13 PM, Jan Burse wrote:
> markspace schrieb:
>> To illustrate this, I had a prototype working about 30 to 40 minutes I

>
> @markspace, @Leif
> Sorry, won't count a troll more than once.

Why not? I count each post you make.

Jan Burse
Guest
Posts: n/a

 06-09-2012
markspace schrieb:
>
> Why not? I count each post you make.

The jury does not accept presents neither
will it change its mind by compliments.
Sorry, nice try.

Joshua Cranmer
Guest
Posts: n/a

 06-10-2012
On 6/9/2012 1:44 PM, Leif Roar Moldskred wrote:
> There's no use to have a "favorite algorithm" decoupled from
> context.. Quicksort is a nice sorting algorithm, by all means, but
> sometimes -- admittedly very rarely -- the right choice is nonetheless
> bubblesort.

Well, I believe Knuth once said that bubblesort has nothing to recommend
it except some interesting math problems.

I tend to use heapsort or insertion sort pretty exclusively if I have to
code a sort by hand.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

Jan Burse
Guest
Posts: n/a

 06-10-2012
Leif Roar Moldskred schrieb:
> There's no use to have a "favorite algorithm"
> decoupled from context..

Anyway, for those who didn't recognize the troll
meme here: "When you ask for favorite algorithm,
you must sure ask for favorite in the absolute,
and not in the relative, which nobody can answer".

Suppose I am asking what is you favorite holiday
resort. Of course a normal person can answer
in winter I usually go to ... and in summer I
usually go to .... But trolls are not normal
persons.

Trolls are so special. They are close to broken
search engines. If a question is not already
narrowed down so that only two or three answers
are possible, they fail with a result overflow.
Trolls are very limited, I guess the limit is
five search hits or so before they need reboot.

But sorry the troll count doesn't change,
since I counted you already. But the troll

Jan Burse
Guest
Posts: n/a

 06-10-2012
Joshua Cranmer schrieb:
> Well, I believe Knuth once said that bubblesort has nothing to recommend
> it except some interesting math problems.
>
> I tend to use heapsort or insertion sort pretty exclusively if I have to
> code a sort by hand.

@Cranmer
Ok, if you insists, the troll count goes up to
5 for irrelevant bla bla. Great you did it.

Jan Burse
Guest
Posts: n/a

 06-10-2012
Jan Burse schrieb:
> Dear All,
>
> What is your favorite algorithm to compute the n-th Square of
> a BigInteger, i.e.
>
> Given: x, n
> Compute: y = max { z | z^n =< x }
>
> Bye

I guess it is time to close the troll parade. The
appearance of trolls was in the following order:

1. markspace <-@.>
2. Lew <(E-Mail Removed)>
3. Leif Roar Moldskred <(E-Mail Removed)>
4. Joshua Cranmer <(E-Mail Removed)>

According to the articles of association of the
jury, the winner will be the troll that first
appeared. Which makes the whole troll parade
unnecessary, but it was nevertheless a nice
display. So the winner is:

1. markspace <-@.>

Since the first troll is like a dog marking a
corner and then alllowing the herd of other dogs
to follow, the winner will receive:

- A certificate attesting that he is a prompt ****er.
- A free supply of dog food for own week.

Bye