@Aamir: First, regarding overflow, 1000 0000 = -128. Thus, the cycle is 0, 1, 2, ..., 127, -128, -127, ..., -1, and back to 0.
Second, regarding your assertion that you only need a single character instead of an array of them: Based on the above sequence, every time a[0] cycles back to 0, p is set to 1. The next step increments a[1]. If that doesn't result in 0, then p is reset to 0, but if it does result in 0, then p is set to 2, and a[2] will be incremented. This means that a[0] has reached 0 256 times, so a[0] has been incremented 256^2 = 65,536 times. After a[0] has been incremented 256^3 times, p will be set to 3. Etc. After a[0] has been incremented 256^49 times, p will be set to 49 and the loop will be terminated. But 256^49 = 2^392. But 2^392 nanoseconds exceeds 1 google years. Dave On May 10, 4:59 pm, Aamir Khan <[email protected]> wrote: > On Mon, May 9, 2011 at 8:31 PM, Don <[email protected]> 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}; > > I think we can use a single character like char a=0; instead of array of > characters as ultimately the value is incremented for a[0] only in your > code. > > And i was testing with smaller values of n=1 and found something strange > like the value of a[p] increases from 0 to 127 (thats normal) but after > adding 1 to 127 it shows -128..I know that char is of 1byte or 8 bits only > and after +127 its value will overflow. > > I have question regarding the same: > > 1) How to calculate the next value in case of overflow. As i tried > calculating by binary addition and 0111 1111 + 1 = 1000 0000 thats means > answer should have been -0 or 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. > > Don > > > On May 7, 12:24 pm, Dave <[email protected]> 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 <[email protected]> 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 [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > 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: [email protected] <[email protected]> > [email protected] Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
