Math on Huge (2GB) numbers in GoLang

[me]

How does GoLang compare to other languages for mathematics dealing with really large numbers?

Prefer the ability to work with 2GB sized strings as numbers (need much bigger than int64)

I see there is this:
https://golang.org/pkg/math/big/

And probably some other github projects for math in go?

Is Python and Mathematica better at handling super large numbers? Plain C? C++ ? Javascript?

I need to start working with some massive numbers, but am unsure to choose Go - as I don't have experience in Go Mathematics units yet.

[Hugh S. Myers]

Like everything else, 'it depends…'

Do you want speed?

Do you want the bulk of the coding already available as a library/module?

With or without a user interface?

Answer those first and then ask again.

Oh! Replace Javascript with Perl…

--
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+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Rémy Oudompheng]

math/big is the standard package for big integer arithmetic in Go, and
it is quite fast.
For your huge numbers, it all depends on which operations you need to do.
For example, the math/big package uses Karatsuba multiplication, which
cannot handle 2GB numbers in a reasonable amount of time.

I wrote a little module (github/remyoudompheng/bigfft) to play with
FFT-based multiplication of huge integers, while maintaining
interoperability with the math/big package.

On my computer, it multiplies 1Gbit numbers (300MB strings when
printed in base 10), in 24 seconds (the GMP library does it in 9.3
seconds). I assume that it would multiply your 2GB strings (6 Gbit
numbers) in about 2 minutes.

You are welcome to try it.

Regards,
Rémy.

[Rémy Oudompheng]

The most annoying issue you might encounter is that if your 2GB
strings are numbers printed in base 10, the math/big will not be able
to parse them in a reasonable time using the standard method
(SetString).

Rémy.

[Hugh S. Myers]

Is math/big pari based?

Rémy.

[Rémy Oudompheng]

The math/big library has basic routines implemented in assembly for
most common architectures, with all the math written in Go atop those.

Rémy.

>> email to golang-nuts...@googlegroups.com.

[Hugh S. Myers]

Ah! Excellent solution. I wrote one of the early multiple precision packages for the C users group in the 80's and I typically wrote in C first, then disassembled and reduced the code and re-assembled again. Not the best approach, but it allowed some exciting prime number research for the time…

>> email to golang-nuts+unsubscribe@googlegroups.com.

[Michael Jones]

Oh no! I wrote some of that code. Maybe I should revisit.

>> email to golang-nuts...@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.
>
>

--
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/d/optout.

--

Michael T. Jones
michae...@gmail.com

[Bakul Shah]

I get about 26 seconds to multiple billion bit (2^10^9-1) numbers with Gambit-Scheme (which has a built-in FFT multiplier written in Scheme by Brad Lucier). On the same hardware your bigfft packet takes about 24s for multiplying two billion digit numbers. GMP is of course much faster.

But multiplication is not the only interesting operation! Here are Gambit numbers for *, quotient, integer-sqrt and gcd.

> (define a (expt 3 20959032))

> (define b (expt 7 11832946))

> (define c (expt 11 19205051))

> (define d (time (* a b)))

(time (* a b))

    622 ms real time

    622 ms cpu time (578 user, 44 system)

    2 collections accounting for 16 ms real time (1 user, 15 system)

    82336 bytes allocated

    18576 minor faults

    no major faults

> (define e (time (quotient c a)))

(time (quotient c a))

    3378 ms real time

    3361 ms cpu time (2918 user, 443 system)

    6 collections accounting for 174 ms real time (2 user, 171 system)

    2177936 bytes allocated

    229194 minor faults

    no major faults

> (define f (time (integer-sqrt c)))

(time (integer-sqrt c))

    3767 ms real time

    3728 ms cpu time (3233 user, 495 system)

    12 collections accounting for 191 ms real time (4 user, 187 system)

    15776000 bytes allocated

    254536 minor faults

    no major faults

> (define g (time (gcd a b)))

(time (gcd a b))

    73149 ms real time

    72645 ms cpu time (67239 user, 5406 system)

    1094 collections accounting for 2062 ms real time (417 user, 1618 system)

    33945273504 bytes allocated

    2987926 minor faults

    no major faults

>

Are there faster, cache oblivious algorithms for these?

[me]

On Saturday, July 22, 2017 at 9:19:44 AM UTC-6, Rémy Oudompheng wrote:

I wrote a little module (github/remyoudompheng/bigfft) to play with
FFT-based multiplication of huge integers, while maintaining
interoperability with the math/big package.

I think I saw that on Github and starred it the other day, thanks...
 

On my computer, it multiplies 1Gbit numbers (300MB strings when
printed in base 10), in 24 seconds (the GMP library does it in 9.3
seconds). I assume that it would multiply your 2GB strings (6 Gbit
numbers) in about 2 minutes.

That is acceptable. Does it ever change speed depending on what type of numbers you feed it?

For example adding 1111111111 *  2222222222
Versus some more complex number

4589347587934 * 874589371596

 As we all know benchmarks can give a false sense ;-)
Depending on inputs/parameters.

(but that may be for me to find out!)

[me]

On Saturday, July 22, 2017 at 9:06:03 AM UTC-6, hsmyers wrote:

Like everything else, 'it depends…'

Do you want speed?

At some point, speed will become important, but if it's under 1 minute or around 2 minutes it's "good enough"...
 

Do you want the bulk of the coding already available as a library/module?

Indeed, there is also this:

https://github.com/salviati/gogmp
 
Go bindings to gmp (c library)

And:
https://github.com/scorpioncompute/go-bigmath
And:
https://github.com/jsimnz/biggish
And:
https://github.com/YuriyNasretdinov/big

With or without a user interface?

When a user interface is needed, indeed Go is not so great for Desktop software:
but that's easily solved by: HTML 5 (or less) interface, chromium embedded interface (but, is large to ship DLL's with app)

Answer those first and then ask again.

Oh! Replace Javascript with Perl…

I thought that so many people use javascript for so many things, that it would have some strange maths stuff out there, possibly even fast.

[me]

p.s. if the c library GMP was written in times without 8 core processors, wouldn't go be able to use multiple processors better than GMP can? Or, GMP has been modified to utilize more processors recently..

Sorry, I know absolutely nothing about GMP, just that it exists. And, I'm not aware of the backbones of the mathematics algorithms, if they can use multiple processors (or goroutines) to do calculations or whether it is more of a serial one cpu problem to solve for the programmer.

This may help me (or any interested):

https://www.google.ca/search?q=gmp+multiple+cores

https://stackoverflow.com/questions/7901752/parallel-arbitrary-precision-arithmetic-library

Quote "The answer is yes, multi-threaded arbitrary-precision libraries do exist. But I'm not aware of a single one that is actually public. (with comparable speed to GMP)"

Interesting...

[me]

On Saturday, July 22, 2017 at 9:37:16 AM UTC-6, Rémy Oudompheng wrote:

The most annoying issue you might encounter is that if your 2GB
strings are numbers printed in base 10, the math/big will not be able
to parse them in a reasonable time using the standard method
(SetString).

Rémy.

2GB is just a rough estimate, it can be maybe 300MB (that's fine too).
The point is I will be working with massive numbers - not important exactly how big, but, bigger is better.

I will indeed be printing in Base 10, but also in Base 27 of my own number system I invented using characters (A-Z plus underscore) for a new mathematical theory.
That's to start, then maybe some other base used later greater than 27, but will still need to convert to base 10 often.

I have downloaded your bigfft from github and will be doing work with it, thanks!

[Michael Jones]

The nat->string code allows any base -- or at least it did -- but it was not exposed in the Int APIs. Maybe you'll want to access the sources.

--

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+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.