136 - Ugly Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Aug 17, 2003 2:04 pm

Why should I? I started this thread to show what can be easily achieved when you don't limit yourself to C or imperative languages in general. Writing took me 10 minutes. An attempt to make this solution work in C++ would need at least ten times more and probably end up as something much alike to yours.
Actually, the point of programming is not to make the code work as fast as possible. It's a good thing, but the priority should be to write in clear, readable and easy to debug way. The time of programmer is much more valuable than moderate improvement of speed. That's why it's sometimes better to use a language not as effective as C, but having some other advantages.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Mon Aug 18, 2003 9:37 am

Well, I still believe that speed is the most important in programming. If I have to choose between time and memory, I would rather choose time since you can increase your memory by buying a more powerful machine.
But time, you can't buy it! :wink: :wink:
Anyway when the first I tried submitting this prob with hardcoding, I got AC in 0.002 sec. Now without hardcode (the code I 've shown previously)
8 out of 11 is AC in 0.000 sec :D :D :D .
The rest 3 is AC in 0.002 sec. :-? :-?
Btw, I have two probs that really bugs me :evil: :evil: .
It's 10393 - The one-handed typist and 10197 - Learning Portuguese.
I already got AC for those two, but I'm still curious why the first codes got WA. Are you interested in finding the bug?? :o :o since this subject doen't seem to interset anyone in the board. I haven't got any replies until now!! :evil: :evil:

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Aug 18, 2003 12:39 pm

Yes, you can't buy the time. Your time. A millisecond improvement that required hours of coding is just a waste of it.

As for the problems you asked, I haven't solved them yet so I can't help you. Maby in future - I want to submit problems 100-199 and then I'm going to pass to volume C and next. However, it can take me a while since it's a week that I'm stuck on problem 149.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Mon Aug 18, 2003 3:31 pm

I achieved 0.8 milisec in friend's PC 1.7 GHz
I got interested in this stuff and I measured my program using processor ticks. Wish I could have a system without windows and it's processor load. Anyway, I got timings from 0.0005 seconds to 0.0020 seconds (ie 0.5 to 2.0 ms) on my 300MHz Pentium II.

I agree with Krzysztof that in real life for common programming optimization is in a way a waste of time. Anyway almost anything you achieve will be eaten up by user-interface. But, in case of some computational research work I believe it is worth to "waste" time to have a faster algorithm and thus finish research earlier. :)

But, optimizing programs is a fun and educational process. And the knowledge you gain will always come in handy as you will not want to write redundant code anymore.

Ivor
(last edited on 20. August 2003 -- fixed important typos)
Last edited by Ivor on Wed Aug 20, 2003 9:31 am, edited 1 time in total.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Mon Aug 18, 2003 7:04 pm

Did you use something like this to measure the clicks?

[cpp]unsigned long long
rdtsc (void)
{
unsigned long long c;
__asm__ __volatile__ ("rdtsc": "=q"(c));
return c;
}[/cpp]

And I said that speed improvement is a waste of time when it is small in comparison to the effort made.

You're right that having lower and lower times is fun. But you have to know when to stop and move to do something new :-)

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Mon Aug 18, 2003 7:44 pm

I am not very strong in asm but my code (actually I got it over a year ago from Ivan Golubev to measure precise time) includes this instruction. So I suppose it more or less correct.

Optimization is fun and it is challenging if you have someone to challenge you. Here at at this site I had a lot of fun and I did a lot of problems as well as I could... some still await rewriting. I suppose I will return someday to solve a couple of problems but unfortunately I don't have time right now.

All the best to you,
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Wed Aug 20, 2003 5:26 am

Anyway, I got timings from 0.0005 seconds to 0.0020 seconds (ie 5 to 20 ms) on my 300MHz Pentium II.
Well, Ivor, if you're interested, I can compile your code in my friend's PC. Just post the code or send me to my e-mail : janus85_ren@hotmail.com.
I'll let you know the timing result. :wink: :wink: [/b]

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Wed Aug 20, 2003 9:30 am

why should I? my timings are already better :) you got 0.8 ms on 1.7Ghz.

I have to correct my typos -> it's 0.5 to 2.0 ms, and that's on a pc that is slower more than 6 times. I wrote it correctly in seconds but I failed to represent it correctly in milliseconds :oops: shame on me!

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Wed Aug 20, 2003 3:31 pm

0.5 - 2.0 ms in Pentium II 300 MHZ??
No shit?
That's REALLY REALLY REALLY fast!!
That's makes me even more curious how you did that. Could you send me your code to my e-mail, plzzzzz? :cry: :cry:
That would make a very good study material since I'm new in these kind of programming stuff. :oops: :oops:

P.S. :You said you measured your program with processor ticks. What's that (some kind of stopwatch??)

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Thu Aug 21, 2003 7:20 pm

I looked at your code in other thread. Mainly it's the same as mine. That is the whole idea. The speed improvement comes from a bit different manipulation of array. For example, you would have a speedup if you used individual variables instead of marker array, and then you would have another speedup if you substituted index-based array access with pointer-access. Not much but I suppose you would see a small difference (can tell how much).

And there's a bit more... but it's a rather messy and complicated stuff. I had a though of setting up a page with some kind of tutorial about optimization but it might take a long while yet.

Processor tick is one full cycle processor makes through its input pins (or something like that... I haven't written anything specific for more than a year, so lowlevel knowledge gets rusted :roll: ). A 300MHz processor makes about 300*10^6 cycles per second.

To measure with ticks you use this instruction (rdtsc) to get a value before your code and after your code. Subtract start value from end value and divide by processor speed. That's what I figured out of the code I was given... At least it sounds plausible.

Ivor

P.S. Kurniawan, if you want to "pick a fight" (ie challenge) then pick some more algorithm specific problems. For example you can try 106, 755, 10226, 412 (on this my time isn't correct, should be more like 0.030). On these it isn't just a matter of solving and optimization, there's a whole different and ingeneous approach needed. ;) Don't ask me for hints otr it'll get too simple.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Fri Aug 22, 2003 7:43 am

Well, actually I never meant to "pick a fight" like you said. :wink:
I just like knowledge sharing between programmers. Besides it's impossible for me (just knew these programming stuff one year ago, if you read my post in 'Help on Languages' Section Topic C: Yellow Check Mark ..........) to pick a fight over someone much much more experienced like you :wink: (You joined this site since June 08 2001). So mathematically you've learned programming since two years ago (I don't stand a chance to win over you). So my point is there's no challenge request here, I just simply want to a knowledge sharing. :wink: :wink:
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Aug 22, 2003 11:47 am

I would never say that Ivor learned programming two years ago. It sounds a bit like insult ;-)

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Fri Aug 22, 2003 12:08 pm

it's not an insult -- in some way it's true... :) and indeed I've spent a lot more time with programming... I joined uva 2 years ago and back then it was in order to practise C - I moved from pascal completely to C in 3 weeks. (before that I tried pascal and delphi). But these optimization tricks I learned in a year and a half (I spent 8 month in army this winter). So there must be interest to learn it -- and it won't take much time. All you need is imagination. And you could start by searching the net -- there are very basic tips to start out with.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Mon Aug 25, 2003 9:15 am

Well, I didn't mean to insult :D . All I meant is Ivor knew and learned programming at least since two years ago. As for me, before Sept 2002, I never knew there were such thing in this world (programming) :oops: . All I knew was only operating Microsoft Winword and Entertainment Pack Four and three (chess, Chips, pipedream and other games) and nothing else hehehe...
In uni I only got two subjects related to programming:
1. Algorithm & Programming (25 * 100 min) But they only taught me the basic C commands (printf, while, for , if and else, scanf, gets and that's all), sorting and searching . Never taught us about any algoritm!! :evil: :evil:
2. Data Structures (23 * 100 min) --> only taught us how to implement array, linked list, Binary tree in C.
In addition, I was only taught to use C and that from that 100 min per class, only a small part of it that was effective (the lecturer was very boring and I very very often fell asleep, hehehe).
Not to mention I don't have books or material source on programming or someone to teach me.
But I can be proud of one thing : all the probs I've solved are all my pure thoughts and ideas (never ask someone's algo or help from board) :D :D .
But I must admit Ivor is good (too good compared to me). In every problem ranklist, your name is always in the top 25.
Btw, about the challenge stuff, I've never thought of it before, but I think it would be fun. But of course I won't challenge you right now. You can see how insufficient my current knowledge and experience now. But when the time comes (although it might take a while) I shall challenge you personally (if you're still interested, of course). :wink: :wink:
Adios Amigo!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Sun Aug 31, 2003 10:01 pm

little joey wrote:42, of course!
:D :D :lol: :lol: :wink:

Post Reply

Return to “Volume 1 (100-199)”