144 votes
Accepted

Disproving Euler proposition by brute force in C

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 ...
user avatar
  • 18.8k
76 votes

Disproving Euler proposition by brute force in C

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 ...
user avatar
  • 14.6k
44 votes
Accepted

Checking if a number is divisible by 9

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 <...
user avatar
  • 64.1k
41 votes
Accepted

Solving the Lazy Hobo Riddle

Notice how the square of a number 15 or greater exceeds 200? What you can do, is set the interval from 1 to ...
user avatar
  • 2,599
40 votes

Solving the Lazy Hobo Riddle

One thing you should note is that the fourth iteration is useless. Once you fixed the first 3 variables, you need to find the value for the fourth one that equals to 200 minus the sum of squares of ...
user avatar
  • 667
32 votes

Beehive numbers - using goto in C++

Your use of goto is wholly unjustified, not just because goto is taboo, but because your code has flow-of-control that is hard ...
user avatar
31 votes

Disproving Euler proposition by brute force in C

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,...
user avatar
  • 441
31 votes

Python program to calculate GCD

Bug: When I input -6 and -3 I expect the result to be 3 but I get a RecursionError exception instead: ...
user avatar
30 votes

Disproving Euler proposition by brute force in C

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 ...
user avatar
  • 401
30 votes

Disproving Euler proposition by brute force in C

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 ...
user avatar
26 votes

Implementation of the trigonometric functions for real time application

Your implementation is going to be slow, and the excuse "I need it to take a fixed amount of time" does not justify this. Using plain tables smells like cargo culting as well. So I'm not ...
user avatar
  • 621
26 votes
Accepted

A math engine with support for complex numbers, calculus, and fractions

using namespace std Given that you're using template and declare your class, you're working ...
user avatar
  • 18.8k
24 votes
Accepted

Greatest common divisor

A more elegant implementation of the gcd function: int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } To ensure ...
user avatar
  • 107k
23 votes
Accepted

Large Number Limit Extravaganza

Your method of generating primes is horribly slow. Running your code takes on the order of 5 minutes on my machine. Consider as an alternative a prime sieve, even a simple one like the Sieve of ...
user avatar
  • 40.5k
22 votes

Disproving Euler proposition by brute force in C

Read the source Since you've already identified the author, why not read the original paper? Some misconceptions In fact, the numbers found by Elkies were not the ones cited in the question. They ...
21 votes

Checking if a number is divisible by 9

After reading gnasher729 and Simon's answers, I was inspired to find the fastest possible way to do this. Analysis of original function The main problem with the original function is that it only ...
user avatar
  • 28.4k
21 votes

Check if a given number N is a power of k

I'd follow Ludisposed's answer. Except, there's a simple way to do this. Use logarithms. Since the equation is \$N = k^a\$ you can change it to \$a = \log_k N\$. And so if \$a\$ is an integer, then ...
user avatar
  • 41.6k
21 votes

Sine function calculated via look-up table and linear interpolation

You only need to store values for \$\left[0, \frac{1}{2}\pi\right)\$ You can exploit the structure of the sine function, and only store values in the table for inputs between 0 and \$\frac{1}{2}\pi\$. ...
user avatar
  • 32.4k
20 votes
Accepted

Finding divisors of a number

This code could do with some editing... First of all is the spacing. It is absolutely horrible (we will fix that after the edits). Also, the naming is horrible. ...
user avatar
  • 9,414
20 votes
Accepted

Calculate square of a number without multiplication

A more efficient way to do this is to keep doubling the product while you can.... So, for example, \$5^2\$ is: $$\begin{eqnarray*} 5 +& 5 &\longrightarrow 10 \\ 10 +& 10 &\...
user avatar
  • 96.7k
20 votes
Accepted

Efficiently find all the Pythagorean triplets where all numbers less than 1000

Some optimizations and style suggestions: After finding a solution you can break: ...
user avatar
  • 5,487
19 votes

Python program to calculate GCD

Python has an official style-guide, PEP8. It recommends (among other things) the following: Use whitespace around operators (so a = input(...)). Don't use ...
user avatar
  • 40.5k
18 votes

Disproving Euler proposition by brute force in C

I recommend to rewrite a problem as finding \$a,b,c,d\$ such that \$a^4 + b^4 = d^4 - c^4\$. Now you may only operate in pairs of powers. Building a table of sums takes \$O(n^2)\$. Building the table ...
user avatar
  • 53k
17 votes
Accepted

Wow that's a big integer! What's its largest prime factor?

What a fascinating solution! It seems that for every smart decision you made, you also threw in a poor decision or two. Smart decision: In PrimeFactors(), you ...
user avatar
17 votes

Solving the Lazy Hobo Riddle

Some minor things, but may still be worth mentioning: Whenever std::endl is used, the buffer gets flushed, which can add to performance a bit, especially if it's ...
user avatar
  • 34.7k
17 votes

Checking if a number is divisible by 9

I did not check if your code works, I assume it does since you say so. Your code lacks consistency if(divby8 == (orgx - (olddivby8 << 3))) { //... } ...
user avatar
17 votes
Accepted

Check if a given number N is a power of k

Major print " True " Don't print but return variables from functions, that makes them usable later on ...
user avatar
  • 11.4k
16 votes
Accepted

Searching for three positive integers as a solution to an equation

Here are some simple optimizations you can make that can push your limit a bit higher: Don't use floating point arithmetic. Floating point arithmetic is slow compared to integer arithmetic (this is ...
user avatar
  • 736
16 votes

Efficiently find all the Pythagorean triplets where all numbers less than 1000

My "review" will have to be "If you really want it fast, you need a completely different approach". The following ~ O(N log N) approach is about ...
user avatar
14 votes

Solving the Lazy Hobo Riddle

As well as the excellent information from @EngieOP, you could also think about taking some repeated calculations out of the inner loop at the cost of an extra int per 'for' loop. These might be ...
user avatar
  • 241

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