本文发表在 rolia.net 枫下论坛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
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