Merge pull request #2344 from holli-holzer/master

faster! faster!!

2 files changed, 86 insertions, 20 deletions

diff --git a/challenge-079/markus-holzer/raku/bench.raku b/challenge-079/markus-holzer/raku/bench.raku
index 1ab34ceea2..76ba62d8fe 100644
--- a/challenge-079/markus-holzer/raku/bench.raku
+++ b/challenge-079/markus-holzer/raku/bench.raku
@@ -1,32 +1,86 @@
 use Bench;
+use experimental :cached;
 
 unit sub MAIN(Int $N = 42);
 
-#say i($N);
-#say r($N);
-#say f($N);
-#say k($N);
-#say l($N);
-
+#say ($N...1).map( &i ).sum;
+#say ($N...1).map( &r ).sum;
+#say (1..$N).map( &f ).sum;
+#say (1..$N).map( &k ).sum;
+#say ($N...1).map( &l ).sum;
+say a($N);
+say b($N);
+#exit;
 sub i {
     +$^n.base(2).indices(1) }
 
 sub r {
     +($^n.base(2) ~~ m:g/1/) }
 
-sub f {
+sub f is cached {
     $^n == 0 ?? 0 !! $^n !%% 2 + f( $^n div 2 ) }
 
-sub k($n is copy) {
+sub k($n is copy) is cached {
     my $c = 0; while $n != 0 { $n = $n +& ($n-1); $c++ }; $c }
 
-sub l {
+sub l is cached {
     state @b = 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4;
     $^n == 0 ?? 0 !! @b[ $^n +& 0xf ] + l($^n +> 4) }
 
-Bench.new.timethese( 10000, {
-    base2-with-indices => { i($N) },
-    base2-with-regex   => { r($N) },
-    div2-recursive     => { f($N) },
-    kernighan          => { k($N) },
-    lookup-recursive   => { l($N) }})
\ No newline at end of file
+sub a($n) {
+    my @scale = (1, 2 * * ...^ * > $n);
+    my $total-bits = 0;
+
+    for @scale -> $pwr {
+        my $fill = ($n + 1) / (2 * $pwr);
+        my $max = $pwr * 2;
+
+        my $fill-full = $fill.Int;
+        my $fill-frac = $fill - $fill-full;
+
+        my $bits-full = $fill-full * $pwr;
+        my $bits-frac = 0;
+
+        if $fill-frac > 0.5 {
+            $bits-frac = ($fill-frac - 0.5) * $max;
+     #       say "($fill-frac - 0.5) * $pwr" if $verbose;
+        }
+
+        my $bits = $bits-full + $bits-frac;
+      #  say "bits-full=$bits-full, bits-frac=$bits-frac, bits=$bits" if $verbose;
+
+        $total-bits += $bits;
+    }
+
+    $total-bits;
+}
+
+sub b(Int \N)
+{
+    my Int \t = 2;
+    my Int \r = 0;
+    my Int \n = N;
+
+    while n {
+        my Int \a = t +> 1;
+        my Int \s = N +& ( t - 1 );
+        my Int \d = N div t;
+
+        r := r +  d * a;
+        r := r +  1 + s - a if 1 + s > a;
+        t := t +< 1;
+        n := n +> 1;
+    }
+
+    return r
+}
+
+Bench.new.timethese( 1000, {
+    ash                => { a($N) },
+    holli              => { b($N) },
+#    base2-with-indices => { ($N...1).map( &i ).sum },
+#    base2-with-regex   => { ($N...1).map( &r ).sum },
+#    div2-recursive     => { ($N...1).map( &f ).sum },
+#    kernighan          => { ($N...1).map( &k ).sum },
+#    lookup-recursive   => { ($N...1).map( &l ).sum }
+})
\ No newline at end of file
diff --git a/challenge-079/markus-holzer/raku/ch-1.raku b/challenge-079/markus-holzer/raku/ch-1.raku
index 592d814445..8aa1e57dd2 100644
--- a/challenge-079/markus-holzer/raku/ch-1.raku
+++ b/challenge-079/markus-holzer/raku/ch-1.raku
@@ -1,7 +1,19 @@
-unit sub MAIN( Int $N );
+unit sub MAIN( Int \N );
 
-# This is not only the simplest, but also a quite fast solution
-# It only loses (sometimes) to the kernighan algorithm
-# See bench.raku in this directory
+my Int \t = 2;
+my Int \r = 0;
+my Int \n = N;
 
-say ($N...1).map( + *.base(2).indices(1) ).sum % 1000000007
\ No newline at end of file
+while n {
+    my Int \a = t +> 1;
+    my Int \s = N +& ( t - 1 );
+    my Int \d = N div t;
+
+    r := r +  d * a;
+    r := r +  1 + s - a if 1 + s > a;
+    t := t +< 1;
+    n := n +> 1;
+}
+
+
+say r % 1000000007;
\ No newline at end of file