Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #38343
| From | Eric Sosman <esosman@comcast-dot-net.invalid> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Can Java compute 9^(9^9) ? |
| Date | 2018-06-05 13:58 -0400 |
| Organization | A noiseless patient Spider |
| Message-ID | <pf6j0p$334$1@dont-email.me> (permalink) |
| References | (2 earlier) <pes2q3$ogn$1@news.albasani.net> <b79c63c3-c935-4889-9803-c4c2c5fba9c0@googlegroups.com> <34305606-daa5-444d-b64e-fb5d3b70e0bf@googlegroups.com> <pf68cb$lbj$1@dont-email.me> <759db7ea-c012-45d2-bcd4-57620cb082c8@googlegroups.com> |
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
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