1

I have some calculations that involve factorials that explode pretty fast so I resolved to use the arbitrary precision library mpmath.

The code I have looks like this:

import numpy as np
import mpmath as mp
import time

a    = np.linspace( 0, 100e-2, 100 )
b    = np.linspace( 0, np.pi )
c    = np.arange( 30 )

t    = time.time()
M    = np.ones( [ len(a), len(b), len(c) ] )
A, B = np.meshgrid( a, b, indexing = 'ij' )
temp = A**2 + B
temp = np.reshape( temp, [ len(a), len(b), 1 ] )
temp = np.repeat( temp, len(c), axis = 2 )
M   *= temp
print 'part1:      ', time.time() - t
t    = time.time()

temp = np.array( [ mp.fac(x) for x in c ] )
temp = np.reshape( temp, [ 1, 1, len(c) ] )
temp = np.repeat(  temp, len(a), axis = 0 )
temp = np.repeat(  temp, len(b), axis = 1 )
print 'part2 so far:', time.time() - t
M   *= temp
print 'part2 finally', time.time() - t
t    = time.time()

The thing that seems to take the most time is the very last line and I suspect it is because M has a bunch of floats and temp has a bunch of mp.mpfs. I tried initializing M with mp.mpfs but then everything slowed down.

This is the output I get:

part1:        0.00429606437683
part2 so far: 0.00184297561646
part2 finally 1.9477159977

Any ideas how I can speed this up?

George G
  • 7,443
  • 12
  • 45
  • 59
evan54
  • 3,585
  • 5
  • 34
  • 61

1 Answers1

3

gmpy2 is significantly faster that mpmath for this type of calculation. The following code runs about 12x faster on my machine.

import numpy as np
import gmpy2 as mp
import time

a = np.linspace(0, 100e-2, 100)
b = np.linspace(0, np.pi)
c = np.arange(30)

t = time.time()
M = np.ones([len(a), len(b), len(c)])
A, B = np.meshgrid( a, b, indexing = 'ij' )
temp = A**2+B
temp = np.reshape(temp, [len(a), len(b), 1])
temp = np.repeat(temp, len(c), axis=2)
M *= temp
print 'part1:', time.time() - t
t = time.time()

temp = np.array([mp.factorial(x) for x in c])
temp = np.reshape(temp, [1, 1, len(c)])
temp = np.repeat(temp, len(a), axis=0)
temp = np.repeat(temp, len(b), axis=1)
print 'part2 so far:', time.time() - t
M *= temp
print 'part2:', time.time() - t
t = time.time()

mpmath is written in Python and normally uses Python's native integers for its computations. If gmpy2 is available, it will use the faster integer type provided by gmpy2. If you just need one of the functions that is provided directly by gmpy2, then using gmpy2 directly is usually faster.

Update

I ran a few experiments. What's actually happening may not be what you expect. When you calculate temp, the values can either be an integer (math.factorial, gmpy.fac, or gmpy2.fac) or a floating-point value (gmpy2.factorial, mpmath.fac). When numpy computes M *= temp, all the values in temp are converted to a 64-bit float. If the value is an integer, the conversion raises an OverflowError. If the value is a floating point number, the conversion returns infinity. You can see this by changing c to np.arange(300) and print M at the end. If you use gmpy.fac or math.factorial, you will get and OverflowError. If you use mpmath.factorial or gmpy2.factorial, you won't get an OverflowError but the resulting M will contain infinities.

If you are trying to avoid the OverflowError, you will need to calculate temp with floating point values so the conversion to a 64-bit float will result in infinity.

If you aren't encountering OverflowError, then math.factorial is the fastest option.

If you are trying to avoid both OverflowError and infinities, then you'll need to use either the mpmath.mpf or the gmpy2.mpfr floating point types throughout. (Don't try to use gmpy.mpf.)

Update #2

Here is an example that uses gmpy2.mpfr with a precision of 200 bits. With c=np.arange(30), it is ~5x faster than your original example. I show it using c = np.arange(300) since that would either generate an OverflowError or infinities. The total running time for the larger range is about the same as your original code.

import numpy as np
import gmpy2
import time

from gmpy2 import mpfr

gmpy2.get_context().precision = 200

a = np.linspace(mpfr(0), mpfr(1), 100)
b = np.linspace(mpfr(0), gmpy2.const_pi())
c = np.arange(300)

t = time.time()
M = np.ones([len(a), len(b), len(c)], dtype=object)
A, B = np.meshgrid( a, b, indexing = 'ij' )
temp = A**2+B
temp = np.reshape(temp, [len(a), len(b), 1])
temp = np.repeat(temp, len(c), axis=2)
M *= temp
print 'part1:', time.time() - t
t = time.time()

temp = np.array([gmpy2.factorial(x) for x in c], dtype=object)
temp = np.reshape(temp, [1, 1, len(c)])
temp = np.repeat(temp, len(a), axis=0)
temp = np.repeat(temp, len(b), axis=1)
print 'part2 so far:', time.time() - t
M *= temp
print 'part2:', time.time() - t
t = time.time()

Disclaimer: I maintain gmpy2.

casevh
  • 11,093
  • 1
  • 24
  • 35
  • Wow! 12x! I ran it with gmpy (I previously had set `MPMATH_NOGMPY`) but it only did a 40% speed up at best. Also, my `mp.libmp.BACKEND` is `gmpy` not `gmpy2` is there a difference? – evan54 Oct 24 '14 at 00:08
  • Oops. I pasted in the wrong code. I was using `gmpy2` directly. I'll edit the answer in a minute. `gmpy2` provides full access to the MPFR (correctly rounded real floating point) and MPC (correctly rounded complex floating point) arbitrary precision libraries. The older `gmpy` doesn't support MPFR and MPC. – casevh Oct 24 '14 at 00:12
  • hm... I just noticed that the only change you've made is what factorial function is used. The thing that is slowing my code down is the last `M*=temp` not the `mp.fac(x)` operation. Does the backend matter in this case this much? – evan54 Oct 24 '14 at 00:23
  • Please double-check the import statements... I am not using mpmath at all. It's not just changing the backend: it's using gmpy2 instead of mpmath. – casevh Oct 24 '14 at 01:14
  • I think I get it... in the sense that you're saying `gmpy2` elements will do the `M *= temp` operation much faster correct? – evan54 Oct 24 '14 at 01:34
  • ok I haven't managed to install `gmpy2` but worked like a charm with `gmpy` – evan54 Oct 24 '14 at 02:20
  • Please see my updated answer. And I highly recommend using `gmpy2` instead of `gmpy` for floating point arithmetic. – casevh Oct 24 '14 at 02:58
  • So the problem with that is one I tried installing gmpy2 and I think I've made a mess :( and the second even if I install it locally the admins on the shared computer where I actually run stuff won't go through anything more than a `sudo apt-get` or `pip install` etc command, reading through your update now. Thanks very much either way!! – evan54 Oct 24 '14 at 03:11
  • you're a genius. I got an `OverflowError` error as you suggested. As you may expect the desired outcome is to avoid both the `OverflowError` and the infs so I assume that gmpy2 is the way to go. I think I'll post another question about "easy installation" of gmpy2 – evan54 Oct 24 '14 at 03:18
  • Actually I think I found the answer to my question here: http://stackoverflow.com/questions/14178594/pip-installation-of-gmpy2#comment19650274_14179137 http://stackoverflow.com/questions/14178594/pip-installation-of-gmpy2/14180357#14180357 – evan54 Oct 24 '14 at 03:20