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

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

Can Java compute 9^(9^9) ?

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

Contents

  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

Page 1 of 2  [1] 2  Next page →

#38331 — Can Java compute 9^(9^9) ?

Can I compute 9^(9^9) with Java BigIntegers?

[toc] | [next] | [standalone]

#38332

On 6/1/2018 1:20 PM, bursejan@gmail.com wrote:
> 
> Can I compute 9^(9^9) with Java BigIntegers?

     Sure, given enough memory.  The product will have about 1.3 billion
bits, or 19.2 million 64-bit `long's.

     The computation might take a while, though.  Be patient.

-- 
esosman@comcast-dot-net.invalid
Nine hundred sixty-four days to go.

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

#38333

Came back from dinner:

?- time((_ is 9^(9^9))).
% Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18 
19:54:01)
Yes

?- statistics.
Max Memory           7,635,730,432 Bytes
Used Memory           765,913,440 Bytes
Free Memory          2,891,739,304 Bytes
Uptime                 2,466,670 Millis
GC Time                    9,315 Millis
Thread Cpu Time          963,812 Millis
Current Time          06/01/18 20:18:37

Eric Sosman schrieb:
> On 6/1/2018 1:20 PM, bursejan@gmail.com wrote:
>>
>> Can I compute 9^(9^9) with Java BigIntegers?
> 
>      Sure, given enough memory.  The product will have about 1.3 billion
> bits, or 19.2 million 64-bit `long's.
> 
>      The computation might take a while, though.  Be patient.
> 

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

#38338

There is something wrong with the 16 minutes.
GNU bignums can do it in 8.5 secs:

   Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.15)
   SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

   ?- [user].
   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. 
   ^D

   ?- pow(9,9,X).
   X = 387420489.

   ?- time((pow(9,9,X), pow(9,X,_))).
   % 159 inferences, 7.500 CPU in 8.514 seconds (88% CPU, 21 Lips) 

I need to check again. Why it took 16 minutes...

Am Freitag, 1. Juni 2018 20:21:01 UTC+2 schrieb j4n bur53:
> Came back from dinner:
> 
> ?- time((_ is 9^(9^9))).
> % Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18 
> 19:54:01)
> Yes
> 
> ?- statistics.
> Max Memory           7,635,730,432 Bytes
> Used Memory           765,913,440 Bytes
> Free Memory          2,891,739,304 Bytes
> Uptime                 2,466,670 Millis
> GC Time                    9,315 Millis
> Thread Cpu Time          963,812 Millis
> Current Time          06/01/18 20:18:37
> 
> Eric Sosman schrieb:
> > On 6/1/2018 1:20 PM, bursejan@gmail.com wrote:
> >>
> >> Can I compute 9^(9^9) with Java BigIntegers?
> > 
> >      Sure, given enough memory.  The product will have about 1.3 billion
> > bits, or 19.2 million 64-bit `long's.
> > 
> >      The computation might take a while, though.  Be patient.
> >

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

#38339

Maybe should raise an issue for OpenJDK.

Still researching, not yet sure what goes

wrong with Java BigInteger here...

Am Dienstag, 5. Juni 2018 16:17:21 UTC+2 schrieb burs...@gmail.com:
> There is something wrong with the 16 minutes.
> GNU bignums can do it in 8.5 secs:
> 
>    Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.15)
>    SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
> 
>    ?- [user].
>    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. 
>    ^D
> 
>    ?- pow(9,9,X).
>    X = 387420489.
> 
>    ?- time((pow(9,9,X), pow(9,X,_))).
>    % 159 inferences, 7.500 CPU in 8.514 seconds (88% CPU, 21 Lips) 
> 
> I need to check again. Why it took 16 minutes...
> 
> Am Freitag, 1. Juni 2018 20:21:01 UTC+2 schrieb j4n bur53:
> > Came back from dinner:
> > 
> > ?- time((_ is 9^(9^9))).
> > % Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18 
> > 19:54:01)
> > Yes
> > 
> > ?- statistics.
> > Max Memory           7,635,730,432 Bytes
> > Used Memory           765,913,440 Bytes
> > Free Memory          2,891,739,304 Bytes
> > Uptime                 2,466,670 Millis
> > GC Time                    9,315 Millis
> > Thread Cpu Time          963,812 Millis
> > Current Time          06/01/18 20:18:37
> > 
> > Eric Sosman schrieb:
> > > On 6/1/2018 1:20 PM, bursejan@gmail.com wrote:
> > >>
> > >> Can I compute 9^(9^9) with Java BigIntegers?
> > > 
> > >      Sure, given enough memory.  The product will have about 1.3 billion
> > > bits, or 19.2 million 64-bit `long's.
> > > 
> > >      The computation might take a while, though.  Be patient.
> > >

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

#38340

Disclaimer: pow/3 is not the usual algorithm that
is implement. But its very similar. So pow/3 doesn't
do really the following:

   x^y = x^(2^k1) * ... * x^(2^kn)

where k1,..,kn are the bit positions. The result
is rather something like:

   x^y = (... (x^2 ...)^2 ...)^2 [* x]

Usually pow/3 is not implemented in bignum libraries
since it uses recursion, and the other iterative
algorithm is implemented. 

But somehow this irrelevant to 
show the potential performance. 

Am Dienstag, 5. Juni 2018 16:30:01 UTC+2 schrieb burs...@gmail.com:
> Maybe should raise an issue for OpenJDK.
> 
> Still researching, not yet sure what goes
> 
> wrong with Java BigInteger here...
> 
> Am Dienstag, 5. Juni 2018 16:17:21 UTC+2 schrieb burs...@gmail.com:
> > There is something wrong with the 16 minutes.
> > GNU bignums can do it in 8.5 secs:
> > 
> >    Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.15)
> >    SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
> > 
> >    ?- [user].
> >    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. 
> >    ^D
> > 
> >    ?- pow(9,9,X).
> >    X = 387420489.
> > 
> >    ?- time((pow(9,9,X), pow(9,X,_))).
> >    % 159 inferences, 7.500 CPU in 8.514 seconds (88% CPU, 21 Lips) 
> > 
> > I need to check again. Why it took 16 minutes...
> > 
> > Am Freitag, 1. Juni 2018 20:21:01 UTC+2 schrieb j4n bur53:
> > > Came back from dinner:
> > > 
> > > ?- time((_ is 9^(9^9))).
> > > % Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18 
> > > 19:54:01)
> > > Yes
> > > 
> > > ?- statistics.
> > > Max Memory           7,635,730,432 Bytes
> > > Used Memory           765,913,440 Bytes
> > > Free Memory          2,891,739,304 Bytes
> > > Uptime                 2,466,670 Millis
> > > GC Time                    9,315 Millis
> > > Thread Cpu Time          963,812 Millis
> > > Current Time          06/01/18 20:18:37
> > > 
> > > Eric Sosman schrieb:
> > > > On 6/1/2018 1:20 PM, bursejan@gmail.com wrote:
> > > >>
> > > >> Can I compute 9^(9^9) with Java BigIntegers?
> > > > 
> > > >      Sure, given enough memory.  The product will have about 1.3 billion
> > > > bits, or 19.2 million 64-bit `long's.
> > > > 
> > > >      The computation might take a while, though.  Be patient.
> > > >

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

#38341

On 6/5/2018 10:29 AM, bursejan@gmail.com wrote:
> Maybe should raise an issue for OpenJDK.
> 
> Still researching, not yet sure what goes
> 
> wrong with Java BigInteger here...

     Perhaps if you'd exhibit the code you used, someone
might be able to suggest ways to speed it up.

-- 
esosman@comcast-dot-net.invalid
Nine hundred sixty days to go.

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

#38342

Well I used the method pow() from Java BigInteger:
Give me some time, I can provide more specs.

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

Am Dienstag, 5. Juni 2018 16:57:27 UTC+2 schrieb Eric Sosman:
> On 6/5/2018 10:29 AM, bursejan@gmail.com wrote:
> > Maybe should raise an issue for OpenJDK.
> > 
> > Still researching, not yet sure what goes
> > 
> > wrong with Java BigInteger here...
> 
>      Perhaps if you'd exhibit the code you used, someone
> might be able to suggest ways to speed it up.
> 
> -- 
> esosman@comcast-dot-net.invalid
> Nine hundred sixty days to go.

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

#38343

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.

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

#38344

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.

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

#38345

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.

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

#38347

bursejan@gmail.com <bursejan@gmail.com> wrote:
> 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..

Maybe, both SWI-Prolog and ECLiPSe are both smart in detecting
and avoiding calculations "assigned" to "_".

Unless you can store the result in a variable and query some
properties of it for checking it might just have skipped some
of the calculations. 

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

#38348

No, no, they are not that smart, _ is not some functional
programming lazy, it only instructs the top-level to not
show the result. I can 100% assure you that. 

Storing the result in on the other hand in a file takes 
like 2 minutes. For the 8.5 secs blinding fast calculation,
I get file size 369'693'102 bigpow999.txt, so the calculation 

is possibly corrrect.

See also here, the Edit 06.06.2018:
https://math.stackexchange.com/a/2809007/4414

Its more the problem that Java probably doesn't implement
FFT multiplication, and the problem is above the threshold
where FFT would make sense. Or its some other problem 
with GC, dunno yet.

I didn't another test right now, with pow/3, it
shows that Java gets increasingly slower, whereby
GNU keeps the runtime for multiplication down:

Java, the (A*A)*B step measured:

% Up 1,059 ms, GC 14 ms, Thread Cpu 1,031 ms (Current 06/06/18 10:07:54)
% Up 2,320 ms, GC 11 ms, Thread Cpu 2,297 ms (Current 06/06/18 10:07:56)
% Up 5,852 ms, GC 27 ms, Thread Cpu 5,812 ms (Current 06/06/18 10:08:02)
% Up 15,949 ms, GC 179 ms, Thread Cpu 15,782 ms (Current 06/06/18 10:08:18)
% Up 45,419 ms, GC 540 ms, Thread Cpu 44,796 ms (Current 06/06/18 10:09:03)
% Up 116,740 ms, GC 1,234 ms, Thread Cpu 115,235 ms (Current 06/06/18 10:11:00)
% Up 326,318 ms, GC 2,266 ms, Thread Cpu 323,765 ms (Current 06/06/18 10:16:26)

GNU, the (A*A)*B step measured.

% 2 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 43 Lips)
% 2 inferences, 0.094 CPU in 0.109 seconds (86% CPU, 21 Lips)
% 2 inferences, 0.203 CPU in 0.219 seconds (93% CPU, 10 Lips)
% 2 inferences, 0.438 CPU in 0.484 seconds (90% CPU, 5 Lips)
% 2 inferences, 0.875 CPU in 0.984 seconds (89% CPU, 2 Lips)
% 2 inferences, 1.828 CPU in 2.062 seconds (89% CPU, 1 Lips)
% 2 inferences, 3.859 CPU in 4.202 seconds (92% CPU, 1 Lips)

Am Mittwoch, 6. Juni 2018 10:51:05 UTC+2 schrieb Andreas Leitgeb:
> bursejan@gmail.com <bursejan@gmail.com> wrote:
> > 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..
> 
> Maybe, both SWI-Prolog and ECLiPSe are both smart in detecting
> and avoiding calculations "assigned" to "_".
> 
> Unless you can store the result in a variable and query some
> properties of it for checking it might just have skipped some
> of the calculations.

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

#38349

Corr.:
I did another test right now, with pow/3, it 

Am Mittwoch, 6. Juni 2018 10:58:44 UTC+2 schrieb burs...@gmail.com:
> No, no, they are not that smart, _ is not some functional
> programming lazy, it only instructs the top-level to not
> show the result. I can 100% assure you that. 
> 
> Storing the result in on the other hand in a file takes 
> like 2 minutes. For the 8.5 secs blinding fast calculation,
> I get file size 369'693'102 bigpow999.txt, so the calculation 
> 
> is possibly corrrect.
> 
> See also here, the Edit 06.06.2018:
> https://math.stackexchange.com/a/2809007/4414
> 
> Its more the problem that Java probably doesn't implement
> FFT multiplication, and the problem is above the threshold
> where FFT would make sense. Or its some other problem 
> with GC, dunno yet.
> 
> I didn't another test right now, with pow/3, it
> shows that Java gets increasingly slower, whereby
> GNU keeps the runtime for multiplication down:
> 
> Java, the (A*A)*B step measured:
> 
> % Up 1,059 ms, GC 14 ms, Thread Cpu 1,031 ms (Current 06/06/18 10:07:54)
> % Up 2,320 ms, GC 11 ms, Thread Cpu 2,297 ms (Current 06/06/18 10:07:56)
> % Up 5,852 ms, GC 27 ms, Thread Cpu 5,812 ms (Current 06/06/18 10:08:02)
> % Up 15,949 ms, GC 179 ms, Thread Cpu 15,782 ms (Current 06/06/18 10:08:18)
> % Up 45,419 ms, GC 540 ms, Thread Cpu 44,796 ms (Current 06/06/18 10:09:03)
> % Up 116,740 ms, GC 1,234 ms, Thread Cpu 115,235 ms (Current 06/06/18 10:11:00)
> % Up 326,318 ms, GC 2,266 ms, Thread Cpu 323,765 ms (Current 06/06/18 10:16:26)
> 
> GNU, the (A*A)*B step measured.
> 
> % 2 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 43 Lips)
> % 2 inferences, 0.094 CPU in 0.109 seconds (86% CPU, 21 Lips)
> % 2 inferences, 0.203 CPU in 0.219 seconds (93% CPU, 10 Lips)
> % 2 inferences, 0.438 CPU in 0.484 seconds (90% CPU, 5 Lips)
> % 2 inferences, 0.875 CPU in 0.984 seconds (89% CPU, 2 Lips)
> % 2 inferences, 1.828 CPU in 2.062 seconds (89% CPU, 1 Lips)
> % 2 inferences, 3.859 CPU in 4.202 seconds (92% CPU, 1 Lips)
> 
> Am Mittwoch, 6. Juni 2018 10:51:05 UTC+2 schrieb Andreas Leitgeb:
> > bursejan@gmail.com <bursejan@gmail.com> wrote:
> > > 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..
> > 
> > Maybe, both SWI-Prolog and ECLiPSe are both smart in detecting
> > and avoiding calculations "assigned" to "_".
> > 
> > Unless you can store the result in a variable and query some
> > properties of it for checking it might just have skipped some
> > of the calculations.

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

#38350

Maybe should try to switch to use this gem:

"This code has been merged into OpenJDK 8 except 
for the Schönhage-Strassen and Barrett algorithms 
which are planned for OpenJDK 9."
https://github.com/tbuktu/bigint

Oki Doki

Am Mittwoch, 6. Juni 2018 11:02:04 UTC+2 schrieb burs...@gmail.com:
> Corr.:
> I did another test right now, with pow/3, it 
> 
> Am Mittwoch, 6. Juni 2018 10:58:44 UTC+2 schrieb burs...@gmail.com:
> > No, no, they are not that smart, _ is not some functional
> > programming lazy, it only instructs the top-level to not
> > show the result. I can 100% assure you that. 
> > 
> > Storing the result in on the other hand in a file takes 
> > like 2 minutes. For the 8.5 secs blinding fast calculation,
> > I get file size 369'693'102 bigpow999.txt, so the calculation 
> > 
> > is possibly corrrect.
> > 
> > See also here, the Edit 06.06.2018:
> > https://math.stackexchange.com/a/2809007/4414
> > 
> > Its more the problem that Java probably doesn't implement
> > FFT multiplication, and the problem is above the threshold
> > where FFT would make sense. Or its some other problem 
> > with GC, dunno yet.
> > 
> > I didn't another test right now, with pow/3, it
> > shows that Java gets increasingly slower, whereby
> > GNU keeps the runtime for multiplication down:
> > 
> > Java, the (A*A)*B step measured:
> > 
> > % Up 1,059 ms, GC 14 ms, Thread Cpu 1,031 ms (Current 06/06/18 10:07:54)
> > % Up 2,320 ms, GC 11 ms, Thread Cpu 2,297 ms (Current 06/06/18 10:07:56)
> > % Up 5,852 ms, GC 27 ms, Thread Cpu 5,812 ms (Current 06/06/18 10:08:02)
> > % Up 15,949 ms, GC 179 ms, Thread Cpu 15,782 ms (Current 06/06/18 10:08:18)
> > % Up 45,419 ms, GC 540 ms, Thread Cpu 44,796 ms (Current 06/06/18 10:09:03)
> > % Up 116,740 ms, GC 1,234 ms, Thread Cpu 115,235 ms (Current 06/06/18 10:11:00)
> > % Up 326,318 ms, GC 2,266 ms, Thread Cpu 323,765 ms (Current 06/06/18 10:16:26)
> > 
> > GNU, the (A*A)*B step measured.
> > 
> > % 2 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 43 Lips)
> > % 2 inferences, 0.094 CPU in 0.109 seconds (86% CPU, 21 Lips)
> > % 2 inferences, 0.203 CPU in 0.219 seconds (93% CPU, 10 Lips)
> > % 2 inferences, 0.438 CPU in 0.484 seconds (90% CPU, 5 Lips)
> > % 2 inferences, 0.875 CPU in 0.984 seconds (89% CPU, 2 Lips)
> > % 2 inferences, 1.828 CPU in 2.062 seconds (89% CPU, 1 Lips)
> > % 2 inferences, 3.859 CPU in 4.202 seconds (92% CPU, 1 Lips)
> > 
> > Am Mittwoch, 6. Juni 2018 10:51:05 UTC+2 schrieb Andreas Leitgeb:
> > > bursejan@gmail.com <bursejan@gmail.com> wrote:
> > > > 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..
> > > 
> > > Maybe, both SWI-Prolog and ECLiPSe are both smart in detecting
> > > and avoiding calculations "assigned" to "_".
> > > 
> > > Unless you can store the result in a variable and query some
> > > properties of it for checking it might just have skipped some
> > > of the calculations.

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

#38351

Lets assume you are too lazy to implement the
recursive Schoenhage algorithm for toString(),
as is found in Java BigInteger.

Are there BigIntegers based on BCD coding.
I guess they could also do FFT multiplication?

Interestingly IBM, also for their new POWER9,
still provides BCD coding support.

Figure 2. Exploit POWER9 technology using XL’s
POWER9 exploited scalar & vector built-in functions (BIFs)
https://openpowerfoundation.org/blogs/xl-compilers-power9/?platform=hootsuite

Something open source or benchmark through
OpenPower Foundation?

How fast 9^(9^9) on summit?

bursejan@gmail.com schrieb:
> 
> Can I compute 9^(9^9) with Java BigIntegers?
> 

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

#38352

j4n bur53 wrote:

> Interestingly IBM, also for their new POWER9,
> still provides BCD coding support.

Is it part of ANSI COBOL?

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

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

#38353

On Sat, 09 Jun 2018 23:29:53 +0000, Volker Borchert wrote:

> j4n bur53 wrote:
> 
>> Interestingly IBM, also for their new POWER9,
>> still provides BCD coding support.
> 
> Is it part of ANSI COBOL?
>
Its been a long time since I wrote any COBOL, and I've never done so on 
IBM kit [only ICL 1900 (24bit word, 6bit char), ICL 2900 (byte-oriented), 
DEC VAX, Tandem and NCR UNIX (Intel chips)] and AFAIK none of these 
machines supported BCD arithmetic at the hardware level. 

COBOL specifies a number of numeric representations which include COMP 
(fixed length numeric strings), DISPLAY (formatted character strings) 
COMP SYNC (native binary representations) and a few others (COMP-n) 
including floating point. I think you'll find that the internal 
representation of COMP variables is undefined by the standard as long as 
manipulating it works to the CODSASYL rules. I've looked at COBOL crash 
dumps on most of these systems and don't recall any of them using some 
form of non-native numeric storage, i.e. if you could read the assembler, 
the data division of the COBOL dump was understandable. 


-- 
Martin    | martin at
Gregorie  | gregorie dot org

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

#38354

Intel 8080 had hardware support for BCD arithmetic
https://en.wikipedia.org/wiki/Half-carry_flag

While packed BCD does not make optimal use 
of storage (about one-sixth of the memory used 
is wasted), conversion to ASCII, EBCDIC, or 
the various encodings of Unicode is still 
trivial, as no arithmetic operations are 
required. The extra storage requirements 
are usually offset by the need for the 
accuracy and compatibility with calculator 
or hand calculation that fixed-point decimal 
arithmetic provides. Denser packings of BCD 
exist which avoid the storage penalty and 
also need no arithmetic operations for 
common conversions.

Packed BCD is supported in the COBOL programming 
language as the "COMPUTATIONAL-3" (an IBM 
extension adopted by many other compiler 
vendors) or "PACKED-DECIMAL" (part of the 
1985 COBOL standard) data type. It is 
supported in PL/I as "FIXED DECIMAL". Besides 
the IBM System/360 and later compatible 
mainframes, packed BCD is implemented 
in the native instruction set of the 
original VAX processors from Digital 
Equipment Corporation and some models 
of the SDS Sigma series mainframes, and 
is the native format for the Burroughs 
Corporation Medium Systems line of 
mainframes (descended from the 1950s 
Electrodata 200 series).

each of the two nibbles of each byte represent a decimal digit
https://en.wikipedia.org/wiki/Binary-coded_decimal#Packed_BCD

Am Sonntag, 10. Juni 2018 11:13:19 UTC+2 schrieb Martin Gregorie:
> On Sat, 09 Jun 2018 23:29:53 +0000, Volker Borchert wrote:
> 
> > j4n bur53 wrote:
> > 
> >> Interestingly IBM, also for their new POWER9,
> >> still provides BCD coding support.
> > 
> > Is it part of ANSI COBOL?
> >
> Its been a long time since I wrote any COBOL, and I've never done so on 
> IBM kit [only ICL 1900 (24bit word, 6bit char), ICL 2900 (byte-oriented), 
> DEC VAX, Tandem and NCR UNIX (Intel chips)] and AFAIK none of these 
> machines supported BCD arithmetic at the hardware level. 
> 
> COBOL specifies a number of numeric representations which include COMP 
> (fixed length numeric strings), DISPLAY (formatted character strings) 
> COMP SYNC (native binary representations) and a few others (COMP-n) 
> including floating point. I think you'll find that the internal 
> representation of COMP variables is undefined by the standard as long as 
> manipulating it works to the CODSASYL rules. I've looked at COBOL crash 
> dumps on most of these systems and don't recall any of them using some 
> form of non-native numeric storage, i.e. if you could read the assembler, 
> the data division of the COBOL dump was understandable. 
> 
> 
> -- 
> Martin    | martin at
> Gregorie  | gregorie dot org

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

#38355

On 6/10/2018 5:31 AM, bursejan@gmail.com wrote:
> Am Sonntag, 10. Juni 2018 11:13:19 UTC+2 schrieb Martin Gregorie:
>> On Sat, 09 Jun 2018 23:29:53 +0000, Volker Borchert wrote:
>>> j4n bur53 wrote:
>>>> Interestingly IBM, also for their new POWER9,
>>>> still provides BCD coding support.
>>>
>>> Is it part of ANSI COBOL?
>>>
>> Its been a long time since I wrote any COBOL, and I've never done so on
>> IBM kit [only ICL 1900 (24bit word, 6bit char), ICL 2900 (byte-oriented),
>> DEC VAX, Tandem and NCR UNIX (Intel chips)] and AFAIK none of these
>> machines supported BCD arithmetic at the hardware level.
>>
>> COBOL specifies a number of numeric representations which include COMP
>> (fixed length numeric strings), DISPLAY (formatted character strings)
>> COMP SYNC (native binary representations) and a few others (COMP-n)
>> including floating point. I think you'll find that the internal
>> representation of COMP variables is undefined by the standard as long as
>> manipulating it works to the CODSASYL rules. I've looked at COBOL crash
>> dumps on most of these systems and don't recall any of them using some
>> form of non-native numeric storage, i.e. if you could read the assembler,
>> the data division of the COBOL dump was understandable.
> 
> Intel 8080 had hardware support for BCD arithmetic
> https://en.wikipedia.org/wiki/Half-carry_flag
> 
> While packed BCD does not make optimal use
> of storage (about one-sixth of the memory used
> is wasted), conversion to ASCII, EBCDIC, or
> the various encodings of Unicode is still
> trivial, as no arithmetic operations are
> required. The extra storage requirements
> are usually offset by the need for the
> accuracy and compatibility with calculator
> or hand calculation that fixed-point decimal
> arithmetic provides. Denser packings of BCD
> exist which avoid the storage penalty and
> also need no arithmetic operations for
> common conversions.
> 
> Packed BCD is supported in the COBOL programming
> language as the "COMPUTATIONAL-3" (an IBM
> extension adopted by many other compiler
> vendors) or "PACKED-DECIMAL" (part of the
> 1985 COBOL standard) data type. It is
> supported in PL/I as "FIXED DECIMAL". Besides
> the IBM System/360 and later compatible
> mainframes, packed BCD is implemented
> in the native instruction set of the
> original VAX processors from Digital
> Equipment Corporation and some models
> of the SDS Sigma series mainframes, and
> is the native format for the Burroughs
> Corporation Medium Systems line of
> mainframes (descended from the 1950s
> Electrodata 200 series).

Note that there is a difference between supporting
BCD format in memory and having the CPU support it.

Systems supporting BCD format in memory can process
them in 3 different ways:
1) BCD instructions in the ISA implemented in actual
    silicium
2) BCD instructions in the ISA implemented in
    micro-code
3) non-BCD instructions

All will support COBOL COMP-3 fine.

#1 will be fastest, so if COBOL COMP-3 is a huge
part of the actual workload for a given computer
architecture then it makes sense.

Arne

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web