How long to complete: while ($i<1e10){i++;}

J

Jose Gomez

Poking around with the Google Labs Aptitude Test question #17, i.e.
"Consider a function which, for a given whole number n, returns
the number of ones required when writing out all numbers between
0 and n.
For example, f(13) = 6
Notice that f(1)=1. What is the next largest n such that
f(n)=n?",
I wondered if there exists a number that satisfies the same function
for all digits 1 thru 9; that is, a number N such that writing all the
numbers between 0 and N requires N ones, N twos, N threes, etc.
The script ran for days! At the last interuption, the largest
interesting number found was 500,000,000: it satisfies the function
for 1,2,3 and 4.
Anyway, in checking what was taking so long I found that on a Dell
Dimension 4400 (1.60 Ghz Intel Pentium 4 with 256MB RAM) the following
script runs for about an hour:

#----------
use strict;
use warnings;
my $n=0;
while( $n < 1e10 ) {
$n++ ;
}
#----------

So to run this while loop up through a limit of $n<1e16 would require
a susprising 114 years.

perl -v
This is perl, v5.6.1 built for MSWin32-x86-multi-thread
(with 1 registered patch, see perl -V for more detail)
Binary build 635 provided by ActiveState Corp.
Built 15:34:21 Feb 4 2003

On a HC PV m470n Dell (3.00 Ghz Intel Pentium 4 with 512MB RAM) and
perl -v
This is perl, v5.8.4 built for MSWin32-x86-multi-thread
(with 3 registered patches, see perl -V for more detail)
Binary build 810 provided by ActiveState Corp.
Built Jun 1 2004 11:52:21
the perl script ran in about 30 minutes - still over 70 years to
iterate through 1e16!

Now, on the same Dell, the binary compiled with Mingw GCC 3.2.3 from
void main()
{
long int i;
i=1;
while ( i > 0) {
i++ ;
}
}
completes in less than one minute. The max long int is 2,147,483,647
so this is roughly comparable to a limit of 1e9 in the perl script.
Using type double in C to get the same 1e10 limit
void main()
{
double limit, i;
i=1.0;
while ( i < 1.0e+10 ) {
i=i+1.0 ;
}
}
runs in under 2 minutes, and can iterate to through 1.0e+11 in about
25 minutes - projecting about 34 years to go through 1e16.

Thoughts anyone?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top