Re: integer multiplication

References	<BANLkTik5Oq0AE5-yrbSa2oES5_g8+gspeA@mail.gmail.com> <AANLkTimsXzAxUBcL=Z8CbUcgGVmw-=_Dp=Z-zAb1u24j@mail.gmail.com> <BANLkTim6fV0tW9ZB07q6xxtYrwZ5mB__+w@mail.gmail.com>
Date	2011-04-03 18:46 -0700
Subject	Re: integer multiplication
From	geremy condra <debatem1@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.178.1301881618.2990.python-list@python.org> (permalink)

Show all headers | View raw

On Sun, Apr 3, 2011 at 6:41 PM, Eddie Tsay <jianyu44@gmail.com> wrote:
>
> On Sun, Apr 3, 2011 at 6:33 PM, geremy condra <debatem1@gmail.com> wrote:
>>
>> On Sun, Apr 3, 2011 at 6:20 PM, Eddie Tsay <jianyu44@gmail.com> wrote:
>> > Does anyone know what algorithms for integer multiplication does Python
>> > use?
>> > I am trying to compare it to those used by Sage as it seems like it
>> > takes
>> > much longer for Python to do large integer multiplication as compared to
>> > Sage (anyone know off the top of their heads?)
>> > thank you
>>
>> (sorry for the double email, this was supposed to go to the list)
>>
>> Karatsuba multiplication, at least for large integers.
>>
>> Geremy Condra
>
>
> Thank you for replying to my question.
> Do you have any idea how I would be able to find how they do this
> multiplication in the python source code? I've been poking around the
> documentation and can't find the area where they outline it.
> Thank you for your reply =)
> Eddie

In the Python3 source tarball its in Objects/longobject.c. I only have
the 3.2a1 tarball on this machine, but I found the 'grade school'
method implemented in x_mul on line 2765 of that file and karatsuba
multiplication as k_mul on line 2890. YMMV depending on what version
you're looking at.

Just as a side-note, top-posting is considered a minor breach of
netiquette on python-list. I've rearranged the reply correctly here.

Geremy Condra

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: integer multiplication geremy condra <debatem1@gmail.com> - 2011-04-03 18:46 -0700

csiph-web