Should we have a small programming challenge?

[pbharris]

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

#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:

./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

[kenshi]

How can it use 110% cpu? Don't worry, this next version of mine is going to fly.

[kenshi]

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:

nasm -f elf factor.asm
gcc -g -lm main.c factor.o -o factor

main.c:

#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;
}

factor.asm:

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

Isn't she beautiful?

[Feztaa]

How do you time your program?

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.

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.

[kenshi]

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.

time factor 1000000000
real 0m0.003s
user 0m0.000s
sys 0m0.003s

I'm still working on a 64-bit version by the way. See my other post (when I post it).

[pbharris]

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 ?

[kenshi]

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.

[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]%

[kenshi]

[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.