search

dnrajugade / guava-libraries

Automatically exported from code.google.com/p/guava-libraries
Apache License 2.0
0 stars 0 forks source link

Optimizations of LongMath #1205

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
FWIW, I was curious if something could be further optimized and it looks like 
it could:

.benchmark     ns linear runtime
.......Pow  12.50 =
.......Mod  10.80 =
.......GCD  10.04 =
.Factorial   3.61 =
..Binomial 244.46 ==============================
BinomialMG 145.49 =================

The idea is quite simple:
- avoid both division and gcd on each step
- maintain the intermediate results in the form `result * p / q`
- multiply into `p` and `q` as long as possible
- merge them into result when needed

The code is a bit shorter than the original. The speed up comes nearly 
exclusively from values above BIGGEST_SIMPLE_BINOMIALS, where it's about twice 
as fast as before.

The first patch introduces everything I needed, the second cleans it up. You 
might want to look first at the result of applying both of them.

Original issue reported on code.google.com by Maaarti...@gmail.com on 15 Nov 2012 at 12:16

Attachments:

GoogleCodeExporter commented 9 years ago

Original comment by kak@google.com on 15 Nov 2012 at 4:04

GoogleCodeExporter commented 9 years ago 
Some improvement is also possible for LongMath.sqrt, based on the fact that the 
double approximation is nearly exact. Because of this, simply 
incrementing/decrementing in loop is faster then the Newton's method.

Actually, it can be shown that (long) Math.sqrt(x) for each long x equals to 
the exact square root rounded either up or down. This makes it very simple and 
fast:

benchmark     ns linear runtime
.....Sqrt   8.44 =
..SqrtOld  18.96 ==

I was surprissed that the test

for (long x=1; x*x>0; ++x) Assert.assertEquals(Math.sqrt(x*x), x, 0);

passes and tried to prove it at

http://math.stackexchange.com/questions/237865/show-that-floating-point-sqrtxx-x
-for-all-long-x

This claim gets used as described in LongMath.sqrtApprox.

My above comment on the patches holds here too.

Original comment by Maaarti...@gmail.com on 17 Nov 2012 at 2:11

Attachments:

GoogleCodeExporter commented 9 years ago 
I'm looking into this.  Not all of this works quite right, and I don't think 
some of these things are worthwhile optimizations, but there's useful material 
here.

Original comment by lowas...@google.com on 17 Nov 2012 at 6:55

GoogleCodeExporter commented 9 years ago 
Both of these have been more or less done and mirrored out, though I came up 
with an alternative proof -- of the *specific* claim that |floor(sqrt(x)) - 
(long) Math.sqrt(x)| <= 1 -- that I feel pretty confident of.

Original comment by lowas...@google.com on 27 Nov 2012 at 6:40

GoogleCodeExporter commented 9 years ago

Original comment by lowas...@google.com on 26 Dec 2012 at 5:01

GoogleCodeExporter commented 9 years ago 
This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:13

GoogleCodeExporter commented 9 years ago

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08