Optimize mathematical operations in c

Question

I am registered in a web programming c where several algorithmic exercises. I made a very simple problem is as follows: I receive 4 numbers that determine coordinates of 2 corner of a rectangle and have to calculate the area. There is a set of tests and when the second corner is below or to the left of the first (x1> x2 || y1> y2) the program exits. enter image description here

Exemple:

Input:

1 1 4 3
0 0 1 1
9 7 3 6 //Exit

Output:

6
1

This is my code.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    while(1) {
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);//x1 y1 == A, x2 y2 == B
        if(x1 > x2 || y1 > y2)
            return 0;
        printf("%d\n", (x2 - x1) * (y2 - y1));
    }
}

My question is simply a curiosity. I solved the problem with a time of "0052", and there are 3 people in front of me that have managed to solve in "0048" and "0024"!. What optimicazion methods can I use to get lower time? Probably pointers?

`scanf` and `printf` (with a flush each time) are going to be much (*much*) slower than anything else. — Ed S., Dec 06 '14 at 22:58
Timing a function that waits for keyboard input is a nonsense. You are timing the typist. — , Dec 07 '14 at 09:08

score 2 · Accepted Answer · answered Dec 06 '14 at 22:41

2

Some thoughts:

You could use gcc's __builtin_expect() functions to make sure that the conditional is assumed to be false.
It's very unlikely that pointers would help you improve your solution.
scanf() is probably the really slow part. Rewriting this with a parser that only expected decimal integers would probably be much faster. Currently, scanf() needs to parse the format string, and the input number could be octal, hexadecimal, or decimal. Or could be invalid input. etc.

answered Dec 06 '14 at 22:41

Bill Lynch

80,138
16
128
173

How should i use __builtin_expect() in my program? I never used it and i dont know how apply it. – Raxkin Dec 06 '14 at 22:55
@Raxkin: I normally use them through the helper macros `likely(x)` and `unlikely(x)`: http://stackoverflow.com/questions/109710/likely-unlikely-macros-in-the-linux-kernel – Bill Lynch Dec 06 '14 at 23:47
This question is a whole nonsense. It's timing the standard I/O statements, on which the programmer has no control. (The time for the other statements - hem two elementary C expressions, nothing to optimize - is ridiculously small in comparison.) – Dec 07 '14 at 09:12

score 0 · Answer 2 · answered Dec 06 '14 at 22:45

0

Not much, but maybe try declaring int x1, x2, y1, y2; before entering the loop.

answered Dec 06 '14 at 22:45

Ranch

437
4
7

I try it, but when i do it, i get a time of 006 that is more than my best time – Raxkin Dec 06 '14 at 22:49
You might find that the machine code generated is identical. Having a look at the machine code (especially with the compiler trying to optimise) does no harm beyond that caused by worrying about four digit time numbers without unit. (Opinion: never bother with timings below five seconds, even in microbenchmarks. Do benchmarks with a limit on time rather than loop count.) – greybeard Dec 07 '14 at 10:23

score 0 · Answer 3 · edited Apr 07 '19 at 04:33

0

Here are my suggestions:

in the compile statement use:
```
gcc -O3
```

place all working variables in global space rather than stack space

int x1, x2, y1, y2;, area
char buffer[100];
int main()
{
    do 
    {
        fgets( buffer, sizeof(buffer), stdin );
        sprintf( buffer, "%d %d %d %d", &x1, &y1, &x2, &y2);
        x2-=x1;
        y2-=y1;
        area = y2*x2;
        printf("%d\n",area); // or perhaps puts( itoa(area) );
    } while(( 0 <= x2) && (0 <= y2)
    return(0);
}

edited Apr 07 '19 at 04:33

phuclv

37,963
15
156
475

answered Dec 07 '14 at 04:54

user3629249

16,402
1
16
17

This is an online contest, you don't compile your own code and submit the binary – smac89 Dec 07 '14 at 05:06
what is that supposed to me, I did not submit any binary – user3629249 Dec 07 '14 at 05:36
You are suggesting that OP uses compiler optimization flags. Which is why I said that you don't compile your code before submitting. The online judge does the compiling and testing, you just write the code – smac89 Dec 07 '14 at 05:38
There was nothing in the OPs question about any restriction on how the code is compiled – user3629249 Dec 07 '14 at 05:41

Optimize mathematical operations in c

3 Answers3