How long to complete: while ($i<1e10)

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View
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
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;
   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;
   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?

Re: How long to complete: while ($i<1e10)

Jose Gomez schrob:
> void main()
> void main()
> {

> Thoughts anyone?

Yes. void main is wrong. See

BEGIN{$^H =sub;$^H |=0x28000}"Just another Perl hacker,\n"

Site Timeline