I get about 26 seconds to multiple billion bit (2^10^9-1) numbers with
Gambit-Scheme <http://gambitscheme.org/> (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?
> On Jul 22, 2017, at 8:19 AM, Rémy Oudompheng <remyoudomph...@gmail.com> 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.
>
> 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.
--
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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
