diao_david
(David Diao)

本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛

Question a)Let's suppose:

the average length of instructions is n (bytes);

the average time cycles for one instruction is m (times);

the number of instructions for a iteration operation (for(){...} or while(){...}) is i;

the machine word length is w bits.

The approximate upper bound is

(m / 50,000,000) * i * (2^w - 1)^(1,000,000 / (i * n)) (seconds)

For simplicity, we assume: n = 1, m = 1, i = 1, w = 32, then

(m / 50,000,000) * i * (2^w - 1)^(1,000,000 / (i * n))

= (1 / 50,000,000) * (2^32 - 1)^1,000,000 (seconds)

At here, an iterative operation is adopted to prolong running time. But it's difficult to determine the value of i. Similar as assuming i as 1, we can also assume i is a huge digital which occupies all of the 1 M memory except several bytes used by the instructions for iterative operation.

So, my answer is:

The approximate upper bound is

(m / 50,000,000)(1,000,000 / n) (seconds)

m & n still need be assigned assumptive values.

Ordinarily, n ranges from 1 to 4. I forgot the range of m.

That's why my answer of a) is 0.02-0.08s.

Question b)

Compared with HH's answer, my plan is clumsy. But I still believe at least it's a correct answer.

This question is about "google " number. There is an article about "Google" number, you can find at http://www.informatik.uni-frankfurt.de/~fp/Tools/Googool.html

In that article, the author wrote:" At today's speed, the program will run for 3.125*10^85 years. A top machine of today will run the program at a speed that allows the printing of about 10 to the power of 7 digits per second. The average year has roughly 3.2*10^7 seconds, so this machine will print about 3.2*10^14 digits per year. We conclude that this machine will need 3.125*10^85 years to finish printing Googolplex. "

The author provided a program. I just changed the program to conform to the requirement. I select 10^200 to assure this program can run longer than 10^100 years.

My mistakes:

1.

vals = malloc(sizeof(int)*200);

memset (vals,'\0',sizeof(int)*201); // error: you only allocated sizeof(int)*200 bytes

while(!vals[200]) // error: vals[200] is out of the block of you allocated

This is a typo. The first 200 should be 201.

2.

while(!vals[200])

{

// What does these mean? You program seems to will

// never terminate itself.

//

*(ptr = vals) += 1;

while (*ptr == 10)

{

*ptr++ = 0;

*ptr += 1;

}

}

You can compile this program and try to run it. Definitely, it can terminate. It's not as clear as iterative method, but it can really test your understanding of POINT. A very important concept of C/C++.

更多精彩文章及讨论，请光临枫下论坛. 网址: rolia.net/zh

(#25634@0)

2001-2-11 -05:00

2001-2-11 -05:00