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

[Mateusz Rukowicz]

Alex Martelli wrote:

>I see "redo Decimal in C" (possibly with the addition of some fast
>elementary transcendentals) and "enhance operations on longs"
>(multiplication first and foremost, and base-conversions probably
>next, as you suggested -- possibly with the addition of some fast
>number-theoretical functions) as two separate projects, each of just
>about the right magnitude for an SoC project. I would be glad to
>mentor either (not both); my preference would be for the former -- it
>appears to me that attempting to do both together might negatively
>impact both.  Remember, it isn't just the coding...: thorough testing,
>good docs, accurate performance measurements on a variety of
>platforms, ..., are all important part of a project that, assuming
>success, it's scheduled to become a core part of Python 2.6, after
>all.
>
>
>Alex
>
>  
>
If it's enough, that's ok for me - I would concentrate on one thing and 
very likely do it better. My main reason of doing these both at the same 
time, was that, these would share many code, and since I did quite a bit 
research in this area (comparing algorithms with diffirent complexity, 
comparing diffirent cache-friendly implementations, timing on machines 
starting at p200 ending at dual Xeon 3GHz), I have quite a experience in 
that stuff. But anyway, conforming to Tim Peters mail, It's not likely 
something will change in long int ;) - I understand that, and don't want 
to change you developing python policy (actually, I was expecting that, 
when I realized that multiply is karatsuba-only).
Here is a little comparsion made by my friend python vs my 
implementation of multiplying (coded in C, without any assembly - I have 
also assembly version ;P)
http://parkour.pl/mat.png
It computes product of k*l log(k) = log(l), X axis is sqrt(n), where 
O(n) = O(logk), in other words, n is 'length' of numbers.
I think, that decimal coded in C by me would achieve quite similiar time 
(also I would eliminate 'staircase' effect), if you wish.
I am quite efficiency concerned, in my opinion, efficiency is third most 
important thing after easy-to-use-code and functionality, and should not 
be forgetten. Also I state that efficient code/algorithms isn't 
necessary hard to maintain. And all in all, these algorithms are not so 
complicated, (in my opinion, fft multiply - which is assymptoticly the 
best - is less complicated than karatsuba, but that's my opinion).

I am now quite sure, what I would like to do, and is possible by you to 
accept - code decimal in C, most important things about that would:
1.Compatibility with old decimal
1.easy to maintain and expand code
1.don't broke python portability, nor adding new depedencies
2.Efficiency (if and only if 1. isn't broke)
I am quite confident I can achieve this points.
But everything is open for discussion ;) I'd like to know as much as 
possible what do you think about this idea. (But already i know quite much)

Best regards,
Mateusz Rukowicz.