An interesting question. -diao_david(David Diao) @拉斯维加斯华人论坛:拉斯维加斯枫下论坛 The Rolia Forum of Las Vegas

工作学习 / IT技术讨论 / An interesting question. -diao_david(David Diao); 2001-2-9 {1149} (#25443@0)
本文发表在 rolia.net 枫下论坛This is a prelimitary question about Embeded Code Programmer. I failed in that interview, but I really think this question is very interesting.
Which expert can tell me what's wrong wtih my answers.

Consider a computer with standard CPU architecture running at 50MHz, one megabyte of memory, no external storage and no external input.

a) Give an approximate upper bound on the running time of the longest-running possible (terminating!) program.

b) Write a small (less than 10 lines) terminating C program with a running time of more than a googol (10^100) years. Assume a 32-bit word size and no external inputs.

You may disregard practical limitations, like energy resources or the end of the universe.

Answer:
a) Depending on the average length of instructions and average time cycles used by these instructions, the answer is between 0.01-0.08s.
b)
#include <mem.h>
#include <stdlib.h>
void main ()
{
int *vals,*ptr;
vals = malloc(sizeof(int)*200);
memset (vals,'\0',sizeof(int)*201);
while(!vals[200])
{
*(ptr = vals) += 1;
while (*ptr == 10)
{
*ptr++ = 0;
*ptr += 1;
}
}
free(vals);
}更多精彩文章及讨论，请光临枫下论坛 rolia.net

My answer for discussion -old(HH); 2001-2-11 {2706} (#25614@0)
本文发表在 rolia.net 枫下论坛a)
We have known:
Time per cycle = 1 / 50MHz = 1 / 50,000,000 seconds.
The total memory space = 1 MBytes = 1024 * 1024 bytes ~ 1,000,000 bytes.

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.

My answer:
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)

b)
10^100 years = 365 * 24 * 60 * 60 * 10^100 (seconds)
= 365 * 24 * 3600 * 10^100 (seconds)
~ 30,000,000 * 10^100 (seconds)
= (1 / 50,000,000) * 50,000,000 * 30,000,000 * 10^100
= (1 / 50,000,000) * 1.5 * 10^115 (seconds)
< (1 / 50,000,000) * 10^(15 * 8) (seconds)

My 9 lines (less than 10 lines) program:

for (double d1 = 0.0; d1 < (1.0e15 - 1.0); d1 += 1.0)
for (double d2 = 0.0; d2 < (1.0e15 - 1.0); d2 += 1.0)
for (double d3 = 0.0; d3 < (1.0e15 - 1.0); d3 += 1.0)
for (double d4 = 0.0; d4 < (1.0e15 - 1.0); d4 += 1.0)
for (double d5 = 0.0; d5 < (1.0e15 - 1.0); d5 += 1.0)
for (double d6 = 0.0; d6 < (1.0e15 - 1.0); d6 += 1.0)
for (double d7 = 0.0; d6 < (1.0e15 - 1.0); d7 += 1.0)
for (double d8 = 0.0; d8 < (1.0e15 - 1.0); d8 += 1.0)
;

c) Some errors in your answers
void main ()
{
int *vals,*ptr;
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
{
// What does these mean? You program seems to will
// never terminate itself.
//
*(ptr = vals) += 1;
while (*ptr == 10)
{
*ptr++ = 0;
*ptr += 1;
}
}
free(vals);
}

**My suggestion after finishing this homework**
I kindly suggest you don't touch any "C" related job at present stage until you learn much more about "C", in order to save your valuable time and energy and the interviewers' valuable time and energy. Otherwise, even if you accidentally get a "C" related job, you will suffer from it very much.

**My feelings after finishing this homework**
I sadly see some of the reasons why Canadian IT companies suspect Chinese IT job seekers so much.

**My wonder after finishing this homework**
How could you get the interview opportunity?更多精彩文章及讨论，请光临枫下论坛 rolia.net

HH, I really appreciate your advices -diao_david(David Diao); 2001-2-11 {1368} (#25630@0)
本文发表在 rolia.net 枫下论坛I totally agree with you.

In fact, all of my knowledge about computer are learned by myself. Even I can solve some puzzles by myself. I know lacking systemic knowledge about computer is my biggest weakness. My aim to post this quiz on this forum is to show the different between professional & amateur.

Another interesting point is, in all of my resumes posted in last summer. I just mentioned that I have some experience about real-time system and ASSEMBLY. But all of those agencies who interviewed me were care of this experience. I believe those agencies lack enough knowledge to identify critical skills needed by their customers.

Thanks again for HH's answers and suggestions.

BTW, HH asked how I can get the interview opportunities. Except posting my resume on some job-hunting websites, I do not do anything. Because I know I am not as good as those IT elites, I gave up my dream to be an IT tek. Just after I was rejected by that company, I deleted all of my resumes from Internet, and began to prepare GMAT. Fortunately, I got opportunity to study in Richard Ivey.

The biggest mistake of mine is that I've spent too many times on different fields. Apperantly, I am very versatile, but I am not expert of any field. This experience gives me bitter feeling. And I know, since present, I should focus all of my energy on one aim.更多精彩文章及讨论，请光临枫下论坛 rolia.net

Thank you. I am very interested in your quiz, thouth I don't know whether my answer is correct or not. Hard work pay off. It is not easy for us to survive here. Let's make our great efforts to learn much more! -old(HH); 2001-2-11 (#25632@0)
Congratulations for your new opportunity! Any experience is a part of one's life. Cherish them! -old(HH); 2001-2-11 (#25675@0)

Thanks. I take this opportunity of expressing my sincere appreciation of your help to me -- a fan of computer. -diao_david(David Diao); 2001-2-11 (#25676@0)

Discussion -diao_david(David Diao); 2001-2-11 {2652} (#25634@0)
本文发表在 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

My discussion -old(HH); 2001-2-11 {1180} (#25658@0)
本文发表在 rolia.net 枫下论坛Thank you for your discussion!

a)
1. You answer of 0.02-0.08 seconds is not reasonable. You answer means that under that condition any program can not last to run for more than 0.02-0.08 seconds.
2. My understanding of upper bound here is as long as possible.
3. Of course as you said we can also assume i is a huge digital which occupies all of the 1 MB memory except several bytes used by the instructions for iterative operation. But in such case we will waist a lot of memory to do iteration operations. The more the iteration operations (for(){for(){for(){...}}}) we put in a program the more time it can last to run.

b)
// The range of subscripts for vals[] should be 0 to 199 if this is a C program.
// vals[200] is out of the memory block you allocated. Dangerous!
// Please change vals[200] to vals[199], then run it and tell me the result.
// Let's learn from our mistakes! Thank you again!
//
int *vals,*ptr;
vals = malloc(sizeof(int)*200);
memset (vals,'\0',sizeof(int)*200);
while(!vals[200]) // error: vals[200] is out of the block of you allocated
{
*(ptr = vals) += 1;
while (*ptr == 10)
{
*ptr++ = 0;
*ptr += 1;
}
}更多精彩文章及讨论，请光临枫下论坛 rolia.net

我当时的想法就是想取个200的整，虽然我知道在C里是以0为底。如果真的想掐好时间刚好10^100年的话，用心算还真有些麻烦了。 -diao_david(David Diao); 2001-2-11 (#25665@0)
BTW, you ask me "Please change vals[200] to vals[199], then run it and tell me the result. " Ok, please wait! I must write this item in my will. Then my son's son's son's ... can tell you the result. :-) -diao_david(David Diao); 2001-2-11 (#25667@0)

I will disappear from this world before you. -old(HH); 2001-2-11 (#25670@0)

对于问题二的讨论 -diao_david(David Diao); 2001-2-11 {2067} (#25657@0)
本文发表在 rolia.net 枫下论坛while (!vals[max]) {
*(ptr = vals) += 1;

while (*ptr == 10) {
*ptr++ = 0;
*ptr += 1;
}
}

当时，为了满足题目中10行程序的要求，我省去了数据初始化的部分。
（问题：有些朋友告诉我，现在的嵌入系统已经都转到用 Embeded C 或者 Embeded C++ 了。请问专家，在内存有限的的条件下，某些初始化的的命令是否可以省略。比如，本题中我不清零，有潜在的危险嘛？）

这段程序其实是很巧妙的。我没有足够的聪明来写这样的程序，即使看懂这段程序也花了不少的精力。

这短短的5行中，最主要的就是指针的调用。比起其他高级语言来，C/C++最强大的功能就是能够通过指针，直接控制内存。当初我用 Delphi 写程序，到了需要控制内存的时候，就是没有办法。最后只好用 C++ 写了个动态连接库。

好了再回到这段程序。
*(ptr=vals)+=1
vals 已经被分配了地址，在第一行，就把这个地址赋给了ptr。然后该地址的数值加1。
如此累加到该地址的数值为10，满足了第二个 while 的条件 (*ptr==10)。
*ptr++=0
"这一行比较绕人。请注意操作符的优先顺序。是指针 ptr 先加一，然后再给 ptr 指向的地址赋零。"谢谢 HH 的帮助，我终于发现原先的解释是错误的。正确的解释应该是 : 将ptr所指的地址赋零，然后指针加一。如果用 ++ptr 就不行了。移动指针以后，个位数没有清零。
*ptr+=1
新地址（指针 ptr 移动后的地址）的值加1。
！！！注意了，当这次 +1 后，如果 *ptr 也变成了 10，就会重复着一步骤。就像 99+1 一样，不但个位变成了0，十位也要变成0，而百位变成1。
因为 ptr=vals，所以 ptr指向的各个地址和 vals数组的各个单元也是对应的。ptr指向的地址的数值的变化，其实就是 vals[]数组各个单元数值的变化。
依此类推，最后 vals[max]也变成了1。就退出了while(!vals[max]) 的循环。

其实我一开始就想到了用循环的方法，但是后来看到这个程序，觉得这个更有意思。

我自己总结面试失败的原因：
1. 基础概念不清楚。第一问中，运行一个指令，需要几个时钟周期，我就没有明确的概念。
2. 正如 HH 指出来的，内存分配有问题（在嵌入系统中，如果程序员已经知道所要占用的内存空间范围，是否还有必要明确的分配内存？）。虽然我知道是键入错误。但是起码也是 not detail-oriented。
3.程序的风格可能有问题。我这样的半瓶子醋，写程序很不规范。还请专业人士能给大家讲讲，写程序中的一些规则。（比如有的人提倡匈牙利命名法，有的人则对此很反感，到底那个是公认的规范）更多精彩文章及讨论，请光临枫下论坛 rolia.net

"*ptr++=0 这一行比较绕人。请注意操作符的优先顺序。是指针 ptr 先加一，然后再给 ptr 指向的地址赋零。 " It sould be *(ptr++)=0; -old(HH); 2001-2-11 (#25661@0)

我编译并且运行了这段程序。*ptr++ 可能不规范，但是它确实实现了和 *(ptr++) 同样的功能。 -diao_david(David Diao); 2001-2-11 (#25664@0)

It is not a problem about programming style. I think it is better for you to know the difference. Please try: -old(HH); 2001-2-11 {425} (#25669@0)
int vals[200];
int * ptr;
::memset(vals, '\0', sizeof(int) * 200);
ptr = vals;
*ptr = 10;
cout << "before " << *ptr << endl;
*ptr++ = 20;
cout << "after " << *vals << " " << *ptr <<endl;

Then try:
int vals[200];
int * ptr;
::memset(vals, '\0', sizeof(int) * 200);
ptr = vals;
*ptr = 10;
cout << "before " << *ptr << endl;
*(ptr++) = 20;
cout << "after " << *vals << " " << *ptr <<endl;

I compile them with TC2.0. Just change the lines of output. The results of both programs are same. Could you tell me why? -diao_david(David Diao); 2001-2-11 (#25673@0)

I am so sorry! That is my mistake. I disunderstood the meaning of ++ operator when I wrote above. *(ptr++)=0 and *ptr++=0 get the same result. It should be *++ptr=0. Sorry again! -old(HH); 2001-2-11 (#25678@0)

Bingle!!! But even ptr++ is different from ++ptr, this program still can terminate. At here, ++ptr is wrong. -diao_david(David Diao); 2001-2-11 (#25680@0)

I have been dizzying and confusing. -old(HH); 2001-2-11 (#25681@0)
Dizzying posting. -old(HH); 2001-2-11 {346} (#25682@0)
If you have changed vals[200] to vals[199] (vals[200] is an error) and keep the sentence *ptr++=0 in your original program, it seems to will not terminate ifself. I have not practised it. If you will try it, please let me know the result. If it terminte itself, I misunderstand something and I will learn some from my misunderstanding. Thank you!

I still prefer change the first 200 to 201. Cause I do not want to make two mistakes. And I tried this program to create small number such as 10^2 or 10^3, it does terminate itself. -diao_david(David Diao); 2001-2-11 (#25685@0)

I have carefully read your program for 5 times again and I think I have known what does it mean. I agree with you this time that your program will terminate itself. I made some big mistakes and learn more today. I say sorry to you. -old(HH); 2001-2-11 (#25706@0)
Just because these interesting puzzles, I love computer. And I am glad to have this opportunity to discuss them with you. -diao_david(David Diao); 2001-2-11 (#25722@0)

I am glad to discussion with you too. Because the memory access errors, I didn't carefully read your program at the start stage. Next time I will be careful. -old(HH); 2001-2-12 (#25759@0)
I have a better answer of question a): approximately (1 / 50,000,000) * 1,000,000!. -old(HH); 2001-2-12 (#25765@0)

Sounds good. -diao_david(David Diao); 2001-2-12 (#25807@0)

@Las Vegas

An interesting question.

Replies, comments and Discussions:

More Topics