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?
...
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? ...
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 ...
41
Notice how the square of a number 15 or greater exceeds 200? What you can do, is set the interval from 1 to 14.
There is no advantage in evaluating the same combination over and over again. Realize that the most efficient way is to structure your for loops such that
$$ a \leq b \leq c \leq d $$
In your attempt, you are iterating 38,416 times!
By ...
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
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 the first 3. You don't have to go through all the possible numbers to check if one of them squared is equal to N, you can simply take the square root of N and ...
36
(long) 0 scructures should be written as 0L.
Access modifiers of numList and result should be private:
private ArrayList<Long> numList = new ArrayList<Long>(5000001);
// status of whether a number is power number
private boolean[] result = new boolean[5000001];
ArrayList<...> reference types should be simply List<...>. See: ...
32
Your use of goto is wholly unjustified, not just because goto is taboo, but because your code has flow-of-control that is hard to follow. Furthermore, the use of goto is not even an effective way to achieve your goal of compactness.
Before addressing the core concern about goto, I'd like to point out that there is a lot of junk in your code:
Your compiler ...
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
Bug:
When I input -6 and -3 I expect the result to be 3 but I get a RecursionError exception instead:
RecursionError: maximum recursion depth exceeded in comparison
For the sake of UX:
Leave some space between the text you display and the data to input:
Enter a number6
Enter a number5
This would be the minimum better:
Enter a number: 6
Enter a ...
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 ...
23
A more elegant implementation of the gcd function:
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
To ensure that the arguments are positive, it's easiest to use the abs(...) function.
Please also indent your code nicely to make it more readable.
And put spaces around operators. For example, instead of this:
for(int i=1;i<=...
answered Oct 15 '14 at 9:27
Stop ongoing harm to Monica
104k13 gold badges137 silver badges360 bronze badges
21
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 were found by Roger Frye using a computer. How did he do that back in 1988? It's mentioned in the paper:
Postscript.
While our first counterexample
...
21
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 you know that \$N\$ is a power of \$k\$.
import math
def check_power(N, k):
return math.log(N, k).is_integer()
Since the above can error, and if there's ...
20
Firstly, your implementation is (arguably) not quite correct:
else if((m < 0) || (n < 0))
return -1;
The GCD of two negative numbers is perfectly well defined. However, if you really don't want the user to pass in negative numbers, make it explicit in the function signature:
unsigned greatestCommonDivisor(unsigned m, unsigned n)
Euclid's ...
19
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. Scanner x could be scanner and y could be num. As for z, it is completely unnecessary:
for (i = 2; i < y; i++) {
long z = y % i;
if (z != 0)
continue;
System.out.print(i + " ...
19
Some brief comments:
Your variable names are quite short (often one letter), which makes the code harder to follow. Longer and more descriptive variable names would make it easier to read and debug (e.g., trg to triangle, r1 to row1).
The input to the function printTrg is rows, but we also have variables like r, r1 and r2 which look like rows. Perhaps this ...
19
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 &\longrightarrow 20
\end{eqnarray*} $$
then add the last 5 to get 25.
This can be done efficiently by using bit shifting:
public static int sqr (int val)
{
int ...
19
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 uses the divide by 8 trick once. After that, it falls into this loop:
while(divby8 >= 9)
{
divby8 = divby8 - 9;
}
Given a large number, ...
19
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 Eratosthenes will do (you don't need to go full Atkinson on it):
def prime_sieve(limit):
a = [True] * limit
a[0] = a[1] = False
for i, isprime in ...
19
Python has an official style-guide, PEP8. It recommends (among other things) the following:
Use whitespace around operators (so a = input(...)).
Don't use unnecessary parenthesis (if, for, while, etc don't need any)
In addition to this, you should make your function return the result rather than printing. Otherwise you cannot use it in further calculations:...
18
Your code is quite nice, and can't really be improved. However, let's put the “generator” back into the code.
Go has channels which can be used to write elegant generators/iterators. We spawn of a goroutine that fills the channel with the fibonacci sequence. The main thread then takes as many fibonacci numbers as it needs.
So let's write a function ...
18
There are three reasonable responses here:
yes, your recursion code can be improved for performance.
yes, part of that improvement can come from sorting the data.
yes, there's a way to refactor the code to not use recursion, and it may even be faster.
Bearing that in mind, this answer becomes 'complicated'.
Basic performance improvements for current code:
...
18
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 of differences also takes \$O(n^2)\$. Sorting them takes \$O(n^2\log{n})\$. Matching sorted tables takes \$O(n^2)\$ in a linear merge-like scan.
Overall ...
17
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 start testing divisors from small to large, rather than large to small.
Poor decision: You used if (IsFactor(number,divisor) … rather than while (IsFactor(number,divisor)). Using if instead of ...
17
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 done multiple times.
In order to get a newline without this added flush, use "\n" within an output statement:
std::cout << "\n";
Also, consider adding a bit more whitespace within the ...
17
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)))
{
//...
}
vs
else{
//...
}
and
if(x>=9) vs while(divby8 >= 9)
I suggest using an automated formatting tool.
Avoid nesting
You can avoid nesting by inverting the outer if statement and ...
17
Major
print " True "
Don't print but return variables from functions, that makes them usable later on
print "not a valid input"
You should raise an Exception with invalid input instead of printing it
for i in range (1,20):
This line will limit the input range from the function
if N <= 0 or k <=0:
Your guard clause does not cover all edge cases
...
16
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 not always true with the advent of things like FPUs, but it is a good rule of thumb). Even worse, floating point arithmetic is prone to things like rounding ...
Only top voted, non community-wiki answers of a minimum length are eligible
