1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#!/usr/local/bin/perl
use strict;
use warnings;
use feature qw(say);
use Test::More;
use Benchmark qw(cmpthese timethis);
use Data::Dumper qw(Dumper);
timethis( 2_000_000, sub { get_no_one_count_9( 0xFFFFFFFFFFFFFFFF ); } );exit;
my @TESTS = (
[ 15, 8 ],
[ 25, 13 ],
[ 100, 80 ],
[ 1000, 728 ],
[ 1100, 728 ],
[ 1200, 728 ],
[ 1300, 728 ],
[ 2000, 729 ],
[ 2100, 809 ],
[ 2200, 810 ],
[ 3000, 1458 ],
[ 4000, 2187 ],
[ 5000, 2916 ],
[ 10000, 6560 ],
[ 20000, 6561 ],
[ 25000, 6561+2916 ],
[ 25500, 6561+2916+324 ],
[ 25540, 6561+2916+324+27 ],
[ 25543, 6561+2916+324+27+2 ],
[ 100000, 59048 ],
[ 1000000, 531440 ],
);
# warn "@{$_} -> ", get_no_one_count_9($_->[0]), "\n" foreach @TESTS;
is( get_no_one_count_9($_->[0]), $_->[1] ) foreach @TESTS;
is( get_no_one_count($_->[0]), $_->[1] ) foreach @TESTS;
done_testing();
cmpthese(-5,{ 'scan 98' => sub { get_no_one_count( 98 ) },
'opt 98' => sub { get_no_one_count_9( 98 ) }, });
cmpthese(-5,{ 'scan 987' => sub { get_no_one_count( 987 ) },
'opt 987' => sub { get_no_one_count_9( 987 ) }, });
cmpthese(-5,{ 'scan 9876' => sub { get_no_one_count( 9876 ) },
'opt 9876' => sub { get_no_one_count_9( 9876 ) }, });
cmpthese(-5,{ 'scan 98765' => sub { get_no_one_count( 98765 ) },
'opt 98765' => sub { get_no_one_count_9( 98765 ) }, });
cmpthese(-5,{ 'scan 987654' => sub { get_no_one_count( 987654 ) },
'opt 987654' => sub { get_no_one_count_9( 987654 ) }, });
cmpthese(-5,{ 'scan 9876543' => sub { get_no_one_count( 9876543 ) },
'opt 9876543' => sub { get_no_one_count_9( 9876543 ) }, });
sub get_no_one_count {
my $n = shift;
return scalar grep { ! m{1} } 2..$n;
}
## Optimized version.... seems to work ... and far better than scan...
sub get_no_one_count_9 {
my ( $n, $count, $pow_9 ) = ( shift, 0, 1 );
while($n) {
my $t = $n % 10; ## get last digit
$count = 0 if $t==1; ## Throw everything away we've found a 1
$count += !$t ? 0 : $t == 1 ? ($pow_9-1) : ($t-1)*$pow_9;
## 0 it contributes nothing
## 1 contributes 9^X-1
## 2-9 contributes (n-1)9^X
$pow_9 *= 9; ## update power of nine
$n = ( $n - $t )/10; ## drop last digit
}
return $count;
}
## Comparison
# | N | scan | opt | Speed-up |
# | --------: | --------: | --------: | ---------: |
# | 98 | 16,027 | 1,173,850 | 72 |
# | 987 | 2,623 | 867,796 | 330 |
# | 9,876 | 253 | 685,956 | 2,715 |
# | 98,765 | 24.4 | 565,427 | 23,155 |
# | 987,654 | 1.23 | 482,800 | 392,998 |
# | 9,876,543 | 0.23 | 418,410 | 1,853,771 |
|
