#Using Euler Project 145 to Teach Myself C

15 messages · Page 1 of 1 (latest)

shut marsh
#

Background: I am a first-year graduate researcher in CFD algorithms, and while I am quite familiar with Python and decent with MATLAB, I have next to no familiarity with C.

Using the same strategy I used to learn the other two languages, I found a random Euler Project problem, and started at it.

nimble crystalBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

shut marsh
#

This is Euler Project 145:

image.png
#

My code is as follows:```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int reverse_n(int n) {
int digit_count = (int) ceil(log10(n));
if (n == 0 || n == 1) {
digit_count = 1;
}

char n_str[digit_count + 1];
char m_str[digit_count + 1];

sprintf(n_str, "%d", n);

int j = digit_count - 1;
for (int i = 0; i < digit_count; i++) {
    m_str[j] = n_str[i];
    j--;
}
m_str[digit_count + 1] = '\0';

int m = atoi(m_str);

return m;

}

int test_n(int n) {
int sum = n + reverse_n(n);
int digit_count = (int) ceil(log10(sum));

for (int i = 0; i < digit_count; i++) {
    if (sum % 2 == 0) {
        return 0;
    }
    sum /= 10;
}

return 1;

}

int main() {

int count = 0;

for (int i = 1; i < 1000; i++) {
    count += test_n(i);
    printf("n: %3i, reversed: %3i, sum: %4i, test: %i, total: %i\n", i, reverse_n(i), i + reverse_n(i), test_n(i), count);
}

printf("%i\n", count);

}

#

Now, one of the pieces of information that the Euler Project provides is that there are 120 reversible numbers for n < 1000. When I run this code, the answer I come up with is 125. This is confusing to me because that means there is some special case that I am not accounting for.

stray bluff
#

i've yet to read throught all of your code - but m_str[digit_count + 1] = '\0'; is UB (undefied behavior and thus isn't allowed). a kind reminder array indices starts at 0

stray bluff
#

as for the problem - since you're counting numbers being added to themselves (e.g. 11 + 11) it might mess with your results thats incorrect

#

after fixing the above mentioned problem (and cleaning up a bit) - the algo seems to be correct. unless there're not restrictions not listed in the pic you posted - 125 seems to be correct

uncut breach
#

If you eliminate numbers that end in 0 because once reversed, it would be a leading zero, you get 120.

stray bluff
#

ah. they should have communicated it a bt more clearly

uncut breach
#

Agreed. Eliminating string stuff and optimizing code a bit, the brute force calculation for 1 billion:

$ time ./a.out
Final count: 608720

real    0m46.736s
user    0m46.698s
sys    0m0.001s

Optimizing some more by using OpenMp:

#include <omp.h>  // Required for OpenMP

#pragma omp parallel for reduction(+:count)
for (int i = 0; i < 1000000000; i++) {
    count += test_n(i);
}

$ gcc -O3 -fopenmp testReversibleOpt.c
$ time ./a.out
Final count: 608720

real    0m5.865s
user    0m22.949s
sys    0m0.007s
ember nova
#

Is it cause it's counting userspace time from all cores individually?

uncut breach
#

Correct. split the processing across all cores.

ember nova
#

Probably also some SIMD, my beloved :D, parts