#
# This function performs simple divisions on big positive integers
# in base 10 if ONE of the following three conditions is true:
#
#   * Divisor is 1 digit long (Dividend can be any length)
#   * Divisor is a multiple of 10 (Dividend can be any length)
#   * Dividend and divisor are both 15 digits or less
#
# The 1st argument should be the dividend, the 2nd the divisor.
# The 1st return value is the quotient followed by the remainder.
#
# Usage: LIST = BIGDIVN(BIGINT, DIGIT)
#
sub BIGDIVN
{
  defined $_[0] && defined $_[1] or return (0, 0);
  my $A = $_[0]; $A =~ tr|0-9||cd;    # Remove illegal chars
  my $B = $_[1]; $B =~ tr|0-9||cd;    # Remove illegal chars
  $A =~ s/^0+(.+)/$1/;                # Remove preceding zeros
  $B =~ s/^0+(.+)/$1/;                # Remove preceding zeros
  length($A) && $B or return (0, 0);  # Divide by zero?
  $B eq '1' and return ($A, 0);       # Divide by one?

  if ($B =~ m/^1(0+)$/)     # Divide by 1, 10, 100, 1000...?
  {
    my $Z = length($1);
    length($A) <= $Z and return (0, $A);
    my $Q = substr($A, 0, length($A) - $Z);
    my $R = substr($A, -$Z);
    $Q =~ s/^0+(.+)/$1/;    # Remove preceding zeros from quotient
    $R =~ s/^0+(.+)/$1/;    # Remove preceding zeros from remainder
    return ($Q, $R);
  }
  elsif (length($A) < 16 && length($B) < 16)  # Divide small numbers
    { return (int($A / $B), $A % $B); }
  elsif (length($B) != 1)
    { return (0, 0); }      # We only accept simple divisons

  # + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  # Okay, here we're going to divide a big integer by a single digit.

  # First, we create lookup tables for processing big integers.
  # These lookup tables are necessary, so we can completely
  # avoid doing divisions or multiplications.

  # The first lookup table ($LUT) is for finding the quotient.
  # When dividing any 1-digit or 2-digit number by the divisor,
  # the result is going to be found in $LUT.

  # The second lookup table ($MUL) is a multiplication table
  # in which each byte is a product of the divisor going
  # from 0 to 9. So, if we're dividing by 6, then $MUL is going to
  # hold the following: "\0\6\x0B\x12\x1B\x1E\x24\x2A\x30\x36"

  my $S = 0;           # Holds the previous multiplication's result
  my $i = -1;          # Counter goes from 0 to 9
  my $LUT = '';        # Lookup table #1
  my $MUL = '';        # Lookup table #2
  while (++$i < 10)
  {
    $MUL .= chr($S);   # Build lookup tables...
    $LUT .= chr($i) x $B;
    $S += $B;
  }

  $A =~ tr|0-9|\x00-\x09|;   # Subtract 48 from dividend's digits

  my $OUTPUT = '';     # This will hold the quotient
  my $REM = 0;         # This will hold the remainder
  my $Q;               # Current digit of the quotient
  $i = -1;             # Counter used to read digits from dividend
  while (++$i < length($A))
  {
    $S = $REM . vec($A, $i, 8);  # Merge remainder with current digit
    $Q =       vec($LUT, $S, 8);  # Calculate next digit for quotient
    $REM = $S - vec($MUL, $Q, 8);  # Calculate remainder
    $OUTPUT .= $Q;
  }
  $OUTPUT =~ s/^0+(.+)/$1/;   # Remove preceding zeros from quotient
  return ($OUTPUT, $REM);
}

sub __Test_BIGDIVN
{
  return RunTest(
  'BIGDIVN(0, 0)',                          '0 0',
  'BIGDIVN(0, 10000)',                      '0 0',
  'BIGDIVN(2179014949932, 3)',              '726338316644 0',
  'BIGDIVN(2179014949933, 3)',              '726338316644 1',
  'BIGDIVN(2179014949934, 3)',              '726338316644 2',
  'BIGDIVN(2179014949935, 3)',              '726338316645 0',
  'BIGDIVN(2179014949936, 3)',              '726338316645 1',
  'BIGDIVN(2179014949930, 5)',              '435802989986 0',
  'BIGDIVN(2179014949931, 5)',              '435802989986 1',
  'BIGDIVN(2179014949932, 5)',              '435802989986 2',
  'BIGDIVN(2179014949933, 5)',              '435802989986 3',
  'BIGDIVN(2179014949934, 5)',              '435802989986 4',
  'BIGDIVN(2179014949935, 5)',              '435802989987 0',
  'BIGDIVN(2179014949936, 5)',              '435802989987 1',
  'BIGDIVN("591092491992919449491", "0")',  '0 0',
  'BIGDIVN("18474690051828881094465", 3)',  '6158230017276293698155 0',
  'BIGDIVN("18474690051828881094466", 3)',  '6158230017276293698155 1',
  'BIGDIVN("18474690051828881094467", 3)',  '6158230017276293698155 2',
  'BIGDIVN("18474690051828881094468", 3)',  '6158230017276293698156 0',
  'BIGDIVN("18474690051828881094469", 3)',  '6158230017276293698156 1',
  'BIGDIVN("18474690051828881094470", 3)',  '6158230017276293698156 2',
  'BIGDIVN("18474690051828881094465", 5)',  '3694938010365776218893 0',
  'BIGDIVN("18474690051828881094466", 5)',  '3694938010365776218893 1',
  'BIGDIVN("18474690051828881094467", 5)',  '3694938010365776218893 2',
  'BIGDIVN("18474690051828881094468", 5)',  '3694938010365776218893 3',
  'BIGDIVN("59109249199291944949881", 8)',  '7388656149911493118735 1',
  'BIGDIVN("59109249199291944949881", "1")',                            '59109249199291944949881 0',
  'BIGDIVN("59109249199291944949881", "100000000000000000")',           '591092 49199291944949881',
  'BIGDIVN("59109249199291944949881", "10000000000000000000000000")',   '0 59109249199291944949881',
  'BIGDIVN("50000000000000000000000", "1000000000000000")',             '50000000 0',
  );
}

sub RunTest
{
  @_ or return 1;
  my $TESTS = @_ >> 1;
  my $ERRORS = 0;

  my $PTR = 0;
  my $SUBNAME = ($_[0] =~ m/([a-zA-Z0-9]+)\(/) ? $1 : '';
  for (my $i = 1; $i <= $TESTS; $i++)
  {
    my $CODE     = $_[$PTR++];
    my $CORRECT  = $_[$PTR++];
    my @RETURN   = eval($CODE);
    my $RETCOUNT = @RETURN;
    foreach (@RETURN) { defined $_ or $_ = '<undef>'; }
    my $OUTPUT   = join(' ', @RETURN);
    if ($OUTPUT ne $CORRECT)
    {
      $ERRORS++;
      print "\n", '-' x 78,
        "\nERROR #$ERRORS IN TEST $i:  $CODE  =>  |$OUTPUT| RetCount: $RETCOUNT",
        "\n\n  Correct:  |$CORRECT|\n";
    }
  }

  print( ($ERRORS) ? "\nFAIL - $SUBNAME() with $ERRORS errors." : "\nOK - $SUBNAME()");
  return ($ERRORS) ? 0 : 1;
}

__Test_BIGDIVN();