Quick n-th Square of BigInteger

J

Joshua Cranmer

I was actually waiting for this troll meme: "Could you tell
us more about your application domain, we are sorry, we can't
answer your question without more context information".

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

markspace

*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;
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)
 
J

Jan Burse

markspace said:
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.
 
J

Jan Burse

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

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.
 
J

Joshua Cranmer

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.
 
J

Jan Burse

Leif said:
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
parade is still open.
 
J

Jan Burse

Joshua said:
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.
 
J

Jan Burse

Jan said:
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 <[email protected]>
3. Leif Roar Moldskred <[email protected]>
4. Joshua Cranmer <[email protected]>

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 pisser.
- A free supply of dog food for own week.

Bye
 
J

Jan Burse

Leif said:
Ah, I see you're using 0-based counting_and_ you have a fencepost
error. Very C, and not out of place in a Java newsgroup either.

There is no correspondence whatever about
the results with the jury.
 
J

Jan Burse

Joshua said:
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.

Oops, the jury forgot to honor the above troll meme: "Hi I am
junior troll, I know I lack the originality and spice of
real trolls, but I know how to use my keyboard and
can easily add to the smoke rising."
 
J

Joshua Cranmer

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

Why do you think I was trolling? I was being honest, and responding
specifically to Leif's question, which is distinct from your original
question.

Oh, because every post in this thread must be someone trolling you. Or
you complaining that you're being trolled.
 
D

Daniel Pitts

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

1. markspace <-@.>
2. Lew <[email protected]>
3. Leif Roar Moldskred <[email protected]>
4. Joshua Cranmer <[email protected]>
Hmm, most of the people on your list are welcome contributors on this
list. At times some of them get pedantic, but never trollish. Perhaps
you're confusing "helpful responses that disagree with you" with "trolling".

Or perhaps you yourself are trolling. Consider the fact that if more
people are "trolling" you than are defending you, perhaps you're not in
the right.
 
J

Jan Burse

Eric said:
BigInteger lo = BigInteger.ONE.shiftLeft(
Math.floor((x.bitCount()-1)/n));
BitInteger hi = BigInteger.ONE.shiftLeft(
Math.ceil(x.bitCount()/n));

I guess you mean bitLength() and not bitCount()
in the above. bitCount() counts the number of
non-zero bits. bitLength() gives the index of
the highest non-zero bit.

Math.floor/Math.ceil are not really needed in the
above since (int)/(int) gives anyway (int). But
I am now going for. Also correcting BitInteger
to BigInteger:

BigInteger lo = BigInteger.ONE.shiftLeft(
(x.bitLength()-1)/n);
BigInteger hi = BigInteger.ONE.shiftLeft(
(x.bitLength()+n-1)/n);

I am not yet done with testing. Bisection works
already, but would like to compare with Newton.
Here is an example run showing determination of
lo and hi:

x=1000000000
n=3
lo=512
hi=1024

Bye
 
R

Roedy Green

Anyway, the troll count goes up from 3 to 4, since I didn't
count Roedy. But your impudence deserves it.

That was uncalled for. Whether you like the answer or not, he took
time out to brainstorm with you. All he did was point out that if
one of the numbers is a constant known ahead of time it greatly
simplifies the problem. He did not try to hurt you.

When you snap at him, you suggest to everyone else that unless their
offerings please your majesty you will similarly order decapitations.
People will leave you alone fearing your wrath. You are showing
signs of pathological entitlement syndrome. Keep in mind, you are not
ENTITLED to an answer. Anything people give you is a favour.

What motivates people to answer? They are hoping something they say
will prove useful and will be acknowledged as such. Why do people
avoid answering? They don't know the answer or they fear criticism.

see http://mindprod.com/jgloss/brainstorming.html

http://mindprod.com/jgloss/newsgroups.html

http://www.amazon.com/gp/product/04...mp=1789&creative=9325&creativeASIN=0452272041




--
Roedy Green Canadian Mind Products
http://mindprod.com
Controlling complexity is the essence of computer programming.
~ Brian W. Kernighan 1942-01-01
..
 
J

Jan Burse

Roedy said:
That was uncalled for. Whether you like the answer or not, he took
time out to brainstorm with you. All he did was point out that if
one of the numbers is a constant known ahead of time it greatly
simplifies the problem. He did not try to hurt you.

@Roedy
Please don't cite the jury out of context. Here is the
full context why the jury judged the post as trolling:
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,830
Latest member
ZADIva7383

Latest Threads

Top