# Thread: Should we have a small programming challenge?

1. ## Re: Should we have a small programming challenge?

thanks Kenshi - works like a cham.

2. ## Re: Should we have a small programming challenge?

She works! After an insane amount of debugging, she finally works! I had to do 64 bit division by doing 32 at a time. I was trying to make it harder than it really was. Now that I know how, I could do any size of numbers, though I think anything beyond 2 ^ 64 would take longer than anyone would care to wait for. The time command seems to show pretty much the same time for anything I put in, so I'm a little skeptical of what it's saying. The time should be proportional to the square root of what you factor. But anyway, here's the new revised source code. Compile it the same as before. And I removed that isnumber crap so you shouldn't have to edit this to get it to work. This is a winner for sure. By the way, I was so frustrated that I didn't comment a lot of the new stuff. I doubt anyone was interested in looking through the assembler code anyway.

main.c:
Code:
```#include &lt;stdio.h&gt;
#include &lt;math.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;limits.h&gt;

extern void factor(long long);

unsigned long square_root(unsigned long long number)
{
double temp;
temp = (double)number;
temp = sqrt(temp);
number = (unsigned long long)temp;
return number;
}

int main(int argc,char *argv[])
{
unsigned long long number;
if(argc != 2)
{
printf(&quot;You must type in a single factor for a parameter.\n&quot;);
return 1;
}
number=strtoull(argv[1],0,10);
factor(number);
return 0;
}```
factor.asm:
Code:
```SEGMENT .data
fmt db '%lu %llu',10,0
number dd 0,0
sroot dd 0
extern printf
extern square_root
global factor
quotient dd 0,0

SEGMENT .text
factor:
push esi
push edi
push ebx
mov ebx,esp
mov eax,[ebx]
mov [number+4],eax
mov edx,[ebx]
mov [number],edx

; that was complicated but now we have the parameter passed from main in number

push dword [number]
push dword [number+4]
call square_root
mov [sroot],eax

mov ecx,0h ; ecx will be incremented in the loop and we want to start factoring with 1

find_factors:
inc ecx
cmp ecx,[sroot] ; if ecx has passed root, return
jng divide
pop ebx ; let's return cleanly to mother
pop edi
pop esi
ret

divide:
mov edx,0 ; dividing little pieces at a time
mov eax,[number] ; high 32 bits of dividend
div ecx ; divide by the divisor
mov [quotient],eax
mov eax,[number+4]
div ecx
mov [quotient+4],eax

cmp edx,0 ; is remainder 0?
jnz find_factors ; next factor if remainder
push ecx ; preserve ecx
push dword [quotient] ; pass the quotient
push dword [quotient+4]
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,010h ; clean up after printf
pop ecx
jmp find_factors ; continue with the next factor```

3. ## Re: Should we have a small programming challenge?

OK, kenshi wins the prize for the fastest program (in the compiled languages category) and also for the most complicated one (all categories)

4. ## Re: Should we have a small programming challenge?

By the way, since time is acting funny, I did my own calculations. It can factor one quadrillion (10 ^ 15) in about 6 seconds. Is that beautiful or what? I don't think ruby can touch that.

5. ## Re: Should we have a small programming challenge?

By the way, since time is acting funny, I did my own calculations. It can factor one quadrillion (10 ^ 15) in about 6 seconds. Is that beautiful or what? I don't think ruby can touch that.
I coded my program in 5 minutes. *You took much more time. *And human time is money, so I'm more economic than you, so bosses like me better *And I bet 10\$ that more people could understand my program than yours.

Edit:
Code:
`./factor.rb 1000000000000000 249.52s user 1.04s system 96% cpu 4:18.44 total`

6. ## Re: Should we have a small programming challenge?

Hum, are you sure your program works? I mean I tried with one quadrillion. Here's my output:
Code:
```1 and 1000000000000000
2 and 500000000000000
4 and 250000000000000
5 and 200000000000000
8 and 125000000000000
10 and 100000000000000
16 and 62500000000000
20 and 50000000000000
25 and 40000000000000
32 and 31250000000000
40 and 25000000000000
50 and 20000000000000
64 and 15625000000000
80 and 12500000000000
100 and 10000000000000
125 and 8000000000000
128 and 7812500000000
160 and 6250000000000
200 and 5000000000000
250 and 4000000000000
256 and 3906250000000
320 and 3125000000000
400 and 2500000000000
500 and 2000000000000
512 and 1953125000000
625 and 1600000000000
640 and 1562500000000
800 and 1250000000000
1000 and 1000000000000
1024 and 976562500000
1250 and 800000000000
1280 and 781250000000
1600 and 625000000000
2000 and 500000000000
2048 and 488281250000
2500 and 400000000000
2560 and 390625000000
3125 and 320000000000
3200 and 312500000000
4000 and 250000000000
4096 and 244140625000
5000 and 200000000000
5120 and 195312500000
6250 and 160000000000
6400 and 156250000000
8000 and 125000000000
8192 and 122070312500
10000 and 100000000000
10240 and 97656250000
12500 and 80000000000
12800 and 78125000000
15625 and 64000000000
16000 and 62500000000
16384 and 61035156250
20000 and 50000000000
20480 and 48828125000
25000 and 40000000000
25600 and 39062500000
31250 and 32000000000
32000 and 31250000000
32768 and 30517578125
40000 and 25000000000
40960 and 24414062500
50000 and 20000000000
51200 and 19531250000
62500 and 16000000000
64000 and 15625000000
78125 and 12800000000
80000 and 12500000000
81920 and 12207031250
100000 and 10000000000
102400 and 9765625000
125000 and 8000000000
128000 and 7812500000
156250 and 6400000000
160000 and 6250000000
163840 and 6103515625
200000 and 5000000000
204800 and 4882812500
250000 and 4000000000
256000 and 3906250000
312500 and 3200000000
320000 and 3125000000
390625 and 2560000000
400000 and 2500000000
409600 and 2441406250
500000 and 2000000000
512000 and 1953125000
625000 and 1600000000
640000 and 1562500000
781250 and 1280000000
800000 and 1250000000
819200 and 1220703125
1000000 and 1000000000
1024000 and 976562500
1250000 and 800000000
1280000 and 781250000
1562500 and 640000000
1600000 and 625000000
1953125 and 512000000
2000000 and 500000000
2048000 and 488281250
2500000 and 400000000
2560000 and 390625000
3125000 and 320000000
3200000 and 312500000
3906250 and 256000000
4000000 and 250000000
4096000 and 244140625
5000000 and 200000000
5120000 and 195312500
6250000 and 160000000
6400000 and 156250000
7812500 and 128000000
8000000 and 125000000
9765625 and 102400000
10000000 and 100000000
10240000 and 97656250
12500000 and 80000000
12800000 and 78125000
15625000 and 64000000
16000000 and 62500000
19531250 and 51200000
20000000 and 50000000
20480000 and 48828125
25000000 and 40000000
25600000 and 39062500
31250000 and 32000000
128 pairs of factors found!```
and here's the output with your program:
Code:
```1 13835052456792293375
5 2767010491358458675
11 1257732041526572125
25 553402098271691735
55 251546408305314425
125 110680419654338347
275 50309281661062885
1375 10061856332212577```
???

7. ## Re: Should we have a small programming challenge?

Forget it. I forgot to change the C program. Your program works fine.

8. ## Re: Should we have a small programming challenge?

not to take sides but i am willing to bet kenshi's takes a whole lot less memory and OS support - and if this were a calculator we are trying to build then i am guessing the memory and OS system resources are at a premium. *for my job we need small small foot prints for everything. *

9. ## Re: Should we have a small programming challenge?

okay - i changed mine to handle bigger numbers - i am curious as to what you people got with this number: 1269777600

mine is:

real 0m42.851s
user 0m36.170s
sys 0m0.000s
i am sure CPU speed matters - this is a 1200 MHz athalon.

10. ## Re: Should we have a small programming challenge?

Hehe... Obviously my algorithm is horribly inefficient. I had it factor 1 billion, went out for breakfast, lunch, and a few more hours, came back and it was still thinking...

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•