[seqfan] Re: Implementing first 500 sequences in Java

Charles Greathouse charles.greathouse at case.edu
Fri Oct 29 15:56:25 CEST 2010

As best I can tell
BigInteger only implements naive algorithms: grade-schools
multiplication, basic RTL binary exponentiation, etc.  No Karatsuba or
FFT-based multiplication, no Jebelean exact division, no sliding
window exponentiation, no subquadratic GCD.

So it's not going to be fast, but the results should be trustworthy.

Charles Greathouse
Case Western Reserve University

On Fri, Oct 29, 2010 at 6:02 AM, Richard Mathar
<mathar at strw.leidenuniv.nl> wrote:
>> From: "N. J. A. Sloane"
>> To: seqfan at list.seqfan.eu
>> Subject: [seqfan] Re: Implementing first 500 sequences in Java
>> Does Java do exact arithmetic on large numbers?
>> Can the results of these programs be trusted?
> Java has "ideal" support to arbitrarily large numbers with
> the BigInteger class. Unlike C/C++ or F90 etc, this is a very
> natural reference library for these tasks. I've used this a lot
> in the FI interpreter http://www.strw.leidenuniv.nl/~mathar/progs/FI.html which uses
> mY API of http://www.strw.leidenuniv.nl/~mathar/progs/jdocs .
> There seems to be no standard NumberTheory library on top of that,
> so one has basically start from scratch to "do" prime numbers,
> rationals etc.
> The functionality that is available in the base library is
> documented in http://download.oracle.com/javase/7/docs/api/ (search
> for BigInteger in the lower left panel). Basically this is +, -, *,
> the integer-with-remainder,  power to an integer and some bit manipulations.

More information about the SeqFan mailing list