strange slow performance of BigInteger.Pow

bow-test

#!/bin/sh

# Copyright (c) 2020 Eliah Kagan <degeneracypressure@gmail.com>
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
# OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
# PERFORMANCE OF THIS SOFTWARE.

./bow 7 10000000 | awk '{ printf "%4s  %s\n", $1, $4 }'

bow.cr

# Copyright (c) 2020 Eliah Kagan <degeneracypressure@gmail.com>
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted.
#
# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
# REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
# AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
# INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
# LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
# OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
# PERFORMANCE OF THIS SOFTWARE.

require "big"

# Extends Number with bad and (fairly) good recursive exponentiation.
struct Number
  # Bad power function. Not likely to overflow the stack though...
  def bow(exponent : Int)
    raise ArgumentError.new("negative exponent unsupported") if exponent < 0

    return self.class.new(1) if exponent.zero?

    result = bow(exponent // 2) * bow(exponent // 2) # lol
    result *= self if exponent.odd?
    result
  end

  # Good power function.
  def gow(exponent : Int)
    raise ArgumentError.new("negative exponent unsupported") if exponent < 0

    return self.class.new(1) if exponent.zero?

    result = gow(exponent // 2)
    result *= result
    result *= self if exponent.odd?
    result
  end
end

# Performs a binary operation, reports timings, and returns the result.
def test(base, exponent, label, &block)
  result = nil
  elapsed = Time.measure { result = yield base, exponent }
  printf "%-4s:  %s  %s\n", label, result, elapsed
  result
end

# Tests all three exponentiation implementations, and compares their results.
def test_all(base, exponent)
  by_std = test(base, exponent, "**") { |b, e| b**e }
  by_bow = test(base, exponent, "bow") { |b, e| b.bow(e) }
  by_gow = test(base, exponent, "gow") { |b, e| b.gow(e) }

  unless by_std == by_bow == by_gow
    STDERR.puts "#{PROGRAM_NAME}: warning: the results differ!"
  end
end

# Print a error message and exit, indicating failure.
def die(message)
  STDERR.puts "#{PROGRAM_NAME}: error: #{message}"
  exit 1
end

EXAMPLE_BASE = 3
EXAMPLE_EXPONENT = 100

if ARGV.empty?
  puts "No arguments. Showing #{EXAMPLE_BASE} to the #{EXAMPLE_EXPONENT}."
  test_all(BigInt.new(EXAMPLE_BASE), EXAMPLE_EXPONENT)
  exit 0
end

die("too few arguments") if ARGV.size < 2
die("too many arguments") if ARGV.size > 2

begin
  base = BigInt.new(ARGV[0])
rescue error : ArgumentError
  die("bad base: #{error}")
end

begin
  exponent = Int32.new(ARGV[1])
rescue error : ArgumentError
  die("bad exponent: #{error}")
end

puts "Computing #{base} to the #{exponent}."
test_all(base, exponent)

bow.linq

<Query Kind="Statements">
  <Namespace>System.Numerics</Namespace>
</Query>

// Copyright (c) 2020 Eliah Kagan <degeneracypressure@gmail.com>
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

static void EnsurePositive(int exponent)
{
    if (exponent < 0) {
        throw new ArgumentOutOfRangeException(
                paramName: nameof(exponent),
                message: "negative exponents not supported");
    }
}

static BigInteger Bang(BigInteger @base, int exponent)
{
    EnsurePositive(exponent);
    if (exponent == 0) return BigInteger.One;

    var power = Bang(@base, exponent / 2);
    power *= power;
    if (exponent % 2 != 0) power *= @base;
    return power;
}

static BigInteger Whimper(BigInteger @base, int exponent)
{
    EnsurePositive(exponent);
    if (exponent == 0) return BigInteger.One;

    var power = Whimper(@base, exponent / 2) * Whimper(@base, exponent / 2);
    if (exponent % 2 != 0) power *= @base;
    return power;
}

static BigInteger Test<TOut>(BigInteger @base, int exponent, string label,
                             Func<BigInteger, int, BigInteger> impl,
                             Func<BigInteger, TOut> reporter)
{
    var ti = Util.ElapsedTime;
    var result = impl(@base, exponent);
    var tf = Util.ElapsedTime;
    reporter(result).Dump($"{label}: {tf - ti}");
    return result;
}

static void HorizontalRule()
    => Util.RawHtml("<hr/>").Dump();

static void TestAll<TOut>(BigInteger @base, int exponent,
                          Func<BigInteger, TOut> reporter)
{
    foreach (var run in Enumerable.Range(0, 2)) {
        var bang = Test(@base, exponent,
                        nameof(Bang), Bang, reporter);

        var whimper = Test(@base, exponent,
                           nameof(Whimper), Whimper, reporter);

        var pow = Test(@base, exponent,
                       nameof(BigInteger.Pow), BigInteger.Pow, reporter);

        if (!(bang == whimper && whimper == pow))
            "The results differ!".Dump("WARNING");

        HorizontalRule();
    }

    HorizontalRule();
}

// Reporters
static T Id<T>(T n) => n;
static BigInteger LastNine(BigInteger n) => n % 1_000_000_000;

TestAll(3, 1000, Id);
TestAll(3, 1_000_000, LastNine);
TestAll(3, 10_000_000, LastNine);

bow.linq.cs

// Copyright (c) 2020 Eliah Kagan <degeneracypressure@gmail.com>
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

// Paste this code into LINQPad (https://www.linqpad.net/).
// You may need to add:  using System.Numerics;

static void EnsurePositive(int exponent)
{
    if (exponent < 0) {
        throw new ArgumentOutOfRangeException(
                paramName: nameof(exponent),
                message: "negative exponents not supported");
    }
}

static BigInteger Bang(BigInteger @base, int exponent)
{
    EnsurePositive(exponent);
    if (exponent == 0) return BigInteger.One;

    var power = Bang(@base, exponent / 2);
    power *= power;
    if (exponent % 2 != 0) power *= @base;
    return power;
}

static BigInteger Whimper(BigInteger @base, int exponent)
{
    EnsurePositive(exponent);
    if (exponent == 0) return BigInteger.One;

    var power = Whimper(@base, exponent / 2) * Whimper(@base, exponent / 2);
    if (exponent % 2 != 0) power *= @base;
    return power;
}

static BigInteger Test<TOut>(BigInteger @base, int exponent, string label,
                             Func<BigInteger, int, BigInteger> impl,
                             Func<BigInteger, TOut> reporter)
{
    var ti = Util.ElapsedTime;
    var result = impl(@base, exponent);
    var tf = Util.ElapsedTime;
    reporter(result).Dump($"{label}: {tf - ti}");
    return result;
}

static void HorizontalRule()
    => Util.RawHtml("<hr/>").Dump();

static void TestAll<TOut>(BigInteger @base, int exponent,
                          Func<BigInteger, TOut> reporter)
{
    foreach (var run in Enumerable.Range(0, 2)) {
        var bang = Test(@base, exponent,
                        nameof(Bang), Bang, reporter);

        var whimper = Test(@base, exponent,
                           nameof(Whimper), Whimper, reporter);

        var pow = Test(@base, exponent,
                       nameof(BigInteger.Pow), BigInteger.Pow, reporter);

        if (!(bang == whimper && whimper == pow))
            "The results differ!".Dump("WARNING");

        HorizontalRule();
    }

    HorizontalRule();
}

// Reporters
static T Id<T>(T n) => n;
static BigInteger LastNine(BigInteger n) => n % 1_000_000_000;

TestAll(3, 1000, Id);
TestAll(3, 1_000_000, LastNine);
TestAll(3, 10_000_000, LastNine);

LICENSE

Copyright (c) 2020 Eliah Kagan <degeneracypressure@gmail.com>

Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.

THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.