Kenshi:
Code:./factor.rb 100000000 0.06s user 0.00s system 110% cpu 0.054 total ./factor.rb 1000000000 0.13s user 0.00s system 97% cpu 0.133 total ./factor.rb 10000000000 0.81s user 0.02s system 99% cpu 0.830 total
i needed to do the -lm to get the object file which has sqrt() defined linked in - per a google search. anywho - here is my response, kinda sucky because there are redundant #'s and little error checking and i am sure it could be done with fewer lines.
it under debian and redhat it compiles fine with
gcc -lm -o numfact numfact.c
Code:#include<stdio.h> #include<math.h> /* okay lets find all pairs of factors for an input number * all input numbers must be integers greater than zero * and checked to see if it is valid. Number must also be * less than the maximum value for a unsigned interger (16 bits) */ #define TRUE 1 #define FALSE 0 #define START 1 int is_valid(int num); /* determines if passed value is okay */ void factor_num(int num); /* factors the numbers */ int main() { int number; /* get value from user */ puts("enter an interger greater than zero to get its factors \n"); scanf("%d",&number); if (is_valid(number)==FALSE) { exit(0); } factor_num(number); return(0); } /* lets see if we were passed garbage - this will return * FALSE if the input is not valid and TRUE if the input * is valid */ int is_valid(int num) { if (num > 65536) { puts("that number is too fucking big \n"); return(FALSE); } else if (num <= 0) { puts("either thats zero - or less than zero \n"); return(FALSE); } else { return(TRUE); } } /* this will find all pairs of numbers which are factors of the * number passed in and print them. */ void factor_num(number) { int *val1; int *val2; int index = START; /*start at 1, number and 1 will always be factors */ int total_factor_pairs = 1; /* there will always be one pair*/ int i; float lowlim,highlim; val1= (int*)malloc(256*sizeof(int)); val2= (int*)malloc(256*sizeof(int)); if(number <= 3) { lowlim = 1; } else { lowlim = sqrt(number) ; } highlim = number/2; *val1 = number; *val2 = 1; /*only need from the sqrt of num ber to 1/2 number */ for ( i = lowlim; i <= highlim ; i++) { if(number%i == 0) { total_factor_pairs++; *(val1+index) = number/i; *(val2+index) = i; index++; } } puts(" "); printf("there are %d factor pairs, they are:\n",total_factor_pairs); for(i = total_factor_pairs-1 ;i >= 0 ;i--) { printf("\t %d \t %d \n",*(val1+i),*(val2+i)); } }
Kenshi:
Code:./factor.rb 100000000 0.06s user 0.00s system 110% cpu 0.054 total ./factor.rb 1000000000 0.13s user 0.00s system 97% cpu 0.133 total ./factor.rb 10000000000 0.81s user 0.02s system 99% cpu 0.830 total
How can it use 110% cpu? Don't worry, this next version of mine is going to fly.
How do you time your program? Now mine factors 1 billion seemingly instantaneously so I need a way to check the precise time. Unfortunately, since it's only 32-bit, I can't input a number over 2 ^ 31 (just over 2 billion) or it will act funny. I would like to go to 64-bit but frankly I have no idea how to get atol to convert a 64-bit number or sqrt to use one. But anyway, here's my program finally. It uses C for the user interfacing and assembler for the heavy duty math work. It's a real speed demon. Since the assembler part doesn't use any system calls, you can compile this in any x86 32-bit operating system (including Windows) if you can get Nasm for it or adjust the syntax to whatever assembler you use. Here she is:
Compilation commands:
main.c:Code:nasm -f elf factor.asm gcc -g -lm main.c factor.o -o factor
factor.asm:Code:#include <stdio.h> #include <math.h> extern void factor(int); unsigned long square_root(unsigned long number) { double temp; temp = (double)number; temp = sqrt(temp); number = (unsigned long)temp; return number; } int main(int argc,char *argv[]) { unsigned long number; if(argc != 2) { printf("You must type in a factor for a parameter.\n"); return 1; } if(isnumber(argv[1])) { printf("Parameter must be valid decimal number.\n"); return 1; } number=atol(argv[1]); factor(number); return 0; }
Isn't she beautiful?Code:SEGMENT .data fmt db '%d %d',10,0 sroot dd 0 extern printf extern square_root global factor SEGMENT .text factor: push ebp mov ebp,esp push esi push edi push ebx mov ebx,ebp add ebx,08h mov esi,dword [ebx] ; that was complicated but now we have the parameter passed from main in edx push esi call square_root mov edi,eax add esp,04h mov ecx,0h ; ecx will be incremented in the loop and we want to start factoring with 1 find_factors: inc ecx cmp ecx,edi ; if ecx has passed root, return jng divide pop ebx ; let's return cleanly to mother pop edi pop esi pop ebp ret divide: mov edx,0 ; high 32 bits of dividend always 0 mov eax,esi ; move our number to eax to be divided div ecx ; divide by the divisor cmp edx,0 ; is remainder 0? jnz find_factors ; next factor if remainder push ecx ; preserve ecx push eax ; pass the quotient push ecx ; pass our factor push dword fmt ; pass the format string call printf ; let's do this the easy way and use printf add esp,0Ch ; clean up after printf pop ecx jmp find_factors ; continue with the next factor
There's a program called time which will time how long it takes to run a program. I'm not sure if it comes with all systems, but it really is handy.How do you time your program?
Just run time program instead of program at the command line, and it will let the program execute normally, while at the same time timing how long it took.
I'm not sure how to read this. Nevertheless I know it's better than GnuVince's. [smiles] Here's what mine says minus the first line which looks like gibberish. I factored 1 billion.
I'm still working on a 64-bit version by the way. See my other post (when I post it).Code:time factor 1000000000 real 0m0.003s user 0m0.000s sys 0m0.003s
that is pretty sweet Kenshi - how do you get the arguement passed in at call time time? i.e. factor 10000 - mine prompts user and waits... is it the argc ?
Argc specifies how many arguments were passed at the command line. Argv is an array of pointers pointing to the strings holding the parameters. First I make sure there were two arguments passed (the command itself counts as an argument). Then, argv[0] is the command, so I make sure argv[1] is a number (although that's not working right now). Then I convert it to a long and pass it to the assembler function. I'm trying to use a long long as you can see in my other thread but conversion is proving to be a bitch.that is pretty sweet Kenshi - how do you get the arguement passed in at call time time? i.e. factor 10000 - mine prompts user and waits... is it the argc ?
[vince@vincent: ~/prog/vitesse]% nasm -f elf factor.asm
[vince@vincent: ~/prog/vitesse]% gcc -lm main.c factor.o -o factor /tmp/ccyrQgmQ.o: In function `main':
/tmp/ccyrQgmQ.o(.text+0x94): undefined reference to `isnumber'
collect2: ld returned 1 exit status
[vince@vincent: ~/prog/vitesse]%
Strange, it compiles on mine. Just delete the if part with isnumber and make sure you type in a parameter as a number. I'm not going for superb error handling at the moment.[vince@vincent: ~/prog/vitesse]% nasm -f elf factor.asm
[vince@vincent: ~/prog/vitesse]% gcc -lm main.c factor.o -o factor /tmp/ccyrQgmQ.o: In function `main':
/tmp/ccyrQgmQ.o(.text+0x94): undefined reference to `isnumber'
collect2: ld returned 1 exit status
[vince@vincent: ~/prog/vitesse]%
Bookmarks