p. 108 of "Java Concurrency in Practice," if one of
the guys there has a copy. ;)
I started writing a version of that cache using Future but it got
looking a bit hairy. I submitted the very-simple version I did (which
is not the one that was in the final release) because I thought
an
I'm not sure I want to bring this into the discussion, but there's a proposal
(pushed largely by Facebook) for a timescale called the "flick" which is
exactly 1/70560 second.
Quote:
"This unit of time is the smallest time unit which is LARGER than a
nanosecond, and can in integer quant
) taking many days, and cross-checked my multiplication
routines against several other packages including GMP and previous
versions of BigInteger.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
ecomposition. This makes toString orders
of magnitude faster for large numbers and will likely improve the
performance of some of the stuff you're doing in BigDecimal as well. I
will polish those up and submit them when you've reviewed the
multiplication and pow fixes.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
Alan Eliasen wrote:
>> Brian, as you may also not know, I have further patches to
>> drastically improve the toString behavior of BigInteger using
>> Schoenhage-Strassen recursive decomposition. This makes toString
>> orders of magnitude faster for large numbers and wi
hms that would then exist, not against the slow
code in JDK 1.7. If my code isn't 100 times faster for large numbers,
(not 100 percent, 100 *times*,) I'll eat my head. (My tests on big
numbers are 330 *times* faster easily. And that's without Timothy
Buktu's magic FFT routines.)
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
rd to get right, even for super-geniuses. The GMP team historically
released versions of SS multiplication that were wrong for a small
subset of arguments. This stuff is hard.
My latest best version of all of these routines is located at:
http://futureboy.us/temp/BigInteger.java
This passes all of my regression tests for multiply in the Karatsuba
and Toom-Cook regions, and all base conversion test. It does not test
multiplication in the Schoenhage-Strassen regions, nor does it test
large division.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
> On May 4, 2013, at 5:13 AM, Alan Eliasen wrote:
>> If you're feeling overwhelmed by the magnitude of the changes to
>> BigInteger, I would very strongly suggest that you review it in
>> stages. This e-mail proposes stages for the review of this patch.
On 05/06/2013
e wants to
quickly drop in the best improvements to their own JDK, just use the 3
files with the ".final" suffix.
Let me know if you have any issues with these.
Tim and Brian, you might decide amongst yourselves who wants to file
the issues for phases 3 and 4. I don
d describing the thresholds in comments will be difficult.
If you want to change the comment to something like my first sentence
in the first paragraph, that would be fine. Alternately, we could
change the logic to match the comment, but that would probably mean that
we should re-tune the thresholds.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
s that you might want to correct "reminder" to
"remainder" in MutableBigInteger.java . I can revise the patches if you
want.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
squaring routines could benefit from some of the tricks that pow() uses
(that is, detecting powers of two in the number and handling those via
left-shifts.) This behavior would probably want to be factored out into
separate private functions, as it would be useful in pow(), square(),
and potentially in division, as I was recently discussing with Tim Buktu.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
onsider in the future if it could improve performance.
Radices that are powers of 2 shouldn't need the recursive improvements
in BigInteger.toString.
If you let me know if these changes get checked in, I can see if
re-tuning the threshold for BigInteger.toString() can improve
performanc
t of a factor of about 93.
> I linked this issue to 4837946 as a duplicate so it will be closed
> out at the same time.
That'll be great to see. Combined, these two bug reports are old
enough to buy us drinks. I'm so proud of them. :)
Is there any plan to backport these
ed
a list of links to undergraduate classes who are expected to implement
Karatsuba or Toom-Cook multiplication in a day or a week. I don't want
to present myself as a genius. I'm no better than a typical
undergraduate.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
ggered unless
numbers are already significantly largish, so it won't affect
performance of smaller numbers, but the algorithm's much-improved
efficiency will make it faster for the larger numbers that trigger it.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
e other powers, as would be
expected. It's possible to do the power-of-two conversions completely
with bit operations in BigInteger and not relying on Long, but the
improvement may be small as these cases are already relatively fast.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
<20 ...
loop to adjust to the time spent in various number sizes. You want
the timings to be significant but not so long as to take forever.
The code for the tuning program is available at:
http://futureboy.us/temp/BigIntTiming.java
Let me know what sort of thresholds you find to work best on various
architectures.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
o be
one of the most controversial parts of BigInteger improvements. :)
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
chine with one megabyte of main memory and a speed of 1
> MIPS.
>
> This is not rocket science.
Hehe. So could you please describe the solution?
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
will help you
debug some of your problems:
https://www.ssllabs.com/ssltest/analyze.html?d=java.nicholaswilliams.net
As you can see, it won't work with most browsers.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
mod m. Assumes m >= 2. */
public static int modPow(int x, int y, int m)
{
long acc = 1;
long z = x % m;
while (y != 0)
{
if ((y & 1) != 0)
acc = (acc * z) % m;
z = (z * z) % m;
y >>= 1;
}
return (int) acc;
}
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
e with my cryptographic key to indicate that it's me. :)
- --
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
-BEGIN PGP SIGNATURE-
Version: GnuPG v1.4.14 (GNU/Linux)
Comment: See Alan's GPG guide at https://futureboy.us/pgp.html
C
nd a bit of Raspberry Pi Arm); I intentionally set my thresholds
to be quite high and conservative. Is there a particular architecture
that requires the thresholds to be set that high? What performance
effect do those higher thresholds have on the most common architectures?
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
e to do a web search for any content here. I
reported this months ago. It's a pretty big issue for all of these
forums because you can't search for existing solutions, discussions, etc.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
On 10/27/2009 01:12 AM, Alan Eliasen wrote:
> On 10/23/2009 11:01 AM, Andrew John Hughes wrote:
>> 6622432 is the one of the ones I just pointed to i.e. it's in JDK7.
>> If Alan has a further patch and hasn't even submitted it for
>> inclusion, it's obviously no
one large patch?
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|for understanding."
http://futureboy.us/ | --H.H. Williams
. I think it's best to get working algorithms with
better asymptotic efficiency, as those will vastly improve performance
for large numbers, and tune them by doing more low-level bit fiddling
later. Even without being tuned to the nth degree, the new algorithms
are vastly faster for large n
with the patch. I had to
hand-edit a few lines to remove the work I'm doing for pow().
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|for understanding."
http://futureboy.us/ | --H.H. Williams
diff --git a/src/sh
hese for a variety of different
arguments, and considering the threading and memory-size-vs-speed
tradeoffs in implementing toString efficiently.
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|for understanding."
http://futureboy.us/ | --H.H. Williams
) works.)
* Optimizes some cases like multiplying 2*100, where the bit
string has a large number of zeroes in a row.
Please use this patch instead of the one I posted yesterday.
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|
e are some more optimizations I'd like to put in.
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|for understanding."
http://futureboy.us/ | --H.H. Williams
import java.math.BigInteger;
public class BigIntegerRegressionTes
with Toom-Cook multiplication
included soon. Below, interspersed among my previous statements, are
some updated performance numbers with the Toom-Cook algorithm:
Alan Eliasen wrote:
>But some numbers. For multiplying the numbers 3^100 * 3^101,
> (with my fixes to do the exponenti
esults by comparing them to the output of both JDK 1.6
> and the Kaffe JVM, which was compiled to use the well-known and
> widely-tested GMP libraries for its BigInteger work. All tests pass. I
> haven't submitted these tests, but am awaiting getting a copy of th
;s available at:
http://futureboy.us/temp/BigInteger.java
--
Alan Eliasen | "Furious activity is no substitute
[EMAIL PROTECTED]|for understanding."
http://futureboy.us/ | --H.H. Williams
diff --git a/src/share/classes/java/math/BigInteger.java
r can be improved by tens or hundreds or
thousands of times (or even more in the case of certain arguments of
pow()), and should be done to make Java a more viable platform for numerics.
This work has been in Sun's hands for a long time, and really needs
to get into 1.7.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
resholds can be again improved after my massive regression test
finishes, hopefully in the next 24 hours.
Note that my optimizations for the pow() function give vastly better
performance at even small bit sizes for many operands, as they factor
out powers of 2 in the exponent and perform these very rapidly as
bit-shifts.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
Alan Eliasen wrote:
>Note that my optimizations for the pow() function give vastly better
> performance at even small bit sizes for many operands, as they factor
> out powers of 2 in the exponent and perform these very rapidly as
> bit-shifts.
Oops. I mean powers of 2 in th
patches are designed to be as easy to read as possible, and are
implemented in terms of already-existing methods in BigInteger. Some
more performance might be squeezed out of them by doing more low-level
bit-fiddling, but I wanted to get a working version in and tested.
--
Alan Elias
methods in Java. If you are able to review this patch, please
contact me. Thanks! From all the e-mails I get, I know this is very
important to a lot of people.
Alan Eliasen wrote:
> Attached is an UPDATED patch for bug 4837946, (and others) for
> implementing asymptotically faste
ping to submit after the
multiplication patches are approved. (I was asked by Joe Darcy to
submit in smaller patches.) Hopefully these might get in JDK 7 too.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
ne
Project.
I'm all for improving Java's numerics. Please keep me informed.
I've already implemented a lot of missing algorithms.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
d what is being done
about the problem? This would appear to have major implications for the
viability of the OpenJDK project.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
ists. I hope
that paid Oracle employees will communicate the necessary fix to all
contributors on all lists, who try to contribute value to their products
for free. Please forward this to the web-discuss list.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
44 matches
Mail list logo
