Dumb python questions

[Paul Rubin]

"Alex Martelli" <aleaxit at yahoo.com> writes:
> Unfortunately, gmpy just relies on GMP, which in turn only has the
> carefully tuned machine-language inner loops on a few selected
> architectures -- elsewhere they're replaced by carefully-coded C
> which, indeed, cannot be quite as fast.  I noticed because at first
> I only had a C-only version of GMP for Windows/VC++6; when I
> moved to a GMP version including the port of the assembly part,
> performance soared [and another boost came from switching to
> an Athlon chip from a pure-Intel one -- so I sort of suspect that
> there should probably be different machine-language inner loops
> for top performance on Athlon vs Pentium3, given different
> caching, branch-prediction, etc, etc].  Unfortunately I did no
> careful measurements (mea culpa!) so thanks for giving them...

The main bottleneck in C is integer multiplication.  Most computers
have an integer multiply instruction that multiplies two words and
gives a doubleword result (32*32->64 bits), so in asm you just use it.
There's not a good way to code that portably in C, so you end up using
four 16*16->32 multiplications instead of one 32*32->64
multiplication.  That slows you down by a factor of 4 right away.
The other differences coming from e.g. differences in cpu architecture
between x86 variants are minor by comparison.  One exception: the
original Pentium had a much faster FMUL (floating point mul) instruction
than IMUL, and it paid off to totally reorganize the bignum calculation
to do the intermediate calculations in floating point.

  ftp://ftp.compapp.dcu.ie/pub/crypto/timings.doc

(an MS Word file, unfortunately) has a bunch of description of how
to do fast bignum arithmetic.  See also http://indigo.ie/~mscott
for some benchmarks.


> > in portable C.  Python's arithmetic is around 100x faster than
> > perl's Math::BigInt.
> 
> Interesting -- I guess (and hope, because competition is what
> keeps everybody on their toes:-) that some devoted Perlist is
> already busy recoding their big-int module for performance?-)

I think there are GMP and other native C extensions for fast
arithmetic in Perl.  Math::BigInt is written in pure Perl,
representing long ints as strings.  That's why it's so slow.