Palindrone tester

Pages: 1 234

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?

helios (17574)

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

ResidentBiscuit (4459)

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.

helios (17574)

For example,
30*2 < 30+2 < 40+1 < 40*1
60 < 32 < 41 < 40
32 < 41, but !(60<40).

ResidentBiscuit (4459)

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.

helios (17574)

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

ResidentBiscuit (4459)

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

Volatile Pulse (1543)

@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.

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

helios (17574)

// 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

Volatile Pulse (1543)

[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()

helios (17574)

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

Volatile Pulse (1543)

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 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

helios (17574)

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

Volatile Pulse (1543)

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.

helios (17574)

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

Volatile Pulse (1543)

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

helios (17574)

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.

Catfish2 (666)

I'll just leave this here, although it's not the full solution...

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.

ResidentBiscuit (4459)

@Catfish,

What is that? :O

Catfish2 (666)

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: 1 234