C Coding Competition - Win an Arduino

[slateraptor]

...it's much more efficient to generate perfect numbers from Mersenne primes than by factorising each positive integer.

*giggles*

Is that an offer? :p

I'm tempted to say sure for shits and grins...but I think I'll pass. I wouldn't want to spoil a good learning opportunity.

[_Sin]

Yours can still be improved though as your primeality test is fairly simplistic - perhaps by dividing by primes less than the square root of the number of interest, rather than potentially by all integers >= 3. Or even just dividing by odd numbers.

Chet T16 - the code I posted was intentionally a bit simplistic but if you are a beginner in C programming it is probably worth making sure you understand it, then make sure you understand _Sin's. Then see if you can spot the (obviously deliberate ) errors of coding style in both - there are things in _Sin's that I would reject at code review. There again there are things in mine that I would also question now that I re-read it. No-one's perfect!!

Yes, I put in a mostly trivial primality test with the intention of replacing it with something a bit faster after proving that the code worked, but as it generates all the perfect numbers <64bits long without any appreciable time delay, it seemed pointless to optimise further.

I think minor optimisations on the primality test wouldn't get very far, however. To test only primes there would need to either be a rather large table, or a recursive call to the prime test (which is significantly slower than brute force in this instance). I did originally generate the primes, but the memory requirements shoot up beyond (IIRC) the 5th perfect number and it started to take noticeable amounts of time to generate.

Considering that only a tiny handful of potential primes are ever even considered in the code, it seemed that a simple test would be a far better option than trying to generate/store primes. Unless I stored only the primes I know I'd need, but then I might as well just store the answer, and that seemed like cheating.

I had a simple implementation of miller-rabin, which is probabilistic (but known good over the range required here). However it seems unnecessary speed-wise, and would have complicated the code.

And no, I wouldn't want anyone taking that code as a good example of anything

[grumpydoc]

Good points.

It's worth remembering that in the real world "good enough" is often just that - "good enough". I think your observations about minimal gain are very valid. One shouldn't optimise unless the section of code in question has shown to be an important bottleneck - and one shouldn't optimise implementation before optimising the (choice of) algorithm.

Another important point that you touch upon is that it's sometimes necessary to trade memory use for speed, or vice versa depending on resources. This is especially true for embedded systems. Another thing is that sometimes an approach which should be faster in theory turns out not to be so in practice as you found with storing primes.

Finally remember that there is a sometimes a trade off between efficiency and maintainability - miller-rabin will be faster but if the next person to maintain the code hasn't a clue how it works it might not be such a good idea.

See - you can make any bit of programming interesting as long as you don't constrain it too much.

[DavidJRobertson]

My working but inefficient solution:

Code: [Select]

#include <stdio.h>

void main() {
  int i = 2;
  int numfound = 0;
  int factorsum;
  int j;
  int hold[1000000]; // Probably doesn't need to be this big but whatever...
  int cv;
 
  while (numfound < 6) {
    factorsum = 1;
    for (j = 2; j < i; j++){
      if (i % j == 0) {
        if (hold[j] == 0) {
          factorsum +=j;
          hold[j] = 1;
        }
        if (hold[i/j] == 0){
          factorsum += i/j;
          hold[i/j] = 1;
        }
      }
    }
   
    if (factorsum == i) {
      printf("%10d\n", i);
      numfound++;
    }
   
    for (cv = 0; cv < 100000; cv++) {
      hold[cv] = 0; 
    }
   
    i += 2; // Assuming all answers will be even
  }
}


[westfw]

find the best possible way of factorising large numbers

A "known to be hard" problem.  Though the 5th perfect number hardly qualifies as "large."
There are probably lots of published algorithms, although they tend to be aimed at finding "prime factors."  (A list of prime factors gives you all of the factors pretty easily, though.  I think.)

I think you should require that it actually run on an Arduino.  The relative lack of RAM might add an interesting component to the challenge...