There's a theorem called the "Infinite Monkey Theorem" which postulates that a chimpanzee banging on a typewriter long enough ( approaching infinity ) will eventually have re-created the complete works of Shakespeare.
Infinite monkey theorem - Wikipedia, the free encyclopedia
So, I had an idea for my own variation of this sort of theorem which goes like this.
Any file or data which is or can be expressed in a series of bytes ( 8 bit variety ) can and will eventually be reproduced if treated as a little-endian integer ( first byte is least significant and last is most significant ) of arbitrary length using extended-precision arithmetic techniques if a second value of arbitrary precision is initialized to zero and incremented one by one and growing a byte at a time in precision as needed until the second arbitrary integer matches the first ( the data )
In other words, a file can be thought of as a little endian integer of file size in bytes length. First byte of file is least significant and last byte is most significant. As such it represents a specific value.
As such, if an arbitrary precision integer is initialized to zero and incremented one by one in an iterative loop, given long enough, will eventually ( given infinity ) have reproduced every bit of data on every computer in the Universe. Not only that, but it will have reproduced the Human Genome for example given enough time.
So I wrote the simplest of programs to test my little thought experiment. I created two strings.. One 4 characters in length: "APES" and a second that is 8 characters in length: "MONKEYS!".
The idea is that I copy each string into a 4 byte unsigned 32 bit integer and a 8 byte unsigned 64 bit integer respectively in which case they equal the following values:
"APES" equals DEC: 1,397,051,457 HEX: 0x53455041
"MONKEYS!" equals DEC: 2,401,361,180,469,645,133 HEX: 0x215359454b4e4f4d
Ok. As such, In the first case of "APES", I created a second unsigned 32 bit integer which is initialized to zero and incremented by one in a loop until eventually it reproduces the 4 characters of the string "APES"... This worked perfectly and reproduced the string "APES" in 3 seconds ( I timed it )
Ok. The second test is coded exactly the same, but in the second portion of the test, I substituted a 8 character string for the 4 character string and used 64 bit unsigned integers to store the target value and the work value which is to be incremented one by one until it matches the value of the string "MONKEYS!" when the string is treated as an integer.
Ok. Here's the problem... The first part of the test finished in almost exactly 3 seconds on my computer with perfect results. However the second 64 bit portion of the code ran for over 4 and a half hours without results.
So here are some of my calculations based on the results of the first 32 bit test
"APES" : 1,397,051,457 was reached from 0 incrementing to 1.3 billion in 3 seconds
1,397,051,457 / 3 == 465,683,819 increments per second
Ok, with that in mind, here are my projections for the amount of time that the second 64 bit portion of my test code will take to complete... like I said, I ran the program for over 4 hours without results...
"MONKEYS!" : 2,401,361,180,469,645,133 / 465,683,819 == 5,156,634,356 seconds to complete
5,156,634,356 / 3600 == 1,432,398 hours to complete
1,432,398 / 24 == 59,683 days to complete
59,683 / 365 == 163 years to complete
Are my calculations correct? Will the following code really take 163 years to complete?
Any input will be appreciated!!!!
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <locale.h>
#include <time.h>
typedef unsigned long DWORD;
typedef unsigned long long QWORD;
char apestr[5] = "APES";
char monstr[9] = "MONKEYS!";
DWORD apes;
QWORD monkeys;
DWORD work_dw;
QWORD work_qw;
int main(void)
{
clock_t start,stop;
double duration;
setlocale(LC_NUMERIC,"");
memcpy(&apes,apestr,4);
memcpy(&monkeys,monstr,8);
printf("APES : DEC: %'lu HEX: %#lx\n",apes,apes);
printf("MONKEYS! : DEC: %'llu HEX: %#llx\n",monkeys,monkeys);
printf("First, let's find APES\n");
work_dw = 0;
start = clock();
while(work_dw != apes) { ++work_dw; }
stop = clock();
duration = (stop - start) / CLOCKS_PER_SEC;
printf("APES found!!!!!!!!!!\n");
printf("Found in %f seconds\n",duration);
printf("Now let's find MONKEYS!\n");
start = clock();
work_qw = 0;
while(work_qw != monkeys){ ++work_qw; }
stop = clock();
duration = (stop - start) / CLOCKS_PER_SEC;
printf("MONKEYS! found!!!!!!!!!!!!\n");
printf("Found in %f hours %f minutes\n",
duration / 3600,
duration / 60);
return 0;
}
And please note, that I do know that I can make the duration of this program considerably less by using optimization flags in the compiler. However the optimization flags produce code which doesn't actually do the number of increments necessary. It simply optimizes the code and assigns the target value rather than generating the code for the loop, which is sort of like cheating..
For example, if I compiled the code like this: gcc poc.c -o poc -O2
It produces code which completes in a fraction of a second with perfect results save the fact that it hasn't actually done the number of increments necessary to prove my silly theory.
WIth flags for optimization of speed - i.e. -O2 - it simply looks at the loops in my code - simple as they are - and decides it's less than optimal and replaces it with simple assignments of values rather than performing the iterative increments in my code...
e.g.
Code:
while(work_dw != apes) { ++work_dw; }
becomes
Any thoughts on how long this program will take to finish without optimizations?
Thanks in advance
Twiki
How long can a 64 bit unsigned integer take to increment from 0 to 2.04 quadrillion?
Originally Posted by twiki
