Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

138

Note: At some point, this review drifted into the realm of assembler and GMP. An actual review is at the end of this post, whereas the first section discusses the runtime-problems concerning pow, wrong data types and arbitrary large integers. No life time for run time Would there be any way (on my current machine) to get this to run in my lifetime? ...

88

The biggest problem with using a for-loop to do this is that you are wasting CPU power. When using sleep, the CPU can, in a sense, take a break (hence the name "sleep") from executing your program. This means that the CPU will be able to run other programs that have meaningful work to do while your program waits. But in the for-loop the CPU continuously ...

77

That's not a bad program, despite the number of suggestions I'm about to make. I do recognize you're a learner, and a young learner at that. There are several levels at which we can analyze this program. One is checking the current implementation. Another is considering whether it is portable. We can question whether the interface is good — should ...

75

Well let's start with this: for (a = 1; a < 100000; a++) { for (b = 1; b < 300000; b++) { for (c = 1; c < 500000; c++) { let's ignore d for now. What do you do here? You check 1, 1, 1, then 1, 1, 2, then 1, 1, 3, ... up to 1, 1, 499999. Then you start over at 1, 2, 1. But you already checked 1, 1, 2, so why are you checking 1, 2, 1? ...

64

The code leaves a bad first impression because of how it is formatted. In particular, the extra whitespace between the return type and the function name, and that between the variable's type and its name, looks odd. Unless you are writing code that needs to be compatible with pre-C99 compilers, you should break the habit of declaring variables at the top of ...

46

If you're to implement something like this, you should first learn about how these things are done. I hope this doesn't sound too harsh. To explain it better, here is my variant of your code, with comparison to what C computes as e using expl(1): #include <stdio.h> #include <math.h> int main () { long double n = 0, f = 1; int i; for ...

43

Implementation: As of now, the code is not practical, because the limit is 500 chars including zero termination. It does unnecessary copying. You need to determine the actual length of the string by relying on the fact that C strings are null terminated. size_t length = 0; while (*(str + length) != 0) { ++length; } Notice that I'm using size_t, ...

41

I see some things that you might want to use to improve your code. Use an early bailout If the passed number x is less than 9, the routine can immediately return 0. Eliminate multiples of 2 Since 9 and 2 have no common factors, you can speed up the operation (on average) by shifting the incoming x to the right until the least significant bit is non-zero. ...

40

It's not possible to avoid undefined behaviour by testing for it after the fact! If the addition overflows then there is already undefined behaviour here: sum = a + b; so attempting to test afterwards is too late. You have to test for possible overflow before you do a signed addition. (If you're puzzled by this, read Dietz et al. (2012), "Understanding ...

35

Back in the day, home computers used to have a “turbo” button, which (when activated), made the processor slower. The problem was that games were coded around an input loop that was expected to take a specific number of milliseconds. If the loop was executed faster, the whole game would speed up, becoming unplayable. Today, computers have vastly different ...

32

printf("|---------- PROGRAM FOR AMICABLE NUMBERS.----------|"); This kind of banner message makes it harder to use the output of your program in a pipeline. I'd suggest removing it (the user has chosen to run it; trust them to know what they're doing!). int num1,num2,sum=0; What's sum for? It doesn't seem to be used. for(num1=1; num1<=10000; ...

31

Too frenetic I ran your program but it was very frenetic. It was constantly clearing the "Loading" prompt and reprinting it which resulted in a flickering effect. In addition, the cursor also moved around in a flickery manner (similar to the green box in the animated image). To improve this, I would do two things: Don't constantly draw when nothing has ...

31

All of the answers given (when this 'answer' was first written) ignore an important constraint: native types. In C, a long int is a 32-bit (or greater) signed type, meaning the largest positive value that can be (counted upon to be) represented is $2^{31}-1$. The largest possible input to a function which calculates a fourth-power and [[can be counted on ...

31

Since you already have a std::vector<std::string>, it's much simpler to let that own the memory, and build a parallel std::vector<char*> which just keeps pointers into the original strings. The only difficulty is ensuring this isn't used after the owning vector goes out of scope. The simplest implementation is something like: std::vector<...

30

You could move the duplicated lines into a function, something like this should work: #include <stdio.h> float get_input(void) { float input; printf("Enter a distance in inches (0 to quit): "); scanf("%f", &input); return input; } int main() { float inches, floatFeet, input; int feet; while (input = get_input()) ...

30

Roughly 50% of all programming is about dealing with errors. You say your code works, but it doesn't handle errors and therefore doesn't work. Example 1: How many feet of steel was received today: four Program doesn't say "Error, try again". Instead it displays all prompts without waiting for any user input and exits. Example 2: How many feet of steel ...

30

Buffer overflow char array[MAX]; scanf("%s", array); This can overflow the buffer in array if the user input exceeds MAX-1 characters. There are multiple ways around this: Ask scanf to allocate an appropriately sized buffer (if you have a moderately recent glibc): char *array = NULL; scanf("%ms", &array); You need to release the allocated buffer ...

30

Some interesting things no one have mentioned about this, but it is an improvement when looking for the smallest solution: If the $\gcd(a,b,c) \neq 1$ then $a^4$,$b^4$,$c^4$ and $d^4$ are all divisible by that gcd to the 4th power, giving a smaller solution. Therefore, at least one of $a$,$b$, and $c$ must be odd, since if they are all even ...

30

I'm not able to comment on vnp's solution, but vnp was right the first time: you can brute force it in $O(n^2\log(n))$ time and $O(n)$ space. You don't need $O(n^2)$ space because you don't have to store the whole list of $a^4+b^4$ or $d^4-c^4$ upfront. Instead you only need to be able to list the values of $a^4+b^4$ and $d^4-c^4$ in ascending ...

29

Indeed you must have been working on this project for a while, since I answered a question on SO related to one of your old versions a while back. At least some of the feedback I had is still pertinent even now. Code and style comments #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <time.h&...

29

Your find_second() function is rather weird. It never finds the second-largest number if it is a. It sometimes finds the second-largest number if it is b or c. I don't know if your program works or not — your main() tries to make up for the deficiencies in find_second() by calling it three times — but the function name is a big fat lie. Special numbers ...

29

Bug Winning a 6/49 game is, of course, unlikely. The probability of any single ticket having all six numbers correct is $$\dfrac{1}{\binom{49}{6}} = \dfrac{6!\,(49-6)!}{49!} = \dfrac{1}{13983816}$$ But your code required 1.5×109 draws to produce a win, which is 100 times more than the expected 1.4×107 draws. Why? Because your comparison loop… // ...

28

You are doing brute-force trial division, and not particularly smartly. For example, you only need to test odd candidate factors up to sqrt(number). When you want to find many prime numbers, a much better algorithm to use is the sieve-of-eratosthenes. It involves just addition, no division, and skips processing of numbers that are already known to be ...

27

The fastest way to do this would be to align your data on 16-byte boundaries, then the entire copy just becomes 5 copies through XMM registers. This is over twice as fast as your version on my machine. Store your data like this: #include <xmmintrin.h> struct Data { union { int i[20]; __m128 v[5]; }; }; Then the copy ...

27

Yes, there is a better way: int CountOnesFromInteger(unsigned int value) { int count; for (count = 0; value != 0; count++, value &= value-1); return count; } The code relies on the fact that the expression x &= x-1; removes the rightmost bit from x that is set. We keep doing so until no more 1's are removed. This technique is described ...

27

This is called 'busywaiting' or 'spinning', and will work but has the following disadvantages: It will perform 'work' on your program instead of yielding control to OS and other programs - so it doesn't "play nice" with others; on a common computer there are many programs running at the same time that could also like to use that CPU instead. Busywaiting ...

27

Over all, this is good, but there's unfortunately some very major performance problems, and I have a few minor design suggestions. A string can be reversed quite trivially in linear time. Your algorithm is quadratic. You can just do a single backwards loop over the input string instead of this convoluted nested loop. Since mon_string_rev doesn't alter ...

27

So my first hunch when I read your question is: Okay this guy is making a complicated solution to a simple problem based on a hunch that the trivial solution is "grossly inefficient" without any measurements to back up said claim. I suspect OPs solution is slower than the trivial solution. So I set out test this, I pit your fancy implementation against ...

27

Assuming int is 32 bit long on your system, an integer overflow occurs on c with upper = 1000000. The multiplication in c = 3 * c + 1 can cause c to grow quite large, eventually exceeding the $2^{31}-1$ upper limit of a 32-bit signed integer, and thus rolling over into negative values. Obviously, the algorithm does not work correctly for negative values of ...

Only top voted, non community-wiki answers of a minimum length are eligible