[Python-Dev] Google Summer of Code proposal: improvement of long int and adding new types/modules.

[Tim Peters]

[Mateusz Rukowicz]
>> I wish to participate in Google Summer of Code as a python developer. I
>> have few ideas, what would be improved and added to python. Since these
>> changes and add-ons would be codded in C, and added to python-core
>> and/or as modules,I am not sure, if you are willing to agree with these
>> ideas.
>>
>> First of all, I think, it would be good idea to speed up long int
>> implementation in python. Especially multiplying and converting
>> radix-2^k to radix-10^l. It might be done, using much faster algorithms
>> than already used, and transparently improve efficiency of multiplying
>> and printing/reading big integers.

[Guido van Rossum]
> That would be a good project, if someone is available to mentor it.
> (Tim Peters?)

Generally speaking, I think longobject.c is already at the limit for
what's _reasonable_ for the core to support in C.  In fact, I regret
that we added Karatsuba multiplication.  That grossly complicated
CPython's bigint multiplication code, yet anyone slinging bigints
seriously would still be far better off using a Python wrapper for a
library (like GMP) seriously devoted to gonzo bigint algorithms.

CPython is missing mountains of possible bigint optimizations and
algorithms, and that's fine by me -- the core can't afford to keep up
with (or even approach) the state of the art for such stuff, but there
are already Python-callable libraries that do keep up.

Speeding the decimal module is a more attractive project.  Note that's
an explicit possibility for next month's "Need for Speed" sprint:

    http://mail.python.org/pipermail/python-dev/2006-April/063428.html

Mateusz, if that interests you, it would be good to contact the sprint
organizers.

>> Next thing I would add is multi precision floating point type to the
>> core and fraction type, which in some cases highly improves operations,
>> which would have to be done using floating point instead.

You can have this today in Python by installing the GMP library and
its Python wrapper.

>> Of course, math module will need update to support multi precision
>> floating points, and with that, one could compute asin or any other
>> function provided with math with precision limited by memory and time.
>> It would be also good idea to add function which computes pi and exp
>> with unlimited precision.

I don't think the CPython core can afford to support such
sophisticated and limited-audience algorithms.  OTOH, the decimal type
has potentially unbounded precision already, and the math-module
functions have no idea what to do about that.  Perhaps some non-gonzo
(straightforward even if far from optimal, and coded in Python)
arbitrary-precision algorithms would make a decent addition.  For
example, the Emacs `calc` package uses non-heroic algorithms that are
fine for casual use.

> I would suggest doing this as a separate module first, rather than as
> a patch to the Python core.
>
> Can you show us some practical applications of these operations?

He could, yes, but they wouldn't meet any web developer's definition
of "practical".  The audience is specialized (he says as if web
developers' peculiar desires were universal ;-)).

>> And last thing - It would be nice to add some number-theory functions to
>> math module (or new one), like prime-tests,

GMP again, although the developers note:

    http://www.swox.com/gmp/projects.html
    ...
    GMP is not really a number theory library and probably shouldn't have
    large amounts of code dedicated to sophisticated prime testing
    algorithms, ...

If they think doing much more here is out of bounds for them, trying
to sneak it into longobject.c is crazy :-)  Note that tests like
Miller-Rabin are very easy to code in Python.

> factorizations etc.

Very large topic all by itself.  On Windows, I use factor.exe:

    http://indigo.ie/~mscott/

and call it from Python via os.popen().  That doesn't implement the
Number Field Sieve, but does use most earlier high-powered methods
(including elliptic curve and MPQS).

> Probably better a new module. But how many people do you think need these?

The people who install GMP <0.5 wink>.

>> Every of above improvements would be coded in pure C, and without using
>> external libraries, so portability of python won't be cracked, and no
>> new dependencies will be added.

> Great -- that's important!

Since when does coding a module in pure C do anything for Jython or
IronPython or PyPy besides make their lives more difficult?  It would
be better to code in Python, if the functionality is all that's
desired; but it isn't, and getting gonzo speed too is the proper
concern of libraries and development teams devoted to gonzo-speed math
libraries.

>> I am waiting for your responses about my ideas, which of these you think
>> are good, which poor etc. Main reason I am posting my question here is
>> that, I am not sure, how much are you willing to change the core of the
>> python.

All the things you mentioned are Good Things, solving some real
problems for some real people.  What I question is the wisdom of
trying to implement them in the CPython core, especially when most of
them are already available in CPython via downloading a Python-wrapped
library.

>> At the end, let my apologize for my poor English, I am trying to do my best.

> No problem. We can understand you fine!

Yup!