Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #15105 > unrolled thread

Quick n-th Square of BigInteger

Back to article view | Back to comp.lang.java.programmer

Contents

  Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 21:03 +0200
    Re: Quick n-th Square of BigInteger Gene Wirchenko <genew@ocis.net> - 2012-06-08 13:34 -0700
      Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 22:36 +0200
        Re: Quick n-th Root of BigInteger markspace <-@.> - 2012-06-08 13:55 -0700
          Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 21:06 +0000
            Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:21 +0200
          Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:34 +0200
            Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:43 -0700
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:47 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:55 -0700
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:00 +0200
                    Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:10 -0700
                      Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:12 +0200
                        Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 15:18 -0700
              Re: Quick n-th Root of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 22:59 +0000
                Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:05 +0200
              Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:00 +0200
                Re: Quick n-th Root of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 16:15 -0700
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:51 +0200
                  Re: Quick n-th Root of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 02:32 +0200
    Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:00 +0200
    Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:04 -0400
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:19 +0200
        Re: Quick n-th Square of BigInteger Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-08 17:40 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-08 23:43 +0200
            Re: Quick n-th Square of BigInteger Lew <lewbloch@gmail.com> - 2012-06-08 14:52 -0700
              Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:30 +0200
                Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:05 +0000
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-11 14:53 +0200
    Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-08 15:32 -0700
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:37 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 00:39 +0200
        Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:34 +0000
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:44 +0200
            Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-09 01:06 +0000
      Re: Quick n-th Square of BigInteger glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-06-08 23:25 +0000
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 01:29 +0200
      Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:00 +0200
    Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 08:42 -0500
      Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 16:54 +0200
        Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 17:56 +0200
          Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:52 -0500
        Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 12:55 -0400
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:23 +0200
        Re: Quick n-th Square of BigInteger Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-09 12:44 -0500
          Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 11:50 -0700
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:13 +0200
              Re: Quick n-th Square of BigInteger markspace <-@.> - 2012-06-09 12:25 -0700
                Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-09 21:29 +0200
          Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-09 21:27 -0400
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:08 +0200
              Re: Quick n-th Square of BigInteger Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:23 -0400
            Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:31 +0200
              Re: Quick n-th Square of BigInteger Wanja Gayk <brixomatic@yahoo.com> - 2012-06-17 15:11 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:04 +0200
        Re: Quick n-th Square of BigInteger Roedy Green <see_website@mindprod.com.invalid> - 2012-06-16 17:45 -0700
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:17 +0200
          Re: Quick n-th Square of BigInteger Jan Burse <janburse@fastmail.fm> - 2012-06-17 03:38 +0200
    Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:31 +0200
      Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 12:35 +0200
      Re: Troll Parade Closing, Award Ceremony Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-06-10 06:28 -0500
        Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 13:30 +0200
      Re: Troll Parade Closing, Award Ceremony Joshua Cranmer <Pidgeot18@verizon.invalid> - 2012-06-10 08:25 -0400
        Re: Troll Parade Closing, Award Ceremony Jan Burse <janburse@fastmail.fm> - 2012-06-10 14:48 +0200
      Re: Troll Parade Closing, Award Ceremony Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-06-10 11:49 -0700

Page 1 of 4  [1] 2 3 4  Next page →

#15105 — Quick n-th Square of BigInteger

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

[toc] | [next] | [standalone]

#15106

On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
wrote:

>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 }

     Do you mean the integer part of the nth *root* of z given integer
x and n?

     I do not have a favourite or even an algorithm.  If I had to come
up with something, I would probably try a first approximation with
logarithms.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#15107 — Quick n-th Root of BigInteger

Gene Wirchenko schrieb:
> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
> wrote:
>
>> 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 }
>
>       Do you mean the integer part of the nth *root* of z given integer
> x and n?
>
>       I do not have a favourite or even an algorithm.  If I had to come
> up with something, I would probably try a first approximation with
> logarithms.
>
> Sincerely,
>
> Gene Wirchenko
>

Sorry, yes root, and z integer.

[toc] | [prev] | [next] | [standalone]

#15108 — Re: Quick n-th Root of BigInteger

On 6/8/2012 1:36 PM, Jan Burse wrote:
> Gene Wirchenko schrieb:
>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>
>> wrote:
>>
>>> 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 }
>>
>> Do you mean the integer part of the nth *root* of z given integer
>> x and n?

> Sorry, yes root, and z integer.


Positive integers?  Do you want the complex roots too? ;-)  You ask big 
questions Jan, but I think you need to ask them a little more thoughtfully.

I'm confused about the max, the z |, and the  =< x.  Care to explain 
what those signify in your question?  If you want something besides the 
real, positive nth root of A=z^n, what do you want?  I think "nth root 
of A" is the correct phrasing, which leads to the wonder what the other 
mathematical verbiage signifies.

[toc] | [prev] | [next] | [standalone]

#15111 — Re: Quick n-th Root of BigInteger

markspace <-@.> wrote:
(snip)
>>> On Fri, 08 Jun 2012 21:03:56 +0200, Jan Burse <janburse@fastmail.fm>

>>>> 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 }

(snip)
>> Sorry, yes root, and z integer.

> Positive integers?  Do you want the complex roots too? ;-)  
> You ask big questions Jan, but I think you need to ask them 
> a little more thoughtfully.

I will guess that the OP isn't a native English speaker, and
is not translating so well.

I had to look it up as I didn't know, .fm seems to be Micronesia.

It looks like he wants the nth root rounded down to the next
integer value.

I do remember when first learning Fortran wondering why no
ISQRT function.

One possibility is to do exactly as written, binary search
for the largest z such that z**n <= x. (No exclusive or operators
are needed here.)

-- glen

[toc] | [prev] | [next] | [standalone]

#15113 — Re: Quick n-th Root of BigInteger

glen herrmannsfeldt schrieb:
> I will guess that the OP isn't a native English speaker, and
> is not translating so well.  I had to look it up as I didn't know,
> .fm seems to be Micronesia.

Ha Ha

fastmail.fm = messagingengine.com

[toc] | [prev] | [next] | [standalone]

#15114 — Re: Quick n-th Root of BigInteger

markspace schrieb:
> I'm confused about the max, the z |, and the  =< x.

For those who don't know, there exists a set builder notation:

	http://en.wikipedia.org/wiki/Set-builder_notation#Z_notation

max is then a higher order function from a set to an element.

Forgot where this is taught, in elementary school?

Bye

[toc] | [prev] | [next] | [standalone]

#15117 — Re: Quick n-th Root of BigInteger

On Friday, June 8, 2012 2:34:40 PM UTC-7, Jan Burse wrote:
> markspace schrieb:
> > I'm confused about the max, the z |, and the  =< x.
> 
> For those who don't know, there exists a set builder notation:
> 
> 	http://en.wikipedia.org/wiki/Set-builder_notation#Z_notation
> 
> max is then a higher order function from a set to an element.
> 
> Forgot where this is taught, in elementary school?

Riiiight. As nations and smaller school districts remove evolution from 
their textbooks, they're going to teach mathematical logic and set 
theory in elementary school?

In any event, this being a Java forum, the notation '=<' (shown nowhere 
in your reference link, BTW) is rather odd, as we are used to '<='. Given 
that '=<' apparently is not part of the "Set Builder" notation, how about 
we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL, 
Python, shell, ...) idiom?

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15118 — Re: Quick n-th Root of BigInteger

Lew schrieb:
> In any event, this being a Java forum, the notation '=<' (shown nowhere
> in your reference link, BTW) is rather odd, as we are used to '<='. Given
> that '=<' apparently is not part of the "Set Builder" notation, how about
> we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
> Python, shell, ...) idiom?

It was not Java, it was a math spec. When one writes:

    Given: xxx
    Compute: yyy

Then xxx and yyy are not necessarely needed to follow
the Java language specification.

Do you want me to start counting the trolls that will
now make their appearance in this thread? You are
number 3 so far. I guess there will follow some more...

Bye

[toc] | [prev] | [next] | [standalone]

#15119 — Re: Quick n-th Root of BigInteger

Jan Burse schrieb:
> Do you want me to start counting the trolls that will
> now make their appearance in this thread? You are
> number 3 so far. I guess there will follow some more...

But still comp.lang.java.programmer is too small
I guess so that a shitstorm will rise. And there are
still some that want to profit.

Bye

[toc] | [prev] | [next] | [standalone]

#15121 — Re: Quick n-th Root of BigInteger

On Friday, June 8, 2012 2:47:05 PM UTC-7, Jan Burse wrote:
> Lew schrieb:
> > In any event, this being a Java forum, the notation '=<' (shown nowhere
> > in your reference link, BTW) is rather odd, as we are used to '<='. Given
> > that '=<' apparently is not part of the "Set Builder" notation, how about
> > we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
> > Python, shell, ...) idiom?
> 
> It was not Java, it was a math spec. When one writes:
> 
>     Given: xxx
>     Compute: yyy
> 
> Then xxx and yyy are not necessarely needed to follow
> the Java language specification.
> 
> Do you want me to start counting the trolls that will
> now make their appearance in this thread? You are
> number 3 so far. I guess there will follow some more...

A troll is not someone who suggests that you be clear in 
your communication, but someone who gets personally 
abusive as you did when given such a suggestion.

Oh, darn, I forgot. You're the same person who suggests 
that one perform a sex act on you when they try to engage 
in any technical discussion with you. How do you feel you have 
the moral authority to accuse anyone else of being a troll?

Because you don't.

Matthew 7:5.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15122 — Re: Quick n-th Root of BigInteger

Lew schrieb:
> A troll is not someone who suggests that you be clear in
> your communication, but someone who gets personally
> abusive as you did when given such a suggestion.

=< should be cristal clear, = = equal and < = less.
And if it is not cristal clear on first sight, it will
become clear from reading the context. In the present
case a troll is somebody who pretends not understand
a post, when he does.

Bye

[toc] | [prev] | [next] | [standalone]

#15123 — Re: Quick n-th Root of BigInteger

On Friday, June 8, 2012 3:00:36 PM UTC-7, Jan Burse wrote:
> Lew schrieb:
> > A troll is not someone who suggests that you be clear in
> > your communication, but someone who gets personally
> > abusive as you did when given such a suggestion.
> 
> =< should be cristal clear, = = equal and < = less.
> And if it is not cristal clear on first sight, it will
> become clear from reading the context. In the present
> case a troll is somebody who pretends not understand
> a post, when he does.

I don't know whom you mean. No one here pretended not
to understand it, only suggested that you follow the conventions
appropriate to the forum.

Stop being so nasty and confrontational, Jan. If you can't play 
nice, stay off the playground. You're being mean without any 
need.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15124 — Re: Quick n-th Root of BigInteger

Lew schrieb:
> Stop being so nasty and confrontational, Jan. If you can't play
> nice, stay off the playground. You're being mean without any
> need.

Stop your peer pressure. I told you already once:

Suck my dick, shut up and fuck off.

[toc] | [prev] | [next] | [standalone]

#15125 — Re: Quick n-th Root of BigInteger

Jan Burse wrote:
> Lew schrieb:
> > Stop being so nasty and confrontational, Jan. If you can't play
> > nice, stay off the playground. You're being mean without any
> > need.
> 
> Stop your peer pressure. I told you already once:
> 
> Suck my d**k, shut up and f**k off.

Who's the troll?

The request was to *stop* being nasty, not to elevate your bad 
behavior to obscenity. What is wrong with you?

Since you resort to such slimy and insulting verbiage, you show
that you have nothing worthwhile to contribute.

For this to be peer pressure, we'd have to be peers.

The slime mold is closer to being your peer.

You are behaving badly, Jan Burse. There is no justification for your 
behavior.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15131 — Re: Quick n-th Root of BigInteger

Lew <lewbloch@gmail.com> wrote:
> On Friday, June 8, 2012 2:34:40 PM UTC-7, Jan Burse wrote:
 
>> For those who don't know, there exists a set builder notation:
 
>>       http://en.wikipedia.org/wiki/Set-builder_notation#Z_notation
 
(snip) 
>> Forgot where this is taught, in elementary school?

> Riiiight. As nations and smaller school districts remove 
> evolution from their textbooks, they're going to teach 
> mathematical logic and set theory in elementary school?

For whatever reason, yes, I believe sets are not taught much
in school, maybe not until calculus where you need them for
continuity proofs. Maybe in geometry, but not as far as I know.

Some years ago we had "new math" which included a little set
theory and, as I remember number bases (radix) but I believe
even that is gone now.

> In any event, this being a Java forum, the notation '=<' 
> (shown nowhere in your reference link, BTW) is rather odd, 
> as we are used to '<='. Given that '=<' apparently is not 
> part of the "Set Builder" notation, how about we stick with 
> the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL, 
> Python, shell, ...) idiom?

I still feel funny using the exclusive or operator as an
exponential operator. Math.pow seems even worse, so I mostly
use the Fortran ** operator in posts, even though I don't write
so much in Fortran these days. There might be some programming
language that allows for =< though I don't remember which one.

-- glen

[toc] | [prev] | [next] | [standalone]

#15133 — Re: Quick n-th Root of BigInteger

glen herrmannsfeldt schrieb:
> I still feel funny using the exclusive or operator as an
> exponential operator. Math.pow seems even worse, so I mostly
> use the Fortran ** operator in posts, even though I don't write
> so much in Fortran these days. There might be some programming
> language that allows for =< though I don't remember which one.

@Glen: It would be a use of the exclusive or operator, if
it were Java. But since it isn't Java, it is not the exclusive
or operator. The ** operator would also be legit, but ^ is
for example used in LaTeX for superscript, so it makes sense
to use ^ for pow().

If you carefully observe your mail reader, depending on the
mail reader you have, you will also see that x ^ 2 is shown
as x with superscripted 2, provide the ^ directly follows
the x.

Bye

[toc] | [prev] | [next] | [standalone]

#15132 — Re: Quick n-th Root of BigInteger

Lew schrieb:
> In any event, this being a Java forum, the notation '=<' (shown nowhere
> in your reference link, BTW) is rather odd, as we are used to '<='. Given
> that '=<' apparently is not part of the "Set Builder" notation, how about
> we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
> Python, shell, ...) idiom?

@Lew: And here comes some education why =< is necessary. The link I
gave refers to set builder notation in the Z specification language.
And not to builder notation in a programming language.

In a specification language the set builder notation reads:

    { variable | condition }

Since the condition can be a first order formula, it might contain
the logical implication. This is sometimes denoted by <= or =>. Therefor 
in mathematical specification the comparators are often
written as =< and >= so that they can be distinguished.

This problem doesn't pose itself for language such as Java that do
not have a logical implication.

Best Regards

[toc] | [prev] | [next] | [standalone]

#15139 — Re: Quick n-th Root of BigInteger

Jan Burse wrote:
> Lew schrieb:
> > In any event, this being a Java forum, the notation '=<' (shown nowhere
> > in your reference link, BTW) is rather odd, as we are used to '<='. Given
> > that '=<' apparently is not part of the "Set Builder" notation, how about
> > we stick with the Java (also C, Fortran, C++, C#, Javascript, BASIC, SQL,
> > Python, shell, ...) idiom?
> 
> @Lew: And here comes some education why =< is necessary. The link I
> gave refers to set builder notation in the Z specification language.
> And not to builder notation in a programming language.

And you couldn't say that the first four times people asked?
Instead you had to rant and curse and abuse them?

And the link you gave never mentioned '=<'.

As for "necessary", not hardly.

> In a specification language the set builder notation reads:
> 
>     { variable | condition }
> 
> Since the condition can be a first order formula, it might contain
> the logical implication. This is sometimes denoted by <= or =>. Therefor[e] 
> in mathematical specification the comparators are often
> written as =< and >= so that they can be distinguished.
> 
> This problem doesn't pose itself for language such as Java that do
> not have a logical implication.

And since this is Java, and not every Java programmer is intimately 
familiar with Z notation, a question about the notation is natural and 
should have been answered politely instead of abusively, and immediately
instead of after all the nonsense you imposed.

Go to.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#15141 — Re: Quick n-th Root of BigInteger

Lew schrieb:
> And since this is Java, and not every Java programmer is intimately
> familiar with Z notation, a question about the notation is natural and

The problem with you Lew is, that you have a very
narrow view of what it means to program Java and
what a Java programming newsgroup is about. I will
not give in and lower the bar for the readers of
this newsgroup only because of your trolling.

In my opinion I can assume that a programmer has
heard about such things as loop invariants etc..
and that he/she has already seen mathematical
notation. If you insists Lew that the readers of
this newsgroup are totally uneducated then I think
you are doing them wrong.

Bye

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web