Skip to main content
Share Your Experience: Take the 2024 Developer Survey
151 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 ...
Zeta's user avatar
  • 19.3k
79 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 ...
Eric Lippert's user avatar
  • 14.9k
33 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,...
whydoubt's user avatar
  • 461
32 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 ...
mascoj's user avatar
  • 421
32 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 ...
Alex Selby's user avatar
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: ...
Billal Begueradj's user avatar
27 votes
Accepted

Arcsine function for a real-time control program

Use a namespace instead of a class There is no reason to use a class if you only have static ...
G. Sliepen's user avatar
  • 57.6k
26 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 ...
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 ...
Zeta's user avatar
  • 19.3k
24 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 ...
Krupip's user avatar
  • 641
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 ...
Graipher's user avatar
  • 41k
21 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 ...
vnp's user avatar
  • 56.5k
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 ...
Peilonrayz's user avatar
  • 43.4k
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: ...
Marc's user avatar
  • 5,604
20 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\$. ...
G. Sliepen's user avatar
  • 57.6k
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 ...
Graipher's user avatar
  • 41k
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 ...
Ludisposed's user avatar
  • 11.6k
17 votes

Newton Fractal writen in C

Use complex numbers Since C99, C supports complex numbers, and has many mathematical functions that work on complex numbers. I would rewrite all your code to use ...
G. Sliepen's user avatar
  • 57.6k
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 ...
jschnei's user avatar
  • 736
15 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 ...
Stefan Pochmann's user avatar
14 votes

Disproving Euler proposition by brute force in C

This is a different method from the other (priority queue) answer I submitted earlier. It is simpler and achieves \$O(n^2\log(n))\$ time and \$O(n)\$ memory with a better constant factor. You choose ...
Alex Selby's user avatar
14 votes

C++ determinant calculator - follow-up

if(dimension == 0) { return 0; } Mathematically, that is not correct. The determinant of an empty (i.e. zero-dimensional) matrix is one, see for example What ...
Martin R's user avatar
  • 23.3k
13 votes
Accepted

RSA algorithm implementation in Python 3

I think your Modular Inverse implementation is slow. We can apply this Extended GCD algorithm recursive implementation which shows quite a dramatic speed improvement (at least on my machine): ...
alecxe's user avatar
  • 17.3k
13 votes

Python program to calculate GCD

If you want to know whether there are more efficient algorithms than Euclid's, this is probably the wrong place to ask. Even Wikipedia would be a better starting point. The answer is yes but they are ...
Josiah's user avatar
  • 5,996
13 votes

Plotting the Mandelbrot set efficiently

Unnecessary use of OpenGL Using OpenGL to draw individual pixels is the completely wrong thing to do. Apart from requiring OpenGL support which might not be present on all systems, this has a huge ...
G. Sliepen's user avatar
  • 57.6k
12 votes

Generalized Project Euler 1: A sledgehammer to crack a nut

Your maths is much better than mine, and so I can't comment on it. However your function remove_multiples can be simplified if you come at the problem in a ...
Peilonrayz's user avatar
  • 43.4k
12 votes
Accepted

Calculator in C++

I have some suggestions here: Using switch/case instead of if/else looks a little better and slightly faster as also mentioned in the comments. You could definitely work on formatting your code it ...
Syed M. Sannan's user avatar
12 votes
Accepted

Count numbers that are the sum of three perfect cubes

Optimization: Code movement You are repeatedly doing the same computations over and over. How many times is \$i^3\$ computed? ...
AJNeufeld's user avatar
  • 33.7k
12 votes

Dividing two numbers then handle the divide by zero exception with try/catch

If you know that you want to divide two numbers then IMHO it would make more sense to perform a pre-liminary check. In other words, rather than executing the operation "blindly" by trusting ...
Peter Csala's user avatar
  • 9,159
11 votes
Accepted

Generalized Project Euler 1: A sledgehammer to crack a nut

Background Let \$N\$ be the size of the range [start, stop). \$N = \textrm{stop} - \textrm{start}\$. Let \$M\$ be the size of the divisor list. \$M\$ = \$\lvert \textrm{divisors} \rvert\$ The ...
twohundredping's user avatar

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