136 - Ugly Numbers

Ivor · Post by **Ivor** » Tue Jul 29, 2003 2:33 pm

you meant 1499

What is the complexity of the algorithm? I had mine in O(n) time and O(n) memory. I could challenge you, but then I would need to use bignumbers as I'm using C. Or convert to float.

Ivor

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Jul 29, 2003 5:06 pm

My time/memory complexity is also O(n). I use lazy functional programming so computations are made only when really necessary.

You think that float conversion won't give up some information? Of course, if float/double types are big enough to remember 300000-th ugly number, we can always add another zero or two

Ivor · Post by **Ivor** » Tue Jul 29, 2003 5:22 pm

Yes I believe we could.

It's because I don't want to add the bignumbers (as I'm not into C++) I won't challenge you. And besides, my bignumbers routines are fast enough to win the challenge.

See 495 for example. I'm not the first though, but then again Ivan's the asm expert.

Ivor

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Jul 29, 2003 5:51 pm

I read about yours rivalry on problem 495

I belive that you like to optimize your code and your stats are a proof (21000 submissions, 15900 accepted and 177 problems solved). It could be hard to win a speed contest with you - impossible if you work long enough to boost your code.

But it's not my point. You can always add bignumber and other stuff. I want to point out that some problems can be solved easily in functional languages, which I look forward to see available during the contests. I wonder how long will I wait

BTW: some Polish contests allow to submit code in OCaml.

InOutMoTo · Post by **InOutMoTo** » Sun Aug 10, 2003 1:34 pm

I got AC by using chrismoh's method.

But I have two little question:

First, how to set " long long " number to maxium? (convenient to compare)

Second, I set a long long number to 9999999999 and get a compile error.
It says integer constant out of range

So, I change it to 900000000 to pass compiliong.

Can anyone tell me why ? Thx a lot

[/c]

Joseph Kurniawan · Post by **Joseph Kurniawan** » Wed Aug 13, 2003 5:42 pm

Here's my code. Can anyone tell me its complexity? (I don't have any idea what complexity means)

[c]
#include<stdio.h>
long num1, num2, num3, marker[4], index;
long number[1510]={0,1,2,3,4,5};
void main(){

index=6; marker[0]=3; marker[1]=3; marker[2]=5;

while ( index <= 1500 ) {

num1 = 2 * number[marker[0]];

num2 = 3 * number[marker[1]];

if( num2 == num1 ) num2 = 3 * number[++marker[1]];

num3 = 5 * number[marker[2]];

if(num3==num1) num3=5*number[++marker[2]];

if(num3==num2) num3=5*number[++marker[2]];

if(num2<num1||num3<num1){

if(num3<num2){number[index]=num3;marker[2]++;}

else{number[index]=num2;marker[1]++;}

}

else{number[index]=num1;marker[0]++;}

index++;

}

printf("The 1500'th ugly number is %li\n",number[1500]);

}
[/c]

It ran in my PC (Pentium I 133MHz) in 9.5 ms (I read that in compile information --> alt C + I).

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Aug 14, 2003 3:07 am

General idea of complexity is to estimate how will the time of execution change if the size of input data increases.
Lets consider some input data of size n (in problem 136, the order to display the n-th ugly number). If a solution does not more than c*n elementary operations for some constant c, we say that it is of linear complexity which is marked as O(n).
If the upper bound is c*n^2, we have an O(n^2) solution, and so on.
Generaly if it is enouth to make not more than f(n) operations then the algorithm of O(f(n)) complexity.

Now try to evaluate the complexity of your algorithm.

I recommend you to read more about this subject. It's very interesting and useful as well.

Master · Post by **Master** » Thu Aug 14, 2003 4:46 am

Now I found very interesting code on the book programming challenges for the prime factorization. I think this code will be very helpful for this problem.

M H
CUET Old Sailor

Joseph Kurniawan · Post by **Joseph Kurniawan** » Thu Aug 14, 2003 9:45 am

Correction:
in Pentium I (133MHz) it ran in 5.3 ms (0.0053 sec) instead of 9.5 milisec.
in Pentium 4 (1.7 GHz) it ran in 0.8 ms (0.0008 sec).

You're the Scheme guy, aren't you?
I've read your previous post, but sadly I don't know anything about Scheme. If you can translate your code in C (since that's the only language I understand), maybe I'll be able to understand more about this subject.

Just asking, what's the complexity of your Scheme code?

Btw, for epsilon0, only your first program that works. But it also produced wrong answer (The output is 675). The rest gave me compile error when I tried to compile them. Are those programs have been "arranged" ?(some parts are hidden).

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Aug 14, 2003 1:46 pm

So why don't you share with us?

Krzysztof Duleba · Post by **Krzysztof Duleba** » Thu Aug 14, 2003 1:59 pm

My complexity is linear, but it is so because of lazy programming involved. I used streams, which are a kind of infinite lists. How can an infinite thing be stored in finite memory, you might ask? It can, as n-th element of stream is computed only when the program is refering to it, not earlier, and then remembered. So my code counts only the numbers directly used to get the result and the complexity is linear.

C is not a functional language and lazy programming isn't possible in such easy way. There is a Scheme compiler, Bigloo, which works by translating Scheme code into C, but the result is unreadable, has at least 500kB and doesn't have big numbers built in.

DD · Post by DD » Fri Aug 15, 2003 10:50 am

InOutMoTo:

you should use <limits.h>

In <limits.h> there is a INT_MAX to set the maxium of integer

i think this should help you

Joseph Kurniawan · Post by **Joseph Kurniawan** » Fri Aug 15, 2003 3:33 pm

Wow Krzysztof Duleba,
you've got lots of replies since the first time I viewed this post.
Btw, you implied that your code ran in 0.1 sec (about 100 milisec) to solve the prob 136. My code, perhaps as you've seen before ran in only
0.8 milisec. That's means my code runs about 125 times faster than yours.
How can the difference be so big :
1. Bad compiler ( Scheme programs run slowly compared to C )
2. What's your PC freq? (the MHz or GHz stuff. I achieved 0.8 milisec in
friend's PC 1.7 GHz)
3. Or maybe my algo is better than yours? (No offense)

I'm really interested in this prob. The first time I solve this is by using precalc. I count the number from 1 to the 1500'th ugly number. It took me half day

. But your post inspired me not to use precalc.
Perhaps you can show me your code in C ? (If you don't mind).

Krzysztof Duleba · Post by **Krzysztof Duleba** » Fri Aug 15, 2003 4:23 pm

You asked about my CPU in other thread and I answered there.

I didn't use a compiler, but interpreter, which is the reason for the speed difference. Scheme compilers that I know don't have big numbers built in.

Scheme code, compiled, runs as fast as C programs, because it is translated into C (or Java) first. I don't like to do that - the code is boosted significantly, but limited as well - some things just don't work with C.

Joseph Kurniawan · Post by **Joseph Kurniawan** » Sun Aug 17, 2003 6:18 am

Oh, yeah silly me

But now I got a few question:

1. You said it was Athlon 1700 ........, I supposed that means you freq is 1.7 GHz ( same as Pentium 4 1.7GHZ ), correct ?

2. Using interpreter ? So, how long did your program really run ? Have you tried to implement your algo in C? If you have try to compare it with my run time 0.0008 sec. This 'speed' thing really makes me curious since I'm searching for the fastest algo for this kind of prob.

Thanx a lot !!!