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

Groups > comp.lang.java.programmer > #38345

Re: Can Java compute 9^(9^9) ?

Show all headers | View raw

The 8.5 secs are plausible. I already tested another
system, which could do it in around 20 secs.

  ECLiPSe Constraint Logic Programming System [kernel threads]
  Version 7.0 #36 (x86_64_nt), Sun Jan 28 10:18 2018

  [eclipse 2]: _ is 9^(9^9).
  Yes (20.09s cpu)

So the magnitude of this time measure is plausible.
I did not double check the result, the 370 mio digits. 

Not sure whether I should check the result..

Am Dienstag, 5. Juni 2018 20:11:04 UTC+2 schrieb burs...@gmail.com:
> In the SWI-Prolog GNU example, pow/3, where we 
> compute 9^(9^9) in blinding fast 8.5 seconds, only 
> multiplication is used. 
> 
>    pow(_,0,1) :- !.
>    pow(X,1,X) :- !.
>    pow(X,N,Y) :-
>         M is N//2, pow(X,M,A),
>         J is N mod 2, pow(X,J,B),
>         Y is (A*A)*B. 
>                ^--^----- here multiplication
> 
> But a system might detect for A*A, that the
> two arguments are identical, and then branch
> into a squaring routine.
> 
> A system might also detect in C*B that B
> is the constant value 1, and directly return C.
> But no pow() routine from GNU was used.
> 
> So for the reference value, on the same machine:
> 
>    8.5 seconds
> 
> no library driven pow() was used, only the 
> above algorithm. Which is recursive, gives
> the following pattern:
> 
>    x^y = (... (x^2 ...)^2 ...)^2 [* x]
> 
> Am Dienstag, 5. Juni 2018 19:59:00 UTC+2 schrieb Eric Sosman:
> > On 6/5/2018 12:32 PM, bursejan@gmail.com wrote:
> > > Well I used the method pow() from Java BigInteger:
> > 
> >      Sonuvagun!  I didn't even know BigInteger::pow existed (never
> > found a need to exponentiate a BigInteger).  You learn something
> > new every day ...
> > 
> > > Meanwhile I guess its this code:
> > > Line  2152:   public BigInteger pow(int exponent)
> > > http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java
> > 
> >      This is not quite identical to the code in Oracle's JDK, but is
> > clearly a "version" of it.  The pow() methods in both appear to be
> > identical, but the implementations of the square() methods they call
> > are slightly different.  The Oracle JDK's version has a comment that
> > says "Java Runtime may use intrinsic for this method" on one of the
> > sub-sub-methods called by square(), but the OpenJDK version has no
> > such remark (and refactors the methods a little differently).  It
> > seems, though, that this difference only affects the square()-ing
> > of relatively small (<4Kbits) numbers; most of the intermediate
> > results in pow(9,pow(9,9)) will be considerably larger, so whatever
> > time saving is achieved should be unimportant.  (There may, though,
> > be other differences I haven't noticed.)
> > 
> >      ... but even without hyper-optimized square() and multiply()
> > routines I don't see why the computation should take so long.  If
> > pow() does what it appears to do, there should be only about 29
> > calls to square() and 13 to multiply(), so even though most of them
> > deal with very large numbers you wouldn't expect HUGE run-times ...
> > 
> >      Meanwhile (and this is *completely* uninformed speculation), it's
> > possible the gnu bignums package is just plain smarter.  BigNum's pow()
> > uses a binary technique, which requires little setup and is quite
> > straightforward.  Perhaps gnu works a little harder on factoring the
> > exponent, discovers that pow(9,9) has *lots* of threes, and uses a
> > ternary algorithm instead?
> > 
> > -- 
> > esosman@comcast-dot-net.invalid
> > Nine hundred sixty days to go.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-01 10:20 -0700
  Re: Can Java compute 9^(9^9) ? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-06-01 13:36 -0400
    Re: Can Java compute 9^(9^9) ? j4n bur53 <janburse@fastmail.fm> - 2018-06-01 20:20 +0200
      Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 07:17 -0700
        Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 07:29 -0700
          Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 07:48 -0700
          Re: Can Java compute 9^(9^9) ? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-06-05 10:57 -0400
            Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 09:32 -0700
              Re: Can Java compute 9^(9^9) ? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-06-05 13:58 -0400
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 11:10 -0700
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-05 11:21 -0700
                Re: Can Java compute 9^(9^9) ? Andreas Leitgeb <avl@logic.at> - 2018-06-06 08:50 +0000
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-06 01:58 -0700
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-06 02:01 -0700
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-06 10:34 -0700
  Re: Can Java compute 9^(9^9) ? j4n bur53 <janburse@fastmail.fm> - 2018-06-09 21:06 +0200
    Re: Can Java compute 9^(9^9) ? v_borchert@despammed.com (Volker Borchert) - 2018-06-09 23:29 +0000
      Re: Can Java compute 9^(9^9) ? Martin Gregorie <martin@mydomain.invalid> - 2018-06-10 09:13 +0000
        Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-10 02:31 -0700
          Re: Can Java compute 9^(9^9) ? Arne Vajhøj <arne@vajhoej.dk> - 2018-06-10 18:28 -0400
            Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-10 15:48 -0700
              Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-10 15:52 -0700
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-10 15:58 -0700
              Re: Can Java compute 9^(9^9) ? Arne Vajhøj <arne@vajhoej.dk> - 2018-06-10 21:17 -0400
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-11 13:20 -0700
                Re: Can Java compute 9^(9^9) ? bursejan@gmail.com - 2018-06-14 13:37 -0700

csiph-web