[PYTHON MATRIX-SIG] Another problem?

[Rob.Hooft@embl-heidelberg.de]

>>>>> "JH" == Jim Hugunin <hugunin@mit.edu> writes:

 JH> I doubt that my new version is more than a factor of 2 slower
 JH> than a C implementation of the same algorithm (though feel free
 JH> to show me wrong with a code sample).

I decided to accept that challenge:

   nu[263]~% cc -O4 -o x x.c -lm -non_shared
   nu[264]~% time ./x                       
   Can divide by 2
   Can divide by 29
   ./x  0.03s user 0.02s system 83% cpu 0.060 total

Remember:

   nu[265]~% python ./x.py 
   Can divide by 2
   Can divide by 29
   factor took  10.354 seconds
   Can divide by 2
   Can divide by 29
   afactor took   0.573 seconds

and, yes the machine is "empty", so clock-times are comparable. And:
changing the array to type='b' makes the python version slower, so
I'm not being unfair.... The only trick I've added is making the thing
non-recursive, but I doubt that change would make the python version
much faster.

   nu[266]~% python
   Python 1.4b2 (Aug 12 1996) [C]
   Copyright 1991-1996 Stichting Mathematisch Centrum, Amsterdam
   >>> 0.573/0.060 > 2.0
   1
   >>> 

-----------------------------------

#include <stdio.h>
#include <math.h>
#include <malloc.h>

#define bool char
int *sieve(int max)
{
  bool *sieve;
  int *result;
  int i,j,limit;
  sieve=(bool *)malloc((max+1)*sizeof(bool));
  for (i=0;i<=max;i++) sieve[i]=1;
  sieve[0]=0;
  sieve[1]=0;
  limit=floor(sqrt((float)max));
  for (i=2;i<=limit;i++) {
    if (sieve[i]) {
      for (j=i*i;j<=max;j+=i) sieve[j]=0;
    }
  }
  j=0;
  for (i=2;i<=max;i++) j+=sieve[i];
  /*printf("Sieve contains %d primes\n",j);*/
  result=(int *)malloc((j+1)*sizeof(int));
  j=0;
  for (i=2;i<=max;i++) if (sieve[i]) result[j++]=i;
  result[j]=0;
  free(sieve);
  return(result);
}

void factor(int a,int max)
{
  int *s;
  int i;
  if (max<2) return;
  s=sieve(max);
  for (i=0;s[i];i++) {
    if (!(a%s[i])) {
      printf("Can divide by %d\n",s[i]);
    }
  }
  free(s);
}

int main() {
  factor(129753308,99999);
  exit(0);
}

=================
MATRIX-SIG  - SIG on Matrix Math for Python

send messages to: matrix-sig@python.org
administrivia to: matrix-sig-request@python.org
=================