# [PYTHON MATRIX-SIG] Another problem?

Rob.Hooft@embl-heidelberg.de Rob.Hooft@embl-heidelberg.de
Fri, 16 Aug 1996 21:57:47 +0200 (MET DST)

```>>>>> "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~% cc -O4 -o x x.c -lm -non_shared
nu~% time ./x
Can divide by 2
Can divide by 29
./x  0.03s user 0.02s system 83% cpu 0.060 total

Remember:

nu~% 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~% 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;
sieve=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