Should we have a small programming challenge?

[TaeShadow]

Okay, I've revised my program considerably. I believe this is the fastest solution that can be implemented in Python:

#!/usr/bin/env python

import math, sys

try:
  number = long(sys.argv[1])
except ValueError:
  print "Must enter an integer!"
  sys.exit(1)
  
found = 0

print "Factors: "

s = math.sqrt(number)
f = 1

while f != s:
  if number % f == 0:
    print f, number / f
    found = found + 1
  f = f + 1

[TaeShadow]

Oops... There were some bugs in that last one. *Here's the correct version:

#!/usr/bin/env python

import math, sys

try:
 * *number = long(sys.argv[1])
except ValueError:
 * *print "Must enter an integer!"
 * *sys.exit(1)

print "Factors: "

s = long(math.sqrt(number) + 1)
f = 1
found = 0

while f != s:
 * *if number % f == 0:
 * * * *print f, number / f
 * * *found = found + 1
 * *f = f + 1 *

[kenshi]

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.

That is sometimes the case but not always. Sometimes companies just want you to put out something that works. In that case, yours would be better. You took a few minutes while I took two days. But sometimes speed and effeciency are very important. Operating systems are an example of this (except for Windows). You're expected to take a while in order to make it work well. You know about how fast your program is. Mine takes probably about 25 or 30 clock ticks for each factor. The number of factors is equal to the square root of the number. So for one quadrillion, it would make about 30 million passes. Multiply the two and you get about 1 billion. That seems like a lot but on an 850 Mhz processor, it takes just over a second. I may be off a little on the clock ticks though because the div instruction can take different numbers of ticks. That doesn't include the printf functions for each factor and the initial stuff in the main function. I could have written it all in assembler to make that faster too but it would have been quite difficult with little gain and it wouldn't have been cross platform. But anyway, since this is a contest, you can't diss on me for taking the time to think about speed and power. I'm winning as far as speed goes so eat that.

[kenshi]

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

Well if you changed it, where's the code for it? Just to let you people know though, the time command says the same thing no matter what number I use so for me to test yours, I'll have to use a number that takes a few seconds at least.

[kenshi]

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

That is horribly inefficient. You probably initially told it to go all the way up to the number instead of the square root of the number. But still, it would make a billion passes. For mine to make a billion passes, I'd have to use the number one quintillion, and I estimate it would take about 5 minutes.

Actually, I started it when I started typing this message and it just finished. It probably took about a minute.

[pbharris]

Well if you changed it, where's the code for it? Just to let you people know though, the time command says the same thing no matter what number I use so for me to test yours, I'll have to use a number that takes a few seconds at least.

i'll post it tonight. all it is changing how the arguments are input and how i switch from a unsigned int (16 bit) to a long unsigned int.

[kenshi]

i'll post it tonight. all it is changing how the arguments are input and how i switch from a unsigned int (16 bit) to a long unsigned int.

That still may not be large enough for me to test it. With 32-bit, you can only go up to about 4 billion. My program does a trillion in about 1/4 of a second and I'm sure yours isn't much slower. A billion will probably be nearly instantaneous.

By the way, I realised that I can only factor up to about 4 quadrillion. Sure that's an insanely large number but it only takes a few minutes to factor. I kind of wanted to give it a huge number like 10 sextillion and let it run while I go to work. It would be hard to push it to 96-bit though since there's no defined 96-bit integer in C. I could integrate it easily into the assembler code though. Would someone like to help me create a 96-bit or 128-bit factoring program just for kicks? I'll take the assembler part if you take the C part.

[pbharris]

the reason i ask *that* number is because there are 672 different factors for it - thats quite a few.

[kenshi]

Did you know 1,000,000,000,000,037 is a prime factor? It's the first prime factor after 1 quadrillion. I was wondering how often prime numbers occurred that high so I checked it out.

By the way, I'm considering making assembler functions to replace printf and square_root so I can use 128-bit numbers. Is that insane or what? Does anyone know if the fpu can handle anything above 80-bit? I'll need some big time precision when finding the square roots of those huge numbers.

[pbharris]

Did you know 1,000,000,000,000,037 is a prime factor? It's the first prime factor after 1 quadrillion. I was wondering how often prime numbers occurred that high so I checked it out.

By the way, I'm considering making assembler functions to replace printf and square_root so I can use 128-bit numbers. Is that insane or what? Does anyone know if the fpu can handle anything above 80-bit? I'll need some big time precision when finding the square roots of those huge numbers.

i dunno aout the hights prime numbers, i'll take your word for it.

yes that would be insane to replace printf() and sqrt().