I don't know that it takes exactly 9 operations. I ran the program on
my 3 GHz computer with n=4. It took 17 seconds. 17*3 billion / 2^32 is
11.87 clock cycles per iteration through the loop. A clock cycle is
not the same as an operation, because many machine operations take
more than one clock cycle. If the computer we are using for this
problem can run one iteration of the loop as a single operation, n=49
would be enough. If it takes 9 operations, n=48 would be enough. So it
depends on the computer, and I don't really have enough information to
say which value of n to use. However, n=49 certainly meets the
requirements of the problem, even if it is excessive.
Don
On May 11, 7:11 am, Aamir Khan <ak4u2...@gmail.com> wrote:
> On Mon, May 9, 2011 at 8:31 PM, Don <dondod...@gmail.com> wrote:
> > That would do it if you have a 64-bit type, which most implementations
> > have, but the standard does not require.
> > I think that I can make it shorter and cleaner.
>
> > int main(int argc, char* argv[])
> > {
> > const int n=49;
> > char a[n]={0};
> > int p=0;
>
> > // This line will run for 10^100 years
> > for(; p < n; p = ++a[p] ? 0 : p + 1);
>
> > return 0;
> > }
>
> > The array of 49 bytes provides 392 bits of state, which will take more
> > than the 2^387 cycles available in a google years.
>
> > If the processor takes 9 operations to execute the loop, a value of
> > n=48 would be sufficient.
>
> Can you elaborate the 9 operations that execution of for loop will take.
>
> Don
>
>
>
>
>
> > On May 7, 12:24 pm, Dave <dave_and_da...@juno.com> wrote:
> > > @Don: Here is my solution:
>
> > > unsigned long long int a=1;
> > > unsigned long long int b=0;
> > > unsigned long long int c=0;
> > > unsigned long long int d=0;
> > > unsigned long long int e=0;
> > > unsigned long long int f=0;
> > > unsigned long long int g=0;
> > > unsigned long long int h=0;
> > > /* here is the line "/
> > > while(a)if(!++h)if(!++g)if(!++f)if(!++e)if(!++d)if(!++c)if(!++b)++a;
>
> > > My reasoning is as follows: 1 google years ~= 10^116.5 nanoseconds ~=
> > > 2^387. Thus, incrementing an integer of length 387 bits once every
> > > nanosecond should take a google years to overflow. Seven 64-bit
> > > integers provides 448 bits of state.
>
> > > Dave
>
> > > On May 6, 11:25 am, Don <dondod...@gmail.com> wrote:
>
> > > > What is the shortest single line in a C program which will take more
> > > > than a google years to execute, but will eventually complete? You are
> > > > permitted to have code before or after the line, but execution of the
> > > > code must remain on that line, meaning no function calls, etc. Assume
> > > > a processor which executes 1 billion operations a second.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Aamir Khan
> Indian Institute of Technology Roorkee,
> Roorkee, Uttarakhand,
> India , 247667
> Phone: +91 9557647357
> email: aami...@iitr.ernet.in <aamir...@iitr.ernet.in>
> ak4u2...@gmail.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
