Palindrone tester

Pages: 1234
Jul 13, 2012 at 7:41pm
I made that assumption my first time, and realized that's not correct. And ended up running through why on paper. It's obvious now, but I think my solution is pretty solid. Helios, do you have any suggestions on my solution?
Jul 13, 2012 at 8:00pm
Your (i + j) < (operand1 + operand2) check is incorrect. There are values of k such that {(x,y)|x*y>=k} contains elements not contained in {(x,y)|x+y>=k}.

EDIT: To clarify, the check would make sense if it was possible to assure this:
i * j < i + j < operand1 + operand2 < operand1 * operand2
for all values of i, j , operand1, and operand2.
Last edited on Jul 13, 2012 at 8:08pm
Jul 13, 2012 at 8:14pm
Hmm, I don't see it. I can't even think of an example where that check would be wrong. I just ran through a few sets of numbers on paper, and don't see how this doesn't work.
Jul 13, 2012 at 8:39pm
For example,
30*2 < 30+2 < 40+1 < 40*1
60 < 32 < 41 < 40
32 < 41, but !(60<40).
Jul 13, 2012 at 8:52pm
What if it was changed to:
if(i < operand1 && j < operand2)?

That way it ensures that both operands are smaller than the previous. I don't think it's possible to get a larger product from 2 smaller numbers.
Jul 13, 2012 at 9:03pm
It's correct, although far too inclusive.

What's the point of this, anyway? You're already checking product > answer before calling is_palindrome(). It doesn't make sense to add more code to avoid doing one integer multiplication and one integer comparison.
Last edited on Jul 13, 2012 at 9:06pm
Jul 13, 2012 at 9:13pm
Well the original check I put in there, that you've now debunked, cut down on run time significantly. Like somewhere around 500%. I'm trying to not lose that.

EDIT:
Looks like whatever I have done after that held up the slack. Removing that check entirely saw no loss of speed.

EDIT2:
Pretty sure it's because I have the product > answer check before the palindrome call now. I originally had it the other way around, and realized that was dumb and wasting a bunch of time.
Last edited on Jul 13, 2012 at 9:18pm
Jul 14, 2012 at 5:28am
@helios
I've been running through your code, and I've been spotting different things about it. I did have one thing I wanted to question though.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
result_t get(){
	bool found=0;
	result_t result;
	for (main_type x=N;x>0;x--){
		main_type end=99;
		if (found)
                        // Why is this here?
			end=result.candidate/x;
		for (main_type y=N;y>end;y--){
			evaluated++;
			if (found && x*y<=result.candidate)
				continue;
			if (!is_palindrome(x*y))
				continue;
			if (!found || x*y>result.candidate){
				result.candidate=x*y;
				result.x=x;
				result.y=y;
				found=1;
                                // And here?
                                // Also, is it not better to just set end to y here?
				end=result.candidate/x;
			}
		}
	}
	return result;
}


Maybe I don't understand all of it yet. And your code doesn't run 2 milliseconds, it runs in 2 seconds, well the first run anyways, this last run it lasted almost 5 seconds.
Last edited on Jul 14, 2012 at 5:29am
Jul 14, 2012 at 6:24am
// Why is this here?
end=result.candidate/x;
That's used to limit the search space to the absolute minimum.
It's based on the idea that the k isoline for f(x,y)=x*y (that is, {(x,y) | f(x,y)=k}) can be parametrized as y=k/x.

// And here?
// Also, is it not better to just set end to y here?
end=result.candidate/x;
Ah, I see what you mean. I didn't think about that. Yeah, same thing really. break would be even better. When I originally wrote that, the loop iterated upwards (and I was modifying start), so it wasn't safe to just break out of the loop.

And your code doesn't run 2 milliseconds, it runs in 2 seconds
Do note that the code as I posted it here calls get() a thousand times to accurately measure its run time.
Last edited on Jul 14, 2012 at 6:33am
Jul 14, 2012 at 6:40am
[quote]And your code doesn't run 2 milliseconds, it runs in 2 seconds

Do note that the code as I posted it here calls get() a thousand times to accurately measure its run time.[/quote]
I noticed that, but after you divide by 1000, it still displays the time in seconds. It took almost 5 seconds on my system, this time it took 4s:
http://prntscr.com/c2agx

That's used to limit the search space to the absolute minimum.
It's based on the idea that the k isoline for f(x,y)=x*y (that is, {(x,y) | f(x,y)=k}) can be parametrized as y=k/x.

What is your profession? You talk a lot like a friend who is an electrical engineer. Possibly a mathematician?

And I was just stating that I think end should just equal result.y since that's all you're doing, correct? I still need to break the code apart step by step, comment out some things so I can understand it better though. But I see that essentially your end variable just shortens up your inner for loop, like you said, to limit the calls to is_palindrome()
Jul 14, 2012 at 7:15am
I noticed that, but after you divide by 1000, it still displays the time in seconds. It took almost 5 seconds on my system, this time it took 4s
Code::Blocks can only measure the time the entire program takes. It's considering the one thousand runs of get() as a single unit.
See that my program prints four numbers? The last number is the average time taken by get() in milliseconds (only on Windows).
If get() took 5 seconds you should have waited an hour and 23 minutes.

And I was just stating that I think end should just equal result.y since that's all you're doing, correct?
Sorry, that doesn't make sense.
This is what I'm doing:
http://i45.tinypic.com/2uhn8qq.png
When you find a candidate solution, what you do is construct the boundary you see above, generated by the function f(x)=k/x, such that the candidate lies directly on the boundary. Once you have that, you can be sure that the product of any vector in the white region is strictly smaller than your candidate ({(x,y) | y<f(x)}={(x,y) | x*y<candidate}), so you can avoid even considering those possibilities.
There are other curves that also work, but this one is simply the best one.

What is your profession? You talk a lot like a friend who is an electrical engineer. Possibly a mathematician?
I'm a computer science student, but the first quadmester of the program at my university consists of just Algebra (a bit of discrete mathematics, a bit of number theory, a bit of abstract algebra) and Calculus II (multivariate calculus and some topology), and both subjects are shared with the mathematics people. That's 16 hours a week (not counting the time I spend studying by myself) of nothing but math for four months.
You'll have to excuse me if I'm speaking too much mathematese.
Last edited on Jul 14, 2012 at 7:32am
Jul 14, 2012 at 7:29am
Sorry, that doesn't make sense.
This is what I'm doing:
http://i45.tinypic.com/2uhn8qq.png
When you find a candidate solution, what you do is construct the boundary you see above, generated by the function f(x)=k/x, such that the candidate lies directly on the boundary. Once you have that, you can be sure that the product of any vector in the white region is strictly smaller than your candidate ({(x,y) | y<f(x)}={(x,y) | x*y<candidate}), so you can avoid even considering those possibilities.
There are other curves that also work, but this one is simply the best one.

Sorry, I'm quite tired. But what I meant was that this line:
end=result.candidate/x;
Is the same as writing:
end=result.x*result*y/x
It just hit me that the x is a different value each time -.- Sorry about the confusion on that one. Great logic.

I'm a computer science student, but the first quadmester of the program at my university consists of just Algebra (a bit of discrete mathematics, a bit of number theory, a bit of abstract algebra) and Calculus II (multivariate calculus and some topology), and both subjects are shared with the mathematics people. That's 16 hours a week (not counting the time I spend studying by myself) of nothing but math for four months.
You'll have to excuse me if I'm speaking too much mathematese.

I completely understand. I love math, but even I get tired of hearing about it sometimes. Tonight my friend was trying to hit on a girl and was using mathematical terms, and needless to say, she wasn't into math so he didn't get far. I wish I had taken more math since I'm limited to derivatives and minimal Calculus. I love learning theory, but I find that a lot of theory is written in cryptic code and takes a long time to understand the formulas. I'm learning, slowly, but surely.

I'll walk you through step by step about how I understand your timer.
std::cout <<double(t1-t0)/repeats<<std::endl;
Evaluates t1 - t0 as a double, divides by 1000
clock_t t0=clock();
t0 is set to the start time of the code in ms
clock_t t1=clock();
t1 is set to the end time of the code in ms

Going back to the first line, the difference of the start and end times will be in milliseconds. Once converted to a double and divided by 1000, you get a time of seconds for the entire program. This is then displayed to the screen.

Granted you might call the function 1000 times, but...now I understand everything...I hang my head in shame v.v
Jul 14, 2012 at 7:43am
Final optimization:

Change outer for loop to
for (main_type x=N;x>99;x--){

Not really an optimization, just a minor correction. By the time x reaches 100, the inner loop does nothing, anyway.

Change inner for loop to
for (main_type y=N;y>end && y>=x;y--){

x*y=y*x

With that last change, my get() finishes in about 1 ms., depending on compiler options.
Last edited on Jul 14, 2012 at 7:48am
Jul 14, 2012 at 7:46am
You're a smart man, or woman, helios. And I checked out your profile, you're only 3 months older than I am. I would love to have half of your knowledge on programming, math, and logic.
Jul 14, 2012 at 7:50am
It's all just practice, my friend. Just practice.

By the way, I edited one of my previous posts, maybe you missed it:
// And here?
// Also, is it not better to just set end to y here?
end=result.candidate/x;
Ah, I see what you mean. I didn't think about that. Yeah, same thing really. break would be even better. When I originally wrote that, the loop iterated upwards (and I was modifying start), so it wasn't safe to just break out of the loop.

You were right (possibly. Depends on what exactly you were saying). I was just having trouble understanding what you meant.
Last edited on Jul 14, 2012 at 7:51am
Jul 14, 2012 at 8:05am
Yes, I did catch that. And I've been talking to a friend who is a programmer for C# .NET applications. He is very knowledgeable and I saw him tonight at work and explained out conversation to him. He actually wants to read your code to see how you went about to find your answer. He's also very interested in the project euler problems so I'm passing him the link for that and your code compared to mine.

I'm also passing him some recursion I helped someone with as well.

I had simply asked why you had two calls of the same thing, but then I began to understand more and more as I read your code more. I am interested in seeing your final code now that it's only about 1ms.
Last edited on Jul 14, 2012 at 8:06am
Jul 14, 2012 at 8:17am
Rather than posting basically the same thing twice, I'll just put it on pastebin:
http://pastebin.com/W7gu3mmD
I made one last addition just before the inner loop that changes practically nothing, but fixes something that was bothering me. Like when you see a crooked picture on the wall and you just have to straighten it.
Jul 14, 2012 at 8:47am
I'll just leave this here, although it's not the full solution...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import std.conv;
import std.stdio;

bool isPalindrome(ulong n)
{
	if (to!string(n) == to!string(n).dup.reverse)
		return true;

	return false;
}

void main()
{
	ulong[] numbers = [1661, 32, 9822, 111, 831, 10001];

	foreach (n; numbers)
		if (isPalindrome(n))
			writeln(n, " is a palindrome.");
		else
			writeln(n, " is NOT a palindrome.");
}
1661 is a palindrome.
32 is NOT a palindrome.
9822 is NOT a palindrome.
111 is a palindrome.
831 is NOT a palindrome.
10001 is a palindrome.
Jul 14, 2012 at 5:36pm
@Catfish,

What is that? :O
Jul 14, 2012 at 5:53pm
It's Digital Mars D2, aka D.

Now I don't have my Euler #4 solution at hand, but knowing myself I must've brute forced it, so nothing truly interesting to see. Apart from maybe, the code being a bit simpler.
Pages: 1234