New drop in replacement for math/big using GMP
737 views
Skip to first unread message
Nick Craig-Wood
Oct 9, 2013, 12:38:33 PM10/9/13
to golang-nuts
I decided to make an industrial strength drop in replacement for
math/big using GMP. You can just change the import and enjoy the super
speed of GMP in your go programs!
https://github.com/ncw/gmp
GMP is very much faster than Go's math/big however it is an external C
library with all the problems that entails (cgo, dependencies etc)
This library was made by taking the cgo example of wrapping GMP from the
Go source and doing the following to it
* Copying the implementation from misc/cgo/gmp/gmp.go
* Copying the documentation from src/pkg/math/big/int.go
* Additional implementation of missing methods
* Bug fixes for existing implementations
* Making it passes the test suite from src/pkg/math/big/int_test.go
* Adding memory management
* Fix problems on 32 bit platforms when using int64 values which don't
fit into a C.long
See here for package docs
http://go.pkgdoc.org/github.com/ncw/gmp
--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick
math/big using GMP. You can just change the import and enjoy the super
speed of GMP in your go programs!
https://github.com/ncw/gmp
GMP is very much faster than Go's math/big however it is an external C
library with all the problems that entails (cgo, dependencies etc)
This library was made by taking the cgo example of wrapping GMP from the
Go source and doing the following to it
* Copying the implementation from misc/cgo/gmp/gmp.go
* Copying the documentation from src/pkg/math/big/int.go
* Additional implementation of missing methods
* Bug fixes for existing implementations
* Making it passes the test suite from src/pkg/math/big/int_test.go
* Adding memory management
* Fix problems on 32 bit platforms when using int64 values which don't
fit into a C.long
See here for package docs
http://go.pkgdoc.org/github.com/ncw/gmp
--
Nick Craig-Wood <ni...@craig-wood.com> -- http://www.craig-wood.com/nick
Michael Jones
Oct 9, 2013, 4:20:22 PM10/9/13
to Nick Craig-Wood, golang-nuts
How fast is "very much"? More than 2-3x for your program's overall runtime?
--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Nick Craig-Wood
Oct 9, 2013, 5:47:38 PM10/9/13
to Michael Jones, golang-nuts
It does depend rather on exactly what you are doing.
There is quite a bit more overhead in creating a gmp.Int vs a big.Int,
however GMP runs much quicker when the numbers get bigger because it has
a range of extremely efficient algorithms.
To give a concrete example on a pi calculating program, math/big is
slightly ahead up to a length of 4,000 digits but by 1,000,000 digits
gmp is 47x times quicker.
The only time the gmp based library is a lot slower is if you are
creating and destroying lots of numbers quickly and that is usually
something you can easily optimize (by re-using numbers) which helps the
performance of both the math/big and the gmp solutions.
On 09/10/13 21:20, Michael Jones wrote:
> How fast is "very much"? More than 2-3x for your program's overall runtime?
>
>
> On Wed, Oct 9, 2013 at 9:38 AM, Nick Craig-Wood <ni...@craig-wood.com
> <mailto:ni...@craig-wood.com>> wrote:
>
> I decided to make an industrial strength drop in replacement for
> math/big using GMP. You can just change the import and enjoy the super
> speed of GMP in your go programs!
>
> https://github.com/ncw/gmp
>
> GMP is very much faster than Go's math/big however it is an external C
> library with all the problems that entails (cgo, dependencies etc)
>
> This library was made by taking the cgo example of wrapping GMP from the
> Go source and doing the following to it
>
> * Copying the implementation from misc/cgo/gmp/gmp.go
> * Copying the documentation from src/pkg/math/big/int.go
> * Additional implementation of missing methods
> * Bug fixes for existing implementations
> * Making it passes the test suite from src/pkg/math/big/int_test.go
> * Adding memory management
> * Fix problems on 32 bit platforms when using int64 values which don't
> fit into a C.long
>
> See here for package docs
>
> http://go.pkgdoc.org/github.com/ncw/gmp
>
> --
> Nick Craig-Wood <ni...@craig-wood.com <mailto:ni...@craig-wood.com>>
There is quite a bit more overhead in creating a gmp.Int vs a big.Int,
however GMP runs much quicker when the numbers get bigger because it has
a range of extremely efficient algorithms.
To give a concrete example on a pi calculating program, math/big is
slightly ahead up to a length of 4,000 digits but by 1,000,000 digits
gmp is 47x times quicker.
The only time the gmp based library is a lot slower is if you are
creating and destroying lots of numbers quickly and that is usually
something you can easily optimize (by re-using numbers) which helps the
performance of both the math/big and the gmp solutions.
On 09/10/13 21:20, Michael Jones wrote:
> How fast is "very much"? More than 2-3x for your program's overall runtime?
>
>
> On Wed, Oct 9, 2013 at 9:38 AM, Nick Craig-Wood <ni...@craig-wood.com
> <mailto:ni...@craig-wood.com>> wrote:
>
> I decided to make an industrial strength drop in replacement for
> math/big using GMP. You can just change the import and enjoy the super
> speed of GMP in your go programs!
>
> https://github.com/ncw/gmp
>
> GMP is very much faster than Go's math/big however it is an external C
> library with all the problems that entails (cgo, dependencies etc)
>
> This library was made by taking the cgo example of wrapping GMP from the
> Go source and doing the following to it
>
> * Copying the implementation from misc/cgo/gmp/gmp.go
> * Copying the documentation from src/pkg/math/big/int.go
> * Additional implementation of missing methods
> * Bug fixes for existing implementations
> * Making it passes the test suite from src/pkg/math/big/int_test.go
> * Adding memory management
> * Fix problems on 32 bit platforms when using int64 values which don't
> fit into a C.long
>
> See here for package docs
>
> http://go.pkgdoc.org/github.com/ncw/gmp
>
> --
> -- http://www.craig-wood.com/nick
>
> --
> You received this message because you are subscribed to the Google
> Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to golang-nuts...@googlegroups.com
> <mailto:golang-nuts%2Bunsu...@googlegroups.com>.
>
> --
> You received this message because you are subscribed to the Google
> Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it,
> send an email to golang-nuts...@googlegroups.com
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate | m...@google.com
> <mailto:m...@google.com> | +1 650-335-5765
>
>
>
>
> --
> Michael T. Jones | Chief Technology Advocate | m...@google.com
Michael Jones
Oct 9, 2013, 7:22:27 PM10/9/13
to Nick Craig-Wood, golang-nuts
Thanks! We need more special multiply cases. There has already been work toward this and it makes sense to review after the release.
--
Nick Craig-Wood
Oct 10, 2013, 7:03:17 AM10/10/13
to Michael Jones, golang-nuts
On 10/10/13 00:22, Michael Jones wrote:
>
> On Wed, Oct 9, 2013 at 2:47 PM, Nick Craig-Wood <ni...@craig-wood.com
> <mailto:ni...@craig-wood.com>> wrote:
>
> To give a concrete example on a pi calculating program, math/big is
> slightly ahead up to a length of 4,000 digits but by 1,000,000 digits
> gmp is 47x times quicker.
>
> Thanks! We need more special multiply cases. There has already been work
> toward this and it makes sense to review after the release.
Don't get me wrong - I think math/big is an amazing piece of work.
>
> On Wed, Oct 9, 2013 at 2:47 PM, Nick Craig-Wood <ni...@craig-wood.com
> <mailto:ni...@craig-wood.com>> wrote:
>
> To give a concrete example on a pi calculating program, math/big is
> slightly ahead up to a length of 4,000 digits but by 1,000,000 digits
> gmp is 47x times quicker.
>
> Thanks! We need more special multiply cases. There has already been work
> toward this and it makes sense to review after the release.
However the sheer number of man years of effort that have gone into GMP
make it very hard to beat in my experience.
BTW I have two patches I'll propose for math/big at some point, one
speeding up the basic arithmetic for ARM and another with some more test
cases.
Rémy Oudompheng
Oct 10, 2013, 7:31:42 AM10/10/13
to Nick Craig-Wood, Michael Jones, golang-nuts
You might be interested in github.com/remyoudompheng/bigfft
for very large integer arithmetic (multiplication).
It is written in Go and shares the existing assembly routines of math/big.
Rémy.
2013/10/10, Nick Craig-Wood <ni...@craig-wood.com>:
for very large integer arithmetic (multiplication).
It is written in Go and shares the existing assembly routines of math/big.
Rémy.
2013/10/10, Nick Craig-Wood <ni...@craig-wood.com>:
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
Jan Mercl
Oct 10, 2013, 7:36:43 AM10/10/13
to Rémy Oudompheng, Nick Craig-Wood, Michael Jones, golang-nuts
On Thu, Oct 10, 2013 at 1:31 PM, Rémy Oudompheng
<remyoud...@gmail.com> wrote:
> You might be interested in github.com/remyoudompheng/bigfft
> for very large integer arithmetic (multiplication).
>
> It is written in Go and shares the existing assembly routines of math/big.
Your package is used by [0] and I can confirm the speedups are as
<remyoud...@gmail.com> wrote:
> You might be interested in github.com/remyoudompheng/bigfft
> for very large integer arithmetic (multiplication).
>
> It is written in Go and shares the existing assembly routines of math/big.
documented. Big (integer) thanks! ;-)
[0]: https://github.com/cznic/mathutil/blob/master/mersenne/mersenne.go#L252
-j
Reply all
Reply to author
Forward
0 new messages