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

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

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

Show all headers | View raw

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