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:
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.
// 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
2001-2-11 -04:00
This post has been archived. It cannot be replied.
Page address has been copied. To share, click to copy page address.
Share Online by QR Code

Back To Topic: An interesting question.

Back To Forum: HOME枫下论坛枫下论坛主坛工作学习IT技术讨论